A resource-efficient and scalable wireless mesh routing protocol

By binding logic addresses to the network topology, routing can be carried out without going through route discovery. This eliminates the initial route discovery latency, saves storage space otherwise needed for routing table, and reduces the communication overhead and energy consumption. In this paper, an adaptive block addressing (ABA) scheme is first introduced for logic address assignment as well as network auto-configuration purpose. The scheme takes into account the actual network topology and thus is fully topology-adaptive. Then a distributed link state (DLS) scheme is further proposed and put on top of the block addressing scheme to improve the quality of routes, in terms of hop count or other routing cost metrics used, robustness, and load balancing. The network topology reflected in logic addresses is used as a guideline to tell towards which direction (rather than next hop) a packet should be relayed. The next hop is derived from each relaying node's local link state table. The routing scheme, named as topology-guided DLS (TDLS) as a whole, scales well with regard to various performance metrics. The ability of TDLS to provide multiple paths also precludes the need for explicit route repair, which is the most complicated part in many wireless routing protocols. While this paper targets low rate wireless mesh personal area networks (LR-WMPANs), including wireless mesh sensor networks (WMSNs), the TDLS itself is a general scheme and can be applied to other non-mobile wireless mesh networks. (c) 2006 Elsevier B.V. All rights reserved.