Font Size: a A A

Research On Geographic Routing Algorithm In Mobile Ad Hoc Network

Posted on:2014-02-01Degree:DoctorType:Dissertation
Country:ChinaCandidate:Z QianFull Text:PDF
GTID:1268330392972566Subject:Computer system architecture
Abstract/Summary:PDF Full Text Request
Mobile Ad Hoc Networks (MANET) is a self-configured multi-hop wirelesscomunication network consisting of mobile nodes. The unique structrue andconfiguration differentiate MANET from traditional network in many aspects suchas requiring no infrastructrue, dynamic topology, demanding on resources and so on.These charactoristics prevent applying traditional network routing technologes inMANET, thus designing routing algorithm for MANET become a researchchallenge.Currently, most MANET routing algorithm discover path according to thetopological information of network. Such topology based routing can produceoptimal path and guarantee packet delivery, however, it is not suitable for large scalenetwork due to the overhead while acquiring topological information of globalnetwork. Benefited localized path discovering strategy, the geographic routingalgorithm achieves high scalability by maintaining low overhead even in large scalenetwork. In recent years, as the network positioning algorithm and satellitepositioning technology developing, the positioning cost decreasing while theprecision enhancing. The routing algorithm that utilizing position to construct pathdraws attention for affordable positioning cost as well as its own strengths. Based onthe analysis of MANET characteristics and current research on routing algorithm,the thesis mainly focuses on the position based routing algorithm in MANET. Themain contents and contributions of this dissertation are indicated below.First, based on the analysis of communication void problem that fails thegreedy forwarding due to the local minimum phenomenal, a routing algorithmGFVB with reactive void handling scheme is proposed. In the network that eachnode maintains only one hop neighbors distribution, the void handling resume therouting task until greedy forwarding failure for local minimum phenomenon. Whenvoid polygon contain concave boundary, the path around such boundary will recruitmany unnecessary boundary nodes in path to destination. To resolve the detour pathproblem incur by concave boundary, GFVB construct virtual boundary between theend nodes of concave boundary, the packets that will across the void redirect to theend node of concave boundary, thus reduce the number of concave boundary nodesand hop counts. Both theoretical analysis and simulation indicate that GFVB iseffective enhance the routing performance for network with concave void.Then, for the blind path selection problem, routing algorithm GRID withproactive void handling scheme is proposed. In the network that each nodemaintains only one hop neighbor’s distribution, without information of void, path to destination may tend to approach along the longer boundary of void. By introducingthe void detect algorithm, the void information can be broadcasted in the vicinity ofvoid, thus the routing algorithm can select the short boundary of the void. To reducethe cost of broadcast, void coverage rectangle is used to denote of the void forsimplification, and the vertex forwarding is employed to construct the path aroundthe void. The detour path problem is partially resolved as well as the blind selectionproblem, these help the GRID algorithm achieve low end to end delay, energyconsumption and high delivery rate. Different from traditional strategy that usingbackup scheme to resume after greedy forwarding scheme failure, GIRD utilizesmaximally to construct path to destination around the void.Moreover, for the problem that CGF routing algorithm recruit unnecessaryboundary node, a boundary optimal routing algorithm BOPF is proposed. To reducethe boundary nodes in path, BOPF send back the information about the landmark.Different from using dedicated probe packet to find the landmark in the GLR, theBOPF use regular data packets. Besides, different from GLR which define theswitch node as landmark, BOPF send back all landmark candidates to source fordecision. Simulation shows BOPF can effectively reduce the routing overhead,increase delivery rate and percent of optimal path.Finally, to handling the coupling effect in multipath routing, a partition basednode disjoint multipath routing algorithm RPOM is proposed. The algorithmheuristically construct multipath, using single path routing algorithm to constructthe main path, then find more paths outside the main path coverage area. Althoughthe multipath is not built at once, the RPOM avoid using the costly route requestbroadcast in traditional multipath algorithm. Also, different from traditionalmultipath routing with the static area partition, RPOM find multipath according toexisting path, its area partition relate with built path, which make it adaptive todynamic deployed network.
Keywords/Search Tags:Ad hoc network, geographic information, greedy forwarding, void handling, reliability
PDF Full Text Request
Related items