A Study Of Node Movement And Deployment In Wireless Ad Hoc Network

Wireless Ad Hoc network is a collection of wireless mobile nodes which is formedwithout the aid of fixed infrastructure, and the it is of self-organizing, self-configuringand self-healing. The mobility of nodes in Ad Hoc network can have a significant effecton the network topology, and will further influence the network performance. Therefore,the main research problems of movement control which deal with the optimization ofthe network topology can greatly enhance the link availability, improve the networkconnectivity and even balance the energy consumptions. In this dissertation, we discussthe problems of Ad Hoc networks in three aspects: the optimal configuration forconnected wireless sensor networks, bi-connected mobile Ad Hoc networks, and nodes’localization with node mobility. The main contributions are listed as follows:1. A minimum number of sensor deployment algorithm for connected wirelesssensor network is proposed to cover the dispersed, non-uniform distributed targetpoints, as well as to establish a connected sensor network by the deployed sensors.When targets’ positions are available, the connected deployment problem is firstlyformulated as an integer linear program problem. And then a greedy algorithm isproposed to deploy sensors into the sub-regions where it covers maximized numberof un-covered targets. The algorithm runs iteratively until all the targets arecovered. Finally, a Steiner tree is constructed based on the already deployedsensors, and newly added sensor nodes are required at the Steiner points to connectthe deployed sensors.2. To improve the reliability of network links and extend the network lifetime, ablind node movement algorithm is proposed. The algorithm is used for Ad Hocnodes without positions, so the optimal position of a relay node is defined as thepoint where the cost of related links is minimized. To reduce the transmittingconsumption, the moving node moves according to the signal strength receivedfrom its neighbors.3. A single node movement to increase the network connectivity is proposed. Itaims to get rid of the cut vertex in the network while the ongoing applications arekept. One of the neighbors of a cut vertex which can build the link to the otherneighbor of the same cut vertex but in different part with minimized energyconsumption is selected to move. And node moves according to the signal strength received from its1-hop neighbors, the cut vertex and its counterpart. Based on thesingle node movement algorithm, more nodes which are neighbors of the cutvertex, are needed to move to increase the bi-connectivity rate. Similarly, One ofthe neighbors of a cut vertex is required to move with minimized energyconsumption at each time.4. A node movement based localization algorithm is introduced for nodes whichlack of GPS. In static networks, a node firstly moves along the+x,+y axis, and its1-hop neighbors sample the signal strength from the moving node and convert eachvalue to the distance to the moving node. Position of the1-hop neighbors in localcoordinate system of the moving node can be calculated by trilateral rule, and thennodes positions in the network coordinate system are available according to thesum of position vectors. Since node postion changes with its moving, a data tableis required to reduce the energy consumption for re-computing and also ensure thelocation accuracy. There is no need to acquire the position using the anchor nodes.