A Multiple-Layer Self-Organizing Wireless Network

Hyunjeong LEE
Chung-Chieh LEE

IEICE TRANSACTIONS on Information and Systems   Vol.E89-D    No.5    pp.1622-1632
Publication Date: 2006/05/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e89-d.5.1622
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Challenges in Ad-hoc and Multi-hop Wireless Communications)
multi-hop network,  routing,  self-organizing network,  packet scheduling,  load balancing,  

Full Text: PDF>>
Buy this Article

A self-organizing wireless network has to deal with reliability and congestion problems when the network size increases. In order to alleviate such problems, we designed and analyzed protocols and algorithms for a reliable and efficient multiple-layer self-organizing wireless network architecture. Each layer uses a high-power root node to supervise the self-organizing functions, to capture and maintain the physical topology, and to serve as the root of the hierarchical routing topology of the layer. We consider the problem of adding a new root with its own rooted spanning tree to the network. Based on minimum-depth and minimum-load metrics, we present efficient algorithms that achieve optimum selection of root(s). We then exploit layer scheduling algorithms that adapt to network load fluctuations in order to optimize the performance. For optimality we consider a load balancing objective and a minimum delay objective respectively. The former attempts to optimize the overall network performance while the latter strives to optimize the per-message performance. Four algorithms are presented and simulations were used to evaluate and compare their performance. We show that the presented algorithms have superior performance in terms of data throughput and/or message delay, compared to a heuristic approach that does not account for network load fluctuations.