Connectivity Algorithms Design And Analysis In Wireless Mobile Network

Connectivity is the most basic requirement to guarantee the communications of boththe wired and wireless network. It is much more challenging to study the connectivity ofthe Wireless Mobile Network, where the connectivity of the network exhibits a propertyof dynamics compared with its counterpart, wired network, due to the user’s moving,battery depletion, malicious attacks etc. As one of the most particular characters ofwireless mobile network, mobility not only brings conveniences to users, but also bringsopportunities to improve the network connectivity. For example, in an unconnectedvehicular network, the mobile vehicles can act as the store-and-forward relays; in aconnected cellular network, mobile base station on a car can be used to improve thequality of local wireless communication environment. This thesis aims at studying howto exploit the mobility of users to improve the connectivity of the network, i.e., studyingthe wireless localization problem, the network topology recovery problem, the networkfault tolerance problem, and the network k-connectivity problem. These studies onabove four problems systematically investigate the network connectivity from theperspectives of prerequisite conditions, passive recovery, active prevention, andextensive analysis. The principle contributions are illustrated as follows.1. LocalizationLocalization is one of the prerequisite conditions to study the connectivity of thewireless mobile network. In this thesis, a new localization estimation algorithm forWireless Sensor Network (WSN) is proposed based on Grid-Scan method. It runs oneach sensor node which is unknown to its position (nodes aware of their positions areanchors). By exploiting the positions of the1-hop and2-hop neighbor anchors, theproposed algorithm firstly divides the intersection region of1-hop anchors wirelesscommunication area into grids, and then determine the possibility of each grid, where itmay locate. Finally, the average position of all possible grids is regarded as its estimatedposition. Simulation results show that the proposed algorithm achieves better accuracythan DLE. 2. Network Partition RecoveryIn the first thrust area of connectivity, the network partition problem is studied, andtwo movement control algorithms based on Steiner Tree and Minimized ConnectedDominated Set (MCDS), named Steiner Movement Control algorithms (SMC) andSteiner tree and MCDS movement control algorithm (SteinerMcds) respectively, areproposed to reconnect the partitioned network, which may consist of severaldisconnected sub-networks.In the first movement control algorithm, SMC, a Steiner Tree is computed firstlyby calling the3STP-MSP algorithm, where the vertices contain all the nodes inthe network and the introduced Steiner points. Then the introduced Steinerpoints are regarded as movement destinations, and some nodes are selected andmoved to these Steiner points. SMC runs iteratively until the network isconnected.The second algorithm, SteinerMcds, however, computes the MCDSs of thesub-networks first. And then a Steiner Tree is computed to connect the MCDSs.Finally, the nodes which are not in MCDSs are matched with, and moved to theSteiner points to reconnect the network. SteinerMcds runs iteratively until thenetwork is connected.Simulation results show that both of the proposed algorithms SteinerMcds and SMCoutperform the PMST-based PMST-UV algorithm in terms of the number of iterations,the total distance of movement, the average and maximum distance of movement pernode. As for the proposed algorithms of SteinerMcds and SMC, SMC outperformsSteinermcds in terms of total number of moved nodes and success rate, whileSteinerMcds outperforms SMC in terms of the number of iterations and the maximumdistance of movement.3. Network Fault ToleranceIn the second thrust area of connectivity, the problem of improving the connectivityof a1-connected network to a2-connected network is studied, such that the network cantolerate more network faults. A novel movement control algorithm, based on removablenode, is proposed. The principle contributions include the followings aspects: Anew concept, removable node, is proposed firstly in graph theory. Aremovablenode has the following merits: if a removable node u is removed from aconnected graph G, neither will G disconnect nor will new cut-node appear.Further, a distributed removable node identification algorithm is proposed.The concept of feasible set of removable nodes is proposed, where if all of theremovable nodes of the set are removed simultaneously, neither will Gdisconnect nor will new cut-node appear. Further, a sufficient condition offeasible set of removable nodes is given.Based on the feasible set of removable nodes and the sufficient condition, adistributed movement control algorithm is proposed to match the removablenodes and the cut nodes, with the objectives of bi-connecting the final network,minimizing the total number of moved nodes, and minimizing the total distanceof nodes movement.The problem of moving the matched removable node to its cut-node isformulated as a convex optimization problem, with the objective of minimizingthe distance of nodes movement. By solving the formulated convex optimizationproblem, the final optimal movement destination can be obtained theoretically.Simulation results show that at least40%of all of the nodes are removablenodes in1-connected network and the proposed removable nodes identificationalgorithm can identify most of the removable nodes (87%~100%). Theproposed movement control algorithms have merits in terms of large successrate, a small number of moved nodes, and a short total distance of nodesmovement. In addition, the proposed algorithms are shown to be effective evenwhen there are a large portion of fixed nodes in the network.4. k-Connectivity AnalysisIn the third thrust area of connectivity, the specific character of the Vehicular AdHoc Network (VANET) is studied, where the departure of the vehicles may disconnectthe network. Due to the unique feature of k-connected network that any (k-1) arbitrarynodes’ failure will not disconnect the network, we focus on analyzing the probability ofnetwork k-connected. And a novel method is proposed to compute the exact probability of the1-dimensional vehicular network to be k-connected, and to derive the expectationof the maximum number of tolerable vehicles departures. The following results areobtained.A sufficient and necessary condition is derived for the vehicular network to bek-connected, which indicates that the network is k-connected if and only if thesum of any k successive spacing, interval distance between adjacent nodes, isless than R, the wireless communication radius of the vehicles.Then, based on the sufficient and necessary condition, the expression of theprobability of the network being k-connected is derived in closed form.To obtain the exact value of the derived expression, the Marking algorithm inorder statistics is imported, and the examples are presented to illustrate thecomputation of the algorithms. Particularly, the special case of the obtainedresults, when k=1, coincides with the existing works, and when k>1, theaccuracy of the obtained probability of the network k-connected is evaluatedthrough simulation.Simulation results confirm the accuracy of our analysis, and indicate that theexpectation of the maximum number of tolerable vehicle departures increasesalmost linearly with the total number of vehicles.