Study On Topology Of Wireless Ad-Hoc Networks

The pervasive computing system, which integrates the collection, transmission, processing and utilization of information into a harmonious whole, shows us a prosperous vision for a bright future of information society.Wireless network is one of the fundamental building blocks of the forthcoming century of pervasive computing. In this dissertation, we investigated some key research issues about the topology of wireless ad-hoc networks including the connected dominating set problem, localization of the nodes, lifetime analysis of WSNs under different routing protocols and topologies, and the trusted computing for the network topology.The main results of this dissertation are as follows:(1) A detailed survey of the previous research works on the topology of wireless ad hoc networks is given in this dissertation. In the survey mentioned above, we proved the expressions of the average length of edges in YG and the connectivity of UDG, respectively. The topology relationships between different graphs are studied and the simulation results of some important parameters are obtained.(2) Using some geometric information as the heuristics, several distributed and centralized approximation algorithms for the CDS problem in UDGs are proposed in this dissertation. The simulation results show that our algorithms perform better than some known ones.(3) The conceptions of the Complete Voronoi Diagram (CVD) and the Mirror Image distribution are defined respectively, and the center effect of the CVD is interpreted through the proving of the expression of the probability density function of the mirror image distribution. The following expressions have also been proved: the expresson of the average localization errors of the CVD based algorithms; the expression for the relationship between the number of vertices, edges and faces in CVD; the expression of the average length of chords in CVD; and the expression for the average number of edges of an attached pologon in CVD. The Polling technique which, to our knowledge, is the first technique that can make use of the information provided by unknown nodes to help us improve the error performance of the CVD based localization algorithms has been proposed, and the mathematical interpretation for the principle of the Polling has been presented. The error performance of the localization scheme in presence of signal strength measurement erros is investigated through simulations.(4) Lifetime model for the wireless sensor networks (WSNs) under different routing protocls and topologies has been proposed. Using this model we can calculate the average energy dissipation ratio of anywhere in the network region and predict the average lifetime of WSNs.(5) Aε-anslysis technique for handling the round off errors and the methods to deal with the degeneration cases are proposed. The methodologies mentioned in this dissertation can help us efficiently improve the robustness of the implementation of the Voronoi diagram construction algorithms and ensure the correctness of the computation results.