Optimized relay node placement for federating wireless sensor sub-networks

Wireless sensor networks (WSNs) have recently received increasing attention due to a growing list of applications. Most notable among the applications are those in harsh environments, such as coast and border protection, search-and-rescue and battlefield reconnaissance. A WSN in these applications may get partitioned into multiple disjoint segments (sub-networks) due to major damage in some part of the network, e.g. inflicted by explosions in battlefield. Since WSNs are often employed to assist in risky missions and to deal with the event that caused the damage itself, it is desired to connect these disjoint partitions in order to restore the full operation of the network. In addition, linking sub-networks may be mandatory in some application setups in which there are multiple autonomous, independently-operating, WSNs that need to collaborate to perform a joint task. For example, a number of existing stand-alone WSNs may be required to operate jointly in order to deal with a major disaster. Connecting multiple WSNs or segments of a damaged WSN is referred to as federation in this dissertation.In this dissertation, we tackle the challenges in federating a partitioned WSN or autonomous wireless sensor sub-networks. In particular, we form a federated system of multiple network segments by deploying the least number of additional relay nodes in the proper locations. We focus on two major factors related to relay placement. The first is the connectivity requirement which is characterized by the distances between every pair of two segments. Those distances may be longer than twice the communication range of a single relay node, which requires consideration of the inter-relay connectivity. In addition, linking the segments may be subject to varying inter-segment quality of service (QoS) requirements. Since finding the optimal count and position of relay nodes is known to be NP-hard, we pursue heuristics.We present three novel approaches in this dissertation. The first approach populates relays towards the center of the area to form a connected inter-segment topology. In the second approach, we design a distributed self-healing algorithm which repositions existing mobile nodes to connect the segments. The third approach incrementally places the relays, addressing the connectivity and QoS requirements one path at a time. It opts to minimize the number of required relays to establish connectivity by maximizing the resource utilization of the deployed nodes. The correctness, convergence and time complexity of those proposed approaches are analyzed and their effectiveness is evaluated through extensive simulation experiments. The resulting topology is also analyzed in comparison to alternate solutions found in the literature.