Wu, Jie

Wireless ad hoc networks (or simply ad hoc networks) are infrastructureless multihop
networks consisting of mobile or stationary wireless devices, which include mobile
ad hoc networks (MANETs) and wireless sensor networks (WSNs). These networks are
characterized by limited bandwidth and energy resources, frequent topology changes,
and a lack of central control. These characteristics lead to the research challenges of ad
hoc networks. The algorithms designed for ad hoc networks should be localized, selforganizing,
and energy efficient. A connected dominating set (CDS) is frequently used in
ad hoc networks as a virtual backbone to support efficient routing, service discovery, and
area monitoring. In addition, efficient broadcasting (i.e., finding a small set of forward
nodes to ensure full delivery) can be viewed as forming a CDS on-the-fly. The periodically
maintained virtual backbone is called a static CDS, and the temporarily formed
forward node set is called a dynamk CDS. For efficiency and robustness, the ideal CDS
construction algorithm is lightweight, has fast convergence, and minimizes the CDS size. Recently, due to some specific applications and new techniques, the concept of a connected
dominating set can be modified or further extended for more efficient usage.
This dissertation focuses on the variations with applications of the connected dominating
set, designing new concepts, and developing new algorithms for them. A review
of CDS construction algorithms for ad hoc networks has been provided at the beginning.
An efficient scheme, called Rule K, has been proposed for static CDS construction. Rule
K achieves a probabilistic constant upper bound on the expected CDS size, which is currently
the best known performance guarantee for localized CDS algorithms. Several CDS
algorithms are extended to generate the extended CDS, which exploits the cooperative
communication technique to further reduce the size of CDS. A k-coverage set is developed
for higher robustness. With the equipment of directional antennas , the transmission
can be restricted to some certain directions to reduce interference and energy consumption.
The corresponding directional CDS is discussed. Finally, a wireless sensor and actor
network (WSAN) is introduced and localized algorithms are designed for it.

Peer-to-peer (P2P) networking has been receiving increasing attention from the
research community recently. How to conduct efficient and effective searching in such
networks has been a challenging research topic. This dissertation focuses on unstructured
file-sharing peer-to-peer networks. Three novel searching schemes are proposed,
implemented, and evaluated. In the first scheme named ISRL (Intelligent Search by Reinforcement
Learning), we propose to systematically learn the best route to desired files
through reinforcement learning when topology adaptation is impossible or infeasible. To
discover the best path to desired files, ISRL not only explores new paths by forwarding
queries to randomly chosen neighbors, but also exploits the paths that have been discovered
for reducing the cumulative query cost. Three models of ISRL are put forwarded: a
basic version for finding one desired file, MP-ISRL (MP stands for Multiple-Path ISRL)
for finding at least k files, and C-ISRL (C refers to Clustering) for reducing maintenance
overhead through clustering when there are many queries. ISRL outperforms existing searching approaches in unstructured peer-to-peer networks by achieving similar query
quality with lower cumulative query cost. The experimental results confirm the performance
improvement of ISRL. The second approach, HS-SDBF (Hint-based Searching
by Scope Decay Bloom Filter), addresses the issue of effective and efficient hint propagation.
We design a new data structure called SDBF (Scope Decay Bloom Filter) to
represent and advertise probabilistic hints. Compared to existing proactive schemes, HSSDBF
can answer many more queries successfully at a lower amortized cost considering
both the query traffic and hint propagation traffic. Both the analytic and the experimental
results support the performance improvement of our protocol. The third algorithm, hybrid
search, seeks to combine the benefits of both forwarding and non-forwarding searching
schemes. In this approach, a querying source directly probes its own extended neighbors
and forwards a query to a subset of its extended neighbors and guides these neighbors
to probe their own extended neighbors on its behalf. The hybrid search is able to adapt
query execution to the popularity of desired files without generating too much state maintenance
overhead because of the 1-hop forwarding inherent in the approach. It achieves
a higher query efficiency than the forwarding scheme and a better success rate than the
non-forwarding approach. To the best of our knowledge, this work is the first attempt
to integrate forwarding and non-forwarding schemes. Simulation results demonstrate the
effectiveness of the hybrid search.

This thesis describes a resource discovery technique in mobile ad hoc networks.
Resource discovery is technique to search data in among the mobile nodes in the network.
The highly dynamic nature of the infrastructure-less ad hoc networks poses new
challenges in resource discovery, thus there is a need to for an optimized resource
discovery technique. Efficient resource discovery algorithm discovers the resources in a
mobile ad-hoc network in an optimized way. As there is no pre-established infrastructure
in the network, every node takes its decision in forwarding resources and every node
dynamically ranks these resources before disseminating them in the network. Ranking of
the resources spreads the data which is of high priority at that instance of time. Ranking
avoids the spreads the unwanted or low priority data which will utilize the bandwidth
unnecessarily. The efficient resource discovery algorithm also keeps a check that
redundant information is not spread in the network with the available bandwidth and the
bandwidth is utilized in an optimized manner. We then introduce brokers in the algorithm
for a better performance. We present a technique to maintain a constant number of
brokers in the network. Our simulations show that, in a network with high density, the
efficient resource discovery algorithm gives a better performance than the flooding and
rank based broadcast algorithms.

Due to the dynamic nature of P2P systems, it is impossible to keep an accurate
history of the transactions that take place while avoiding security attacks
such as whitewashing and collusion, and abuse such as freeriding . This is why it
is important to develop a mechanism that rewards cooperative peers and punishes
misbehaving peers. Modeling P2P networks as social structures can allow incentive
mechanisms to be used that prevent the negative behaviors mentioned. In this thesis,
we extend a social network algorithm to include credit transfer between peers in
order to reduce the path length of queries. We also develop a selection strategy that
involves different aspects of peer interactions in P2P networks, which is promoted by
our credit transfer mechanism that discourages misbehaving peers by taking away
credits that they have with good peers and transferring them to more cooperative
ones. The simulation results show that our algorithm is effective in reducing the
debt between peers, meaning that peers become more cooperative, and shortening
the average path length to a satisfied query while increasing delivery ratio.

In mobile ad hoc networks, it is challenging to solve the standard problems
encountered in fixed network because of the unpredictable motion of mobile nodes.
Due to the lack of a fixed infrastructure to serve as the backbone of the network, it
is difficult to manage nodes' locations and ensure the stable node performance. The
virtual mobile node (VMN) abstraction that has been applied implements an virtual
mobile node that consists of a set of real nodes traveling on one predetermined virtual
path to collect messages and deliver them to the destinations when they meet. It
conquers the unpredictable motion with virtual nodes' predictable motion. But it
encounters unavoidable failure when all the nodes leave the VMN region and stop
emulating the VMN. We extend the idea of the VMN abstraction to the Multi-path
Intelligent Virtual Mobile Node (MIVMN) abstraction, which allows the messages
to switch between multiple Hamiltonian paths to increase the message delivery ratio
and decrease the failure rate of the virtual nodes. Through simulation results we
show that the MIVMN abstraction successfully meets our goals.

Wireless sensor networks or WSNs continually become more common in todays world. They
are able to give us a constant view into the world as they gather information and make this information
more readily available. The infonnation these networks gather and contain is valuable and protecting
it is of great importance. Today more and more devices are becoming wireless and mobile. This
is allowing for very diverse networks to be created and they are constantly changing. Nodes in
these networks are either moving to different positions or going offi ine which constantly changes the
overall layout of the network. With this increasing connectivity of today's devices this opens the
door for possibility for these types of networks to become targets by malicious objects designed to
bring harm to the network. Many unre liable networks already face many problems such as having
to optimize battety life and being deployed in areas where they can be damaged. A malicious object
in this type of network has the power to destroy data and deplete the networks limited resources
such as bandwidth and power. Removal of these malicious objects can also have a negative effect
on these limited resources. We must find a way to remove these malicious objects in a way that
minimizes loss to the network. In this paper we will look at the information survival threshold of these types of networks. Certain controllable parameters exist that directly impact the survival rate
of all data in the network. We will combine this with the addition our own self-replicating objects to
the network designed to neutralize their malicious counterparts. We will examine these information
survival threshold parameters along with specific parameters available to the network. We shall see
how these parameters affect overall survival of data in the network and their impact on our own good
data.

Parallel/distributed systems offer a tremendous processing capacity. However, in order to take full advantage of it, good load distributions are needed. We study the task graph partition problem for a given parallel/distributed application which is modeled using data parallelism and is implemented in a transputer system in a mesh construction. Our approach uses domain partition to separate a given domain into a set of subdomains of equal size and each of which has at most four neighbors. We devise three methods to partition a given domain, these methods are compared based on several criteria. The impact of the number of processors used in implementation is also investigated based on several parameters, including processor speed, communication speed, and amount of computation and communication per data point. We discuss implementation of our approach in the application based on the existing features of the transputer system, and compare different versions of application through running a simulation system.

Fault tolerant programming methods improve software reliability using the principles of design diversity and redundancy. Design diversity and redundancy, on the other hand, escalate the cost of the software design and development. In this thesis, we study the reliability of hybrid fault tolerant systems. Probability models based on fault trees are developed for the recovery block (RB), N-version programming (NVP) and hybrid schemes which are the combinations of RB and NVP. Two heuristic methods are developed to construct hybrid fault tolerant systems with total cost constraints. The algorithms provide a systematic approach to the design of hybrid fault tolerant systems.

Mesh-connected multicomputers are one of the simplest and least expensive structures to build a system using hundreds and even thousands of processors. The nodes communicate with each other by sending and receiving messages. As the system gets larger and larger, it not only requires the routing algorithms be efficient but also fault-tolerant. The fault model we use in 2-D meshes is a faulty block while in 3-D meshes, the fault model is a faculty cube. In order to route messages through feasible minimum paths, the extended safety level is used to determine the existence of a minimal path and faulty block (cube) information is used to guide the routing. This dissertation presents an in-depth study of fault-tolerant minimal routing in 2-D tori, 3-D meshes, and tree-based fault-tolerant multicasting in 2-D and 3-D meshes using extended safety levels. Also path-based fault-tolerant deadlock-free multicasting in 2-D and 3-D meshes is studied. In fault-tolerant minimal routing in 2-D meshes, if no faulty block is encountered, any adaptive minimal routing can be used until the message encounters a faulty block. The next step is guided by the faulty block information until the message gets away from the faulty block. After that, any minimal adaptive routing can be used again. The minimal routing in 2-D tori is similar to that in 2-D meshes if at the beginning of the routing a conversion is made from a 2-D torus to a 2-D mesh. The fault-tolerant minimal routing in 3-D meshes can be done in a similar way. In the tree-based multicasting in 2-D and 3-D meshes, a time-step optimal and traffic-step suboptimal algorithm is proposed. Several heuristic strategies are presented to resolve a conflict, which are compared by simulations. A path-based fault-tolerant deadlock-free multicast algorithm in 2-D meshes with inter-block distance of at least three is presented to solve the deadlock problem in tree-based multicast algorithms. The approach is then extended to 3-D meshes and to inter-block distance of at least two in 2-D meshes. The path is Hamiltonian that is only updated locally in the neighborhood of a faulty block when a faulty block is encountered. Two virtual channels are used to prevent deadlock in 2-D and 3-D meshes with inter-block (inter-cube) distance of at least three and two more virtual channels are added if the inter-block distance is at least two.

This thesis describes routing in mobile ad hoc wireless networks. Ad hoc networks are lack of wired backbone to maintain routes as mobile hosts move and power is on or off. Therefore, the hosts in ad hoc networks must cooperate with each other to determine routes in a distributed manner. Routing based on a connected dominating set is a frequently used approach, where the searching space for a route is reduced to nodes in small connected dominating set subnetwork. We propose a simple and efficient distributed algorithm for calculating connected dominating set in a given un-directed ad hoc network, then evaluate the proposed algorithm through simulation. We also discuss connected dominating set update/recalculation algorithms when the topology of the ad hoc network changes. We also explore the possible extension of using hierarchical connected dominating set. The shortest path routing and the dynamic source routing, which are based on the connected dominating set subnetwork, are discussed.