Research Article
An Optimized Version of Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks
St. Marys School of Management Studies, Chennai-119, India
S.K Srivatsa
St. Josephs College of Engineering, Chennai-119,India
Minimizing energy consumption is an important challenge in mobile networking. The wireless network interface is often a devices single largest consumer of power. Since the network interface may often be idle, turning the radio off when not in use could save this power. In practice, however, this approach is not straightforward. A node must arrange to turn its radio on not just to receive packets addressed to it, but also to participate in any higher-level routing and control protocols. Coordination of power saving with routing in ad hoc wireless networks is the subject of this study.
A good power-saving coordination technique for wireless ad-hoc networks ought to have the following characteristics. It should allow as many nodes as possible to turn their radio receivers off most of the time, since even an idle receiver circuit can consume almost as much energy as an active transmitter. On the other hand, it should forward packets between any source and destination with minimally more delays than if all nodes were awake. This implies that enough nodes must stay awake to form a connected backbone. Furthermore, the backbone formed by the awake nodes should provide about as much total capacity as the original network, since otherwise congestion may increase. This means that paths that could operate without interference in the original network should be represented in the backbone. For example, Fig. 1 sho\Vll a topology that violates this principle.
Fig. 1: | A connected backbone does not necessarily preserve capacity |
In connected topology, black nodes are coordinators. Packets between node 3 and 4 may contend for bandwidth with packets between nodes 1 and 2. On the other hand, if node 5 were a coordinator, no contention would occur.
Each node in the network makes periodic, local decisions on whether to sleep or stay awake as a coordinator and participate in the forwarding backbone topology. To preserve capacity, a node decides to volrmteer to be a coordinator if it discovers that two of its neighbors cannot commmricate with each other directly or through an existing coordinator. To keep the number of redrmdant coordinators low and rotate this role amongst all nodes, each node delays annormcing its willingness with a random delay that takes two factors into accormt viz., the amormt of remaining battery energy and the number of pairs of neighbors it can connect together. This combination ensures, with high probability, a capacity preserving connected backbone at any point of time. The nodes are assumed to consume energy at about the same rate. The power saving technique does all this using only local information, consequently scaling well with the number of nodes.
Related work: The geography informed energy conservation method (ns: Notes and Documents. www.isi.edu/vint/nsnam) uses the nodes geographic location to divide the world into fixed square grids. The information of each grid stays constant, regardless of node density.Nodes within grid switch between sleeping and listening, with the guarantee that one node in each grid must stay in the listening mode. However, the technique used in this study will broadcast messages to discover and direct changes in the network topology. Also non- coordinator nodes are ready to receive the packets when operating in power saving mode.
In reducing power consumption of network interface in hand-held devices, the setting of on/off periods based on application hints reduces both power and delay. The technique discussed in this paper assumes the presence of polling mechanism which provides potential work in concert with application hints. Such hints would apply only to sleeping nodes and not coordinators.
In general, the basic area that a path with many short hops is sometimes more energy-efficient than one with a few long hops. This is applicable to a network with variable power radios and knowledge of positions of nodes.
Design: The network adaptively elects Coordinators from all nodes and the coordinators stay awake continuously and perform multi-hop packet routing within the ad hoc network, while other nodes remain in power-saving mode and periodically check if they should wake up and become a coordinator.
This can be achieved in the four ways.
• | The network ensures that enough coordinators are elected so that every node is in radio range of at least one coordinator. |
• | The network rotates the coordinators in order to ensure that all nodes share the task of providing global connectivity roughly equally. |
• | The network attempts to minimize the number o fnodes elected as coordinators, thereby increasing network lifetime, but without suffering a significant loss of capacity or an increase in latency. |
• | Finally, the network elects coordinators using only local information in decentralized mllilller. Each node only consults state stored in local routing tables during the election process |
Fig. 2: | The power saving protocol |
In the network, each node periodically broadcasts HELLO messages that contain the nodes status (i.e., whether or not the node is a coordinator), its current coordinators and its current neighbors. These HELLO messages and consequently the states maintained are similar to those of proactive ad hoc routing protocols (e.g ., geographic routing (Parnas et oZ.. 1998) or DSDV (Meug and June. 1998). Each node maintains only a small ammmt of additional state-its coordinators and coordinators of neighbors-in addition to a list of neighbors normally fmmd in the routing table. In Fig. 2 the power saving protocol operates rmder the routing layer and above the MAC and physical layers.
The routing layer uses information of the power saving features of MAC layer. It nms above the link and MAC layers and interacts with the routing protocol. This structuring allows taking advantage of power-saving features of the link layer protocol, while still being able to affect the routing process. For example, non-coordinator nodes can periodically turn on their radios and listen (e.g., 802.11 power-saving mode (Benjie et oZ.. 1999) or poll (as in LPMAC (Shepard, 1996) for their packets. It has a feature of modem power-saving MAC layers, wherein if a node has been asleep for a while, packets destined for it are not lost but are buffered at an upstream neighbor. When the node awakens, it can retrieve these packets from the buffering node, typically a coordinator. It also requires a modification to the route lookup process at each node-at any time, only those entries in a nodes routing table that correspond to cmently active coordinators can be used as valid next-hops (nnless the next hop is the destination itself).
A node switches state from time to time between being a coordinator and being a non-coordinator. A node includes its current state in its HELLO messages. The following sections describe how a node decides that it should annmmce that it is a coordinator and how it decides that it should withdraw from being a coordinator.
COORDINATOR ANNOUNCEMENT
Periodically, a non-coordinator node determines if it should become a coordinator or not. The following coordinator eligibility rule in power saving method ensures that the entire network is covered with enough coordinators.
Coordinator eligibility rule: If two neighbors of a non- coordinator node cannot reach each other either directly or via one or two coordinators, the node should become a coordinator.
While this election algorithm does not yield the minimum number of coordinators required to merely maintain connectedness, it forms a network that roughly contains a coordinator in every populated radio range in the entire network topology. Since packets will be routed through coordinators, this topology ought to yield good capacity.
Annoncement contention occurs where multiple nodes discover the lack of a coordinator at the same time and all decide to become a coordinator. We resolve contention by delaying coordinator annmmcements with a randomized back-off delay. Each node chooses a delay value and delays the HELLO message that annmmces the nodes volrmteering as a coordinator for that amormt of time. If at the end of the delay, the node has not received any HELLO messages from other potential coordinators, it sends the HELLO message. Otherwise, it reevaluates its eligibility based on any HELLO messages received and makes its annormcement if and only if the eligibility rule still holds.
Let us consider that all nodes have roughly equal energy, which implies that only topology can play a role in deciding which node becomes coordinator. Let N, be the number of neighbors of node i and let C, be the number of additional pairs of nodes among these neighbors that would be connected if i were to become a coordinator and forward packets.
we call
The utility of node i. If the nodes with high C, become coordinators, fewer coordinators in total may be needed in order to make sure energy node can talk to a coordinator; thus a node with a high C, can volrmteer more quickly than one with smaller Ci.
If there are multiple nodes within radio range that all have the same utility, we need to ensure that not too many of them all become coordinators. This is because such coordinators are redrmdant-they do not increase system capacity, but simply drain power. If the potential coordinators make their decision simultaneously, they may all decide to become coordinators. If, on the other hand, they decide one at a time, only the first few will become coordinators and the rest will notice that there are already enough coordinators and go back to sleep.
To handle this, by choosing the delay for each node randomly over an interval proportional toN, x T, where T is the delay over the wireless link. If all the nodes have equal energy, then the delay Tis given by
(1) |
The randomization is achieved by picking R uriformly at random from the interval.
Let us consider the case when nodes all have unequal energy left in their batteries. The amormt of energy scaled to the maximum amormt of energy that the nodes can have. Let Er denote the amormt of energy at a node that still remains and Em be the maximum amormt of energy available at the same node. Then the decreasing function is (Er/Em). Putting this in the Eq. 1. then
(2) |
The first term does not have a random component; thus if a node is nmning low on energy, its propensity to become a volrmteer is guaranteed to diminish relative to other nodes in the neighborhood with similar neighbors.
In a network with rmiform density and energy, our election algorithm rotates coordinators among all nodes of the network. It achieves fairness because the likelihood of becoming a coordinator falls as a coordinator uses up its battery.
COORDINATOR WITHDRAWAL
Each coordinator periodically checks if it should withdraw as a coordinator. A node should withdraw if every pair of its neighbors can reach each other directly or via some other coordinators. However, in order to also ensure fairness, after a node has been a coordinator for some period of time, it withdraws if every pair neighbor nodes can reach each other via some other neighbors, even if those neighbors are not currently coordinators. This rule gives other neighbors a chance to become coordinators.
To prevent temporary loss of connectivity between a coordinators withdrawal message and the mormcement from a new coordinator, a node continues to serve as a coordinator for a short period of time even after annmmcing its withdrawal. This grace period allows the routing protocol to continue to use the old coordinator rmtil a new coordinator is elected.
COORDINATOR ELECTION
• | The coordinator election algoritlnn uses two criteria for electing coordinators. The source and destination nodes of each flow need to constantly send and receive packets, they do not operate in power saving mode. Thus, they automatically become coordinators. |
• | The routing algoritlnn can readily detect that a coordinator has left the region through MAC layer failure. The election algoritlnn may not react fast enough to elect new coordinator. In the worst case, nodes must wait rmtil the old coordinator information has expired before a new coordinator can be elected. Even if the coordinator does not exist, a non-coordinator node annormces itself as a coordinator, if it has received a large number of packets to route in the recent past. If this coordinator turns out to be redrmdant, the coordinator withdrawal algoritlnn will force the node to withdraw itself as a coordinator soon after. |
POWER SAVING MODE
The power saving protocol determines when to turn a nodes radio on or off. It depends on the low level MAC layer to support power saving frmctions, such as buffering packets for sleeping nodes. We have implemented the algoritlnn on top of the MAC and physical layers with ad hoc power saving support (Benjie et oZ.. 1999).
802.11 ad hoc power-saving mode uses periodic beacons to synchronize nodes in the network. Beacon packets contain timestamps that synchronize nodes clocks. A beacon period starts with an Ad hoc Traffic Indication Message Window (ATIM window), during which all nodes are listening and pending traffic transmissions are advertised. A node that receives and acknowledges an advertisement for mricast or broadcast traffic directed to it must stay on for the rest of the beacon period. Otherwise, it can turn itself off at the end of the ATIM window, rmtil the beginning of the next beacon period. After the ATIM window, advertised traffic is transmitted. Since traffic cannot be transmitted during the ATIM window, the available channel capacity is reduced.
When the 802.11 MAC layer is asked to send a packet, it may or may not be able to send it immediately, depending on which ATIMs have been sent and acknowledged in the immediately preceding or cment, ATIM window. If the packet arrives at the MAC during the ATIM window, or if the advertisement for the packet has not been acknowledged, it needs to be buffered. In our implementation, we buffer packets for two beacon periods. Packets that have not been transmitted after two beacon periods are dropped.
The beacon period and ATIM window size affect routing performance greatly (Perkins and Landon. 1994). While using a small ATIM window may improve energy savings, there may not be enough time for all buffered packets to be advertised. Using an ATIM window that is too large not only decreases available channel utilization, it may also not leave enough room between the end of the ATIM window and the beginning of the next beacon period to transmit all advertised traffic.
IMPROVING POWER SAVING MODE
Using this technique on top of 802.11 ad hoc power saving mode can improve routing throughput and packet delivery latency. Since coordinators do not operate in power saving mode, packet routed between coordinators do not need to be advertised or delayed. To further take advantage of the synergy, the following modification can be made in the technique.
No advertisement for packet between coordinators: Packets routed between coordinators are marked and the MAC layer still needs to buffer these packets if they arrive during the ATIM window, it does not send traffic advertisements for them. To ensure that MAC layer uses a bit in the MAC header of each packet, it notifies neighbors of its power saving status. When a node withdraws as a coordinator, advertisements for traffic to that node will be sent during the next ATIM window. This optimization allows the ATIM window to be reduced without hurting throughput.
Individual advertisement of each broadcast message: A node only needs to send one broadcast advertisement even if it has more than one broadcast message to send.This is because once a node hears an advertisement for a broadcast message. It stays up for the entire duration of the beacon period. For example, if a node receives five broadcast advertisement, no mricast advertisement and then five broadcast message after the ATIM window, it can safely turn itself off.
New advertisement traffic window: If a node receives a unicast advertisement, it must remain on for the rest of the beacon period. In an ad hoc network, packet routed via non-coordinator nodes is rare. To take advantage of this, a new advertised traffic window is introduced in MAC layer. It starts at the beginning of the beacon period and extends beyond the end of the ATIM window. Outside the ATIM window but inside the advertised traffic window, advertised packets and packets to coordinators can be transmitted. Outside the advertised traffic window, however, only packets between coordinators can be transmitted. This allows a node in power saving mode to turn itself off at the end of the advertised traffic window rmtil the next beacon period.
These three modifications allow each node to use a long beacon period and a short ATIM window. The short ATIM window improves channel utilization, while the long beacon period increases the fraction of time a non coordinator node can remain asleep.
PERFORMANCE EVALUATION
To measure the effectiveness of the power saving method, we simulate on various static and mobile topologies on their energy consumption, network lifetime, etc.
Using NS-2 simulator (CMU), we simulate various node densities with different fraction of energy remaining in different nodes.
Figure 3 shows coordinator density as a frmction of node density. Coordinator density is computed from the average number of coordinators elected by the simulated five mobile stations over 300 sec.
Fig. 3: | Ideal and actual coordinator density as a fonction of node density |
Fig. 4: | Energy consumption |
The nodes becomes coordinator not only because they are sources or destinations, they reside at the left and right edges of simulation area. The numbers in the figure are only slightly less than the number of coordinators had there been no sources or sinks. Points on the ideal curve in Fig.3 are computed using the ideal number of coordinators with equal area distance.
The power saving method elects more coordinators than are needed. There are two reasons for this. First, non-rmiform density often causes more nodes to become coordinators. Second, to rotate coordinators among all nodes, the optimal set of coordinators may not always be selected.
ENERGY CONSUMPTION
The potential for savings depends on node density, since the fraction of sleeping nodes depends on the number of nodes per radio coverage area. The energy saving also depends on a radios power consumption in sleep mode and the amormt of time that sleeping nodes must turn on their receivers to listen to the messages.
Figure 4 shows the fraction of energy remaining at each node after the simulation. From the result, we find the power saving method provides a considerable amormt of energy savings over 802.11 power saving mode.
802.11 power saving mode does not provide any energy savings at all. We also find out that as density increases, a smaller fraction of the nodes are elected coordinators. Consequently, we expect energy savings to increase. In practice, however, energy saving does not increase as much. To rmderstand why, we estimate the amormt of energy used in our power saving method based on as estimate of the average fraction of time a node must nm its radio in idle mode.
This study presents a distributed coordination technique for multi-hop ad hoc networks that reduces energy consumption without significantly diminishing the capacity or connectivity of the network. In ad hoc network, coordinator is elected from all nodes and it rotates amongst them in time. The coordinator may stay awake and perform multi-hop packet routing within the ad hoc network, while other nodes remain in power-saving mode and periodically check if they should awaken and become a coordinator.
Each node uses a random back off to decide whether to become a coordinator. This delay is a frmction of the number of other nodes in the neighborhood that can be bridged using this node and the ammmt of energy it has remains the same. The implementation of the power saving technique periodically wakes up the nodes and makes them listen the advertisements and this will increase the cost. This warrants investigation into a more robust and efficient power saving technique in J\1AC layer that minimizes the ammmt of time each node spends in power saving mode. We have taken the nodes which occupy equal distances. In practice, the nodes are not in equal positions. This increases the number of coordinators. Such case needs future exploration to reduce the number of coordinators and energy consumption.