Article Preview
TopIntroduction
A mobile ad hoc network (MANET) is a temporary network formed dynamically by wireless mobile hosts without a pre-setup infrastructure. Unlike in a traditional infrastructure-based wireless network where each host routes packets through an access point or a mobile router, in MANET each host routes the packets and communicates directly with its neighbors. MANET may be viewed as a general network model that is applicable to other emerging wireless network technologies such as wireless mesh networks and sensor networks.
Since MANET offers much flexibility than traditional wireless networks, its demand and potential applications have rapidly increased. It is excellent for highly dynamic situations such as military operations, disaster recovery including its healthcare needs, and ad-hoc teleconferencing. In the near future it may also be applied to vehicular ad-hoc networks and countless forms of social gatherings.
Growing along with the demand is the research challenges in designing efficient MANET protocols. There are several major factors to be considered. Firstly, as its demand is rapidly rising, so is the number of mobile hosts shared a MANET. Secondly, since MANET is designed to work without an existing network infrastructure, it needs to adapt dynamically to the changing network topology. Yet, the third critical factor to be considered is energy; mobile hosts usually rely on limited battery power. Thus, it is vital that a MANET protocol be scalable, energy efficient, dynamic, and self-organization/self-healing (Banerjee & Misra, 2002; Chen & Gerla, 2002; Pei, Gerla, Hong, & Chiang, 1999; Royer, 2004; Sivakumar, Sinha, & Bharghavan, 1999).
To address the scalability issue, this paper focuses on hierarchical routing, as hierarchy makes a routing protocol scalable. We investigate hierarchical routing based on the idea of dominating sets (DS). Minimum connected dominating sets (MCDS) and its variations have been used for hierarchical routing in MANET such that nodes in a DS form a virtual backbone and are responsible for routing packets through the entire network. Both DS and MCDS and their use in MANET routing will be described further in the Related Studies section.
To address the energy efficiency issue, we study energy awareness of these dominating-set based routing algorithms. Most existing works have mainly focused on heuristics for finding a small dominating set (since MCDS is NP-complete) and evaluating the size of dominating sets and the message costs. We incorporate IEEE 802.11 medium access control (MAC) schemes, with power saving mode (PSM) (IEEE, 1999), into these routing algorithms and assess them in terms network lifetime, throughput, and delay.
To address the dynamic issue, we propose a new algorithm, Dynamic Leader Set Generation (DLSG), which dynamically selects leader nodes based on traffic demand, locality, and residual energy level. As a result, the network lifetime is greatly increased.
Finally, to address the self-organization, self-healing issue, the new algorithm DLSG not only dynamically selects new leaders; it further follows a threshold mechanism, such that a leader node may de-select itself when its energy level falls below some threshold. The network therefore reorganizes itself around new leaders. Furthermore, a simple self-healing mechanism is also suggested.
The rest of the paper is organized as follows. Firstly we will give a broad overview of related work on energy efficient routing. We then present our proposed algorithm DSLG. Performance evaluation of our algorithm is also discussed. Lastly, we offer concluding remarks.