Boundary mapping and its application to geographic routing

Lemmon, Colin John (2010) Boundary mapping and its application to geographic routing. PhD thesis, James Cook University.

[img] PDF (Thesis front)
Download (157kB)
[img] PDF (Thesis whole)
Download (2MB)
 
420


Abstract

Geographic routing is a self organizing, low overhead, distributed system for routing in ad-hoc wireless networks. Practical application of this approach is limited due to the lack of global information to deal with local minima at voids or the outer boundary. To address this problem, an improved geographic forwarding strategy Greedy-BoundedCompass was developed to reduce the instance of local minima. Greedy-BoundedCompass allows packets to move away from the destination without looping in situations where Greedy forwarding would fail. Greedy-BoundedCompass was applied to Greedy Perimeter State Routing (GPSR) to confirm its effectiveness as an alternate forwarding strategy.

The Boundary Mapping Protocol (BMP) was then developed to detect local minima, and probe boundaries; handling branches, edge crossovers, detecting probe home, and boundary confirmation. Using BMP, a multi-strategy Boundary State Routing protocol (BSR) was developed which incorporated Greedy-BoundedCompass forwarding. BSR manages boundary exit points, path selection for boundary traversal, swapping of boundaries, and loop prevention with multimode strategies. In response to performance issues, a low resolution grid occupancy mapping system was developed as a replacement for BMP to address excessive probe overhead and memory requirements. Implementation, testing, and analysis of the improved geographic routing strategies were performed using a purpose built network simulator. Metrics used included path completion rate, route efficiency, control overhead, and memory requirements.

Greedy-BoundedCompass reduced the number of local minima, improving the path completion rate of Greedy forwarding by 49.2% in sparse networks with a significant improvement in route efficiency of 8.9%. Greedy-BoundedCompass applied as a replacement for Greedy forwarding in GPSR also demonstrated a significant improvement in route efficiency. BSR then demonstrated a significant improvement in route efficiency over improved GPSR of 46.1% in sparse networks. The alternate low resolution grid occupancy mapping demonstrated a significant reduction in probe overhead and memory requirements compared to BMP.

Greedy-BoundedCompass forwarding has application in existing geographic routing protocols. BSR along with the low resolution grid occupancy mapping system is a promising approach to geographic routing with minimal local information maintained for routing around local minima. Future research will focus on refining the proposed grid occupancy mapping system and dealing with mobility.

Item ID: 15226
Item Type: Thesis (PhD)
Keywords: wireless network, routing, protocol, geographic routing, routing protocols
Related URLs:
Additional Information:

Publications arising from this thesis are available from the Related URLs field. The publications are:

Lemmon, Colin, Lui, Siu Man, and Lee, Ickjai (2009) Geographic forwarding and routing for ad-hoc wireless network: a survey. ISBN 978-1-4244-5209-5. Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDC In: 2009 Fifth International Joint Conference on INC, IMS and IDC, 25-27 August 2009, Seoul, Korea.

Lemmon, C and Musumeci, P., Boundary Mapping and Boundary State Routing (BSR) in Ad-Hoc Networks. IEEE Transactions on Mobile Computing, vol 7, 1, pp. 127-139, January 2008.

Date Deposited: 26 Jan 2011 23:37
FoR Codes: 08 INFORMATION AND COMPUTING SCIENCES > 0805 Distributed Computing > 080501 Distributed and Grid Systems @ 33%
08 INFORMATION AND COMPUTING SCIENCES > 0805 Distributed Computing > 080503 Networking and Communications @ 33%
08 INFORMATION AND COMPUTING SCIENCES > 0805 Distributed Computing > 080502 Mobile Technologies @ 34%
SEO Codes: 89 INFORMATION AND COMMUNICATION SERVICES > 8901 Communication Networks and Services > 890103 Mobile Data Networks and Services @ 100%
Downloads: Total: 420
Last 12 Months: 6
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page