Optimization algorithms in wireless sensor networks.

摘要

Wireless Sensor Networks (WSN) recently has attracted the attention of many researchers. In particular, Wireless Sensor and Actor Networks (WSAN) has attracted attention due to the heterogeneity of their nodes. They consist of two types of nodes: static sensor nodes, and mobile actor nodes. In this dissertation, we first study the Minimizing Multi-hop transmission Range (M2R) problem. Various heuristics are proposed for this problem, and their results are compared by thorough simulations. Then, we introduce the Minimizing Range and actor Movement Simultaneously (MRaMS) problem, and its multi-hop version, the M2RaMS problem. To find a solution to these problems, we introduce an optimal ILP formulation. For the ILP solution to be feasible, we introduce a finite set of potential actor positions such that an optimal solution is guaranteed to be found within this set. Due to the complexity of the problem, we propose several heuristics, and compare their performance through extensive simulations.;Another area we investigate in WSN is the design of algorithms for barrier-coverage. A subset of sensor nodes provides barrier-coverage over an area of interest if the sensor nodes are dividing the area into two regions such that any object moving from one region to another is guaranteed to be detected by a sensor node. An area of interest usually contains multiple barrier-coverages, which are then scheduled in sequence to maximize the lifetime of the coverage. In this dissertation, we introduce a new security problem in scheduling algorithms for barrier-coverage, namely, the Maximum Lifetime Non-penetrable Barrier-coverage (MaxLNB) problem. The problem arises due to weak points that we have found in previous sleep-wakeup algorithms that allow intruders to cross the barrier. We show the existence of barrier-breaches, which allow the penetration of an area when one barrier-cover is replaced by another. To deal with this issue, we propose three different algorithms to solve the problem. We compare their performance via simulations and discuss the results.;Lastly, this dissertation addresses another barrier-coverage problem. In many practical scenarios in barrier-coverage, it may be desirable to detect an intruder that enters the region through any of its sides and exits through any other of its sides. That is, not only detect top-down movement, but also side-to-side, and even turning from one side to another. We define a new barrier-coverage problem, namely, the Maximum Lifetime Reinforced Barrier-coverage (MaxLRB) problem, whose objective is to maximize the network lifetime such that any penetration of the intruder is detected. To solve the problem, we create a new form of sensor barriers, which we refer to as reinforced barriers, which can detect any movement variation of the intruder. Also, we propose three approaches to obtain these barriers from a given layout of sensor nodes, and we compare their relative performances through extensive simulations.