Algorithms for optimized node and data placement in wireless sensor and ad hoc networks

This research work focuses on node and data placement in wireless communication networks. We investigate two related challenging problems in wireless communication networks: the Constrained Relay Node Placement problem and the Cooperative Caching problem.;For each one, we present an introduction and the problem definition along with a note of our contributions. Then we present a survey of the state of the art in each area. Finally, we present our research in details for both problems including formal problems definitions, underlying assumptions, system models, proposed algorithms, utilized techniques, theorems, proofs, simulations setups, results and analyses.;i) The constrained relay node placement problem in a wireless sensor network seeks the deployment of a minimum number of relay nodes (RNs) in a set of candidate locations in the network to satisfy specific requirements, such as connectivity or survivability. In this work, we study the constrained relay node placement problem in an energy-harvesting wireless sensor network in which the energy harvesting potentials of the candidate locations are known a priori. Our aim is to place a minimum number of relay nodes to achieve connectivity or survivability, while ensuring that the relay nodes harvest large amounts of ambient energy. We explore related work on the constrained relay node placement problem in wireless sensor networks. We present the connectivity and survivability problems, discuss their NP-hardness, and propose polynomial time O(1)-approximation algorithms with low approximation ratios to solve them. We validate the effectiveness of our algorithms through numerical results to show that the RNs placed by our algorithms harvest 50% more energy on average than those placed by the algorithms unaware of energy harvesting. We also develop a unified-mixed integer linear program (MILP)-based formulation to compute a lower bound of the optimal solution for minimum relay node placement and demonstrate that the results of our proposed algorithms were on average within 1.5 times of the optimal. ii) Wireless ad hoc networks (WAHNs) consist of autonomous nodes cooperating with each other to transmit/receive data over multiple-hops in the network. Caching is a useful mechanism to leverage this cooperation. Nodes with cached content can satisfy requests from other nodes, thus helping reduce network traffic and energy consumption, and improve latency. With the proliferation of wireless devices on the Internet and the proposal of a future Internet with emphasis on in-network caching, improvements in caching can significantly improve network response while reducing network load. In this study, we present a holistic caching framework, Split-Cache, which enables a network node to account for the frequency of requests of data items and their presence in the network, and to leverage a split-cache (one part caches popular items and the other caches less popular items) to make caching and cache-eviction decisions. We performed exhaustive simulations to compare Split-Cache with the state-of-the-art: Split-Cache improved the average cache-hit rate by at least 5%, cache request resolution time on an average by 30%, and required almost 15% less traffic on average for every resolved request.