The Relocation Of Mobile Sensors For Coverage Holes Healing In Hybrid Wireless Sensor Networks

Coverage is one of the primary research areas of the quality of service in wirelesssensor networks (WSN). The main objective of it is to ensure that every point on themonitor area will be at least covered by one sensor. However, sensors may fail due tolacking of energy or environmental changing in real world, and coverage holes mayarise in WSN. The quality of service in WSN cannot be ensured with the existence ofthe coverage holes. In order to solve this problem, coverage holes’ healing performscoverage recovery in WSN.The relocation of mobile sensors is one of the main fields of coverage holes’healing in hybrid wireless sensor networks. It assigns mobile sensors to the locations ofthe coverage holes and recovers those areas. However, most of the existing works haveproblems of relocating mobile sensors for healing timeliness coverage holes or incascade movement. Furthermore, the existing works also have problems of mobilesensors’ energy consumption in the relocation or in coverage holes’ on-line healing.Based on the above observations, the relocation of mobile sensors in the abovefour problems are studied in this dissertation. Firstly, a mobile sensors’ relocationprotocol for healing the timeliness coverage holes is proposed in a grid-based model.Secondly, a distributed algorithm for mobile sensors’ relocation in cascaded movementis suggested by separating mobile sensors from their vacancies. Thirdly, an optimizationscheme for mobile sensors’ moving energy cost in the relocation is proposed bycombining two single-objective algorithms. At last, algorithms assigning mobile sensorsfor healing coverage holes in the on-line fashion are suggested by partitioning,embedding and on-line matching cells.The above studies contain the following innovative results:1. A grid-based timeliness coverage holes’ healing model is proposed with adistributed multiple mobile sensors scheduling protocol. Existing algorithms may sufferfrom conflicts when multiple timeliness coverage holes appear at the same time in WSN.The grid-based timeliness coverage holes’ healing model solves this problem throughpartitioning grids by the coverage holes’ recovery delay. Based on the model, the distributed protocol realizes mobile sensors’ relocation and avoids the conflicts.2. A new algorithm is proposed to perform mobile sensors’ cascade movement. Inexisting works, mobile sensors in cascade movement also suffer from conflicts, and theproblem becomes worse as the mobile sensors cannot move at the same time. It isindicated in this dissertation that mobile sensors can be classified into S type and E type,and the later ones’ movement generate new coverage holes. By separating vacanciesfrom the E type mobile sensors, algorithms designed for direct movement can beimplemented to relocate mobile sensors in cascade movement. Based on this result, adistributed algorithm is proposed for mobile sensors’ cascade movement. This algorithmenhances coverage holes’ healing ratio when the mobile sensors’ maximum movingdistance is limited.3. A bi-objective mobile sensors’ relocation algorithm is suggested. Existing workscannot observe moving energy cost of all the mobile sensors and a single mobile sensorat the same time. By combining two single-objective-optimal algorithms, a bi-objectivealgorithm is suggested with the objectives of minimizing all mobile sensors’ totalmoving energy cost and minimizing a mobile sensor’s maximum moving energy cost.This algorithm accomplishes moving energy cost control of all the mobile sensors and asingle mobile sensor in the coverage holes’ healing.4. Algorithms that relocate mobile sensors for coverage holes’ on-line healing aresuggested. Existing works cannot relocate mobile sensors for healing the coverage holesthat appear one at a time. The work in this dissertation partitions a monitor area intocells of equal size and embeds the cells into a hierarchically well separated tree (HST).Based on the HST, a centralized two-objective mobile sensors’ on-line relocationalgorithm is suggested. Furthermore, a simple distributed on-line algorithm is suggestedfor the same objectives based on the centralized one. It combines the partitioning ofcells for a laminar family and the on-line matching of cells in one step. The mobilesensors’ on-line relocation algorithms heal the coverage holes that appear one at a timeand maintain networks’ coverage effectively.