Distance Routing Effect Algorithm For Mobility Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

The Location-Aided Routing protocol exploits location information to limit the scope of route request flood employed in protocols such as AODV and DSR. Such location information can be obtained through GPS (Global Positioning System). LAR limits the search for a route to the so-called request zone, determined based on the expected location of the destination node at the time of route discovery. Distance Routing Effect Algorithm for Mobility

DREAM (Distance Routing Effect Algorithm for Mobility) is a routing protocol for ad hoc networks built around two novel observations. One, called the distance effect, uses the fact that the greater the distance separating two nodes, the slower they appear to be moving with respect to each other. Accordingly, the location information in routing tables can be updated as a function of the distance separating nodes without compromising the routing accuracy. The second idea is that of triggering the sending of location updates by the moving nodes autonomously, based only on a node's mobility rate. Intuitively, it is clear that in a directional routing algorithm, routing information about the slower moving nodes needs to be updated less frequently than that about highly mobile nodes. In this way each node can optimize the frequency at which it sends updates to the networks and correspondingly reduce the bandwidth and energy used, leading to a fully distributed and self-optimizing system. Based on these routing tables, the proposed directional algorithm sends messages in the "recorded direction" of the destination node, guaranteeing delivery by following the direction with a given probability. Relative Distance Micro-Discovery Ad-hoc Routing

The RDMAR (Relative Distance Micro-discovery Ad Hoc Routing) routing protocol is a highly adaptive, efficient and scaleable routing protocol. It is well-suited in large mobile networks whose rate of topological changes is moderate. A key concept in its design is that protocol reaction to link failures is typically localized to a very small region of the network near the change. This desirable behavior is achieved through the use of a novel mechanism for route discovery, called Relative Distance Micro-discovery (RDM). The concept behind RDM is that a query flood can be localized by knowing the relative distance (RD) between two terminals. To accomplish this, every time a route search between the two terminals is triggered, an iterative algorithm calculates an estimate of their RD, given an average nodal mobility and information about the elapsed time since they last communicated and their previous RD. Based on the newly calculated RD, the query flood is then localized to a limited region of the network centered at the source node of the route discovery and with maximum propagation radius that equals to the estimated relative distance. This ability to localize query flooding into a limited area of the network serves to minimize routing overhead and overall network congestion.

In RDMAR, calls are routed between the stations of the network by using routing tables which are stored at each station of the network; each node is treated as a host as well as a store-and-forward node. Each routing table lists all reachable destinations, wherein for each destination i, additional routing information is also maintained. This includes: the "Default Router" field that indicates the next hop node through which the current node can reach i, the "RD" field which shows an estimate of the relative distance (in hops) between the node and i, the "Time_Last_Update" (TLU) field that indicates the time since the node last received routing information for i, a "RT_Timeout" field which records the remaining amount of time before the route is considered invalid, and a "Route Flag" field which declares whether the route to i is active.

RDMAR comprises of two main algorithms:

• Route Discovery - When an incoming call arrives at node i for destination node j and there is no route available, i initiates a route discovery phase. Here, i has two options; either to flood the network with a route query in which case the route query packets are broadcast into the whole network, or instead, to limit the discovery in a smaller region of the network, if some kind of location prediction model for j can be established. The former case is straightforward. In the latter case, the source of the route discovery, i, refers to its routing table in order to retrieve information on its previous relative distance with j and the time elapsed since i last received routing information for j. Let us designate this time as tmotion. Based on this information and assuming a moderate velocity, Micro Velocity, and a moderate transmission range, Micro_Range, node i is then able to estimate its new relative distance to destination node j in terms of actual number of hops. To accomplish this, node i calculates the distance offset of DST (DST_Offset) during tmotion, and "adjusts" the result onto their previous relative distance (RDM_Radius).

• Route Maintenance - An intermediate node i, upon reception of a data packet, first processes the routing header and then forwards the packet to the next hop. In addition, node i sends an explicit message to examine whether a bi-directional link can be established with the previous node. RDMAR, therefore, does not assume bidirectional links but in contrast nodes exercise the possibility of having bi-directional links. In this way, nodes that forward a data packet will always have routing information to send the future acknowledgement back to the source. If node i is unable to forward the packet because there is no route available or a forwarding error occurs along the data path as a result of a link or node failure, i may attempt a number of additional re-transmissions of the same data packet, up to a maximum number of retries. However, if the failure persists, node i initiates a Route Discovery procedure.

3.7.3. Hybrid Routing Protocols Zone Routing Protocol

Zone Routing Protocol (ZRP) [87] is a hybrid example of reactive and proactive schemes. It limits the scope of the proactive procedure only to the node's local neighborhood, while the search throughout the network, although it is global, can be performed efficiently by querying selected nodes in the network, as opposed to querying all the network nodes. In ZRP, a node proactively maintains routes to destinations within a local neighborhood, which is referred to as a routing zone and is defined as a collection of nodes whose minimum distance in hops from the node in question is no greater than a parameter referred to as zone radius. Each node maintains its zone radius and there is an overlap of neighboring zones. The construction of a routing zone requires a node to first know who its neighbors are. A neighbor is defined as a node that can communicate directly with the node in question and is discovered through a MAC level Neighbor discovery protocol (NDP). The ZRP maintains routing zones through a proactive component called the Intra-zone routing protocol (IARP) which is implemented as a modified distance vector scheme. On the other hand, the Inter-zone routing protocol (IERP) is responsible for acquiring routes to destinations that are located beyond the routing zone. The IERP uses a query-response mechanism to discover routes on demand. The IERP is distinguished from the standard flooding algorithm by exploiting the structure of the routing zone, through a process known as border casting. The ZRP provides this service through a component called Border resolution protocol (BRP). The network layer triggers an IERP route query when a data packet is to be sent to a destination that does not lie within its routing zone. The source generates a route query packet, which is uniquely identified by a combination of the source node's ID and request number. The query is then broadcast to all the source's peripheral nodes. Upon receipt of a route query packet, a node adds its ID to the query. The sequence of recorded node Ids specifies an accumulated route from the source to the current routing zone. If the destination does not appear in the node's routing zone, the node border casts the query to its peripheral nodes. If the destination is a member of the routing zone, a route reply is sent back to the source, along the path specified by reversing the accumulated route. A node will discard any route query packet for a query that it has previously encountered. An important feature of this route discovery process is that a single route query can return multiple route replies. The quality of these returned routes can be determined based on some metric. The best route can be selected based on the relative quality of the route. Fisheye State Routing (FSR)

The Fisheye State Routing (FSR) protocol [88] introduces the notion of multilevel fisheye scope to reduce routing update overhead in large networks. Nodes exchange link state entries with their neighbors with a frequency which depends on distance to destination.

From link state entries, nodes construct the topology map of the entire network and compute optimal routes. FSR tries to improve the scalability of a routing protocol by putting most effort into gathering data on the topology information that is most likely to be needed soon. Assuming that nearby changes to the network topology are those most likely to matter, FSR tries to focus its view of the network so that nearby changes are seen with the highest resolution in time and changes at distant nodes are observed with a lower resolution and less frequently. It is possible to think the FSR as blurring the sharp boundary defined in the network model used by ZRP. Landmark Routing (LANMAR) for MANET with Group Mobility

Landmark Ad Hoc Routing (LANMAR) [89] combines the features of FSR and Landmark routing. The key novelty is the use of landmarks for each set of nodes which move as a group (viz., a group of soldiers in a battlefield) in order to reduce routing update overhead. Like in FSR, nodes exchange link state only with their neighbors. Routes within Fisheye scope are accurate, while routes to remote groups of nodes are "summarized" by the corresponding landmarks. A packet directed to a remote destination initially aims at the Landmark; as it gets closer to destination it eventually switches to the accurate route provided by Fisheye. In the original wired landmark scheme [Tsuchiya 1988], the predefined hierarchical address of each node reflects its position within the hierarchy and helps find a route to it. Each node knows the routes to all the nodes within it hierarchical partition. Moreover, each node knows the routes to various "landmarks" at different hierarchical levels. Packet forwarding is consistent with the landmark hierarchy and the path is gradually refined from top-level hierarchy to lower levels as a packet approaches the destination.

LANMAR borrows from [90] the notion of landmarks to keep track of logical subnets. A subnet consists of members which have a commonality of interests and are likely to move as a "group" (viz., soldiers in the battlefield, or a group of students from the same class). A "landmark" node is elected in each subnet. The routing scheme itself is modified version of FSR. The main difference is that the FSR routing table contains "all" nodes in the network, while the LANMAR routing table includes only the nodes within the scope and the landmark nodes. This feature greatly improves scalability by reducing routing table size and update traffic overhead. When a node needs to relay a packet, if the destination is within its neighbor scope, the address is found in the routing table and the packet is forwarded directly.

Otherwise, the logical subnet field of the destination is searched and the packet is routed towards the landmark for that logical subnet. The packet however does not need to pass through the landmark. Rather, once the packet gets within the scope of the destination, it is routed to it directly.

The routing update exchange in LANMAR routing is similar to FSR. Each node periodically exchanges topology information with its immediate neighbors. In each update, the node sends entries within its fisheye scope. It also piggy-backs a distance vector with size equal to the number of logical subnets and thus landmark nodes. Through this exchange process, the table entries with larger sequence numbers replace the ones with smaller sequence numbers.

3.7.4. Other Routing Protocols

There is plenty of routing protocol proposals for mobile ad hoc networks. Our discussion here is far from being exhaustive. Below we will describe some other routing protocols which employ different optimization criteria as the ones we have previously described. Signal Stability Routing

Another on-demand protocol is the Signal Stability-Based Adaptive Routing protocol (SSR) [91]. Unlike the algorithms described so far, SSR selects routes based on the signal strength (weak or strong) between nodes and a node's location stability. The signal strengths of neighboring nodes are obtained by periodic beacons from the link layer of each neighboring node. This route selection criterion of SSR has the effect of choosing routes that have "stronger" connectivity. Power Aware Routing

In this protocol, power-aware metrics [92, 93] are used for determining routes in wireless ad hoc networks. It has been shown that using these metrics in a shortest- cost routing algorithm reduces the cost/packet of routing packets by 5 - 30 percent over shortest-hop routing (this cost reduction is on top of a 40-70 percent reduction in energy consumption over the MAC layer protocol used). Furthermore, using these new metrics ensures that mean time to node failure is increased significantly, but packet delays do not increase. A recent work concentrates on selecting a route based the traffic and congestion characteristics in the network. Associativity-Based Routing

This is a totally different approach in mobile routing. The Associativity-Based Routing (ABR) protocol is free from loops, deadlock, and packet duplicates, and defines a new routing metric for ad hoc mobile networks. In ABR, a route is selected based on a metric that is known as the degree of association stability. Each node periodically generates a beacon to signify its existence. When received by neighboring nodes, this beacon causes their associativity tables to be updated. For each beacon received, the associativity tick of the current node with respect to the beaconing node is incremented. Association stability is defined by connection stability of one node with respect to another node over time and space.

A high (low) degree of association stability may indicate a low (high) state of node mobility.

Associativity ticks are reset when the neighbors of a node or the node itself move out of proximity. A fundamental objective of ABR is to derive longer-lived routes for ad hoc networks. The three phases of ABR are:

• Route discovery,

• Route reconstruction (RRC),

• Route deletion.

The route discovery phase is accomplished by a broadcast query and await-reply (BQ- REPLY) cycle. A node desiring a route broadcasts a BQ message in search of mobiles that have a route to the destination. All nodes receiving the query (that are not the destination) append their addresses and their associativity ticks with their neighbors along with QoS information to the query packet. A successor node erases its upstream node neighbors' associativity tick entries and retains only the entry concerned with itself and its upstream node. In this way, each resultant packet arriving at the destination contains the Associativity ticks of the nodes along the route to the destination. The destination is then able to select the best route by examining the associativity ticks along each of the paths. When multiple paths have the same overall degree of association stability, the route with the minimum number of hops is selected. The destination then sends a REPLY packet back to the source along this path. Nodes propagating the REPLY mark their routes as valid. All other routes remain inactive, and the possibility of duplicate packets arriving at the destination is avoided. RRC may consist of partial route discovery, invalid route erasure, valid route updates, and new route discovery, depending on which node(s) along the route move. Movement by the source results in a new BQ-REPLY process. The RN message is a route notification used to erase the route entries associated with downstream nodes. When the destination moves, the immediate upstream node erases its route and determines if the node is still reachable by a localized query (LQ [H]) process, where H refers to the hop count from the upstream node to the destination. If the destination receives the LQ packet, it REPLYs with the best partial route; otherwise, the initiating node times out and the process backtracks to the next upstream node. Here, a RN [0] message is sent to the next upstream node to erase the invalid route and inform this node that it should invoke the LQ [H] process. If this process results in Back tracking more than halfway to the source, the LQ process is discontinued and a new BQ process is initiated at the source

3.8 Multicast Routing Protocols

Multicasting is the process of sending packets from a transmitter to multiple destinations identified by a single address. As with their wired counterparts, multicasting in MANET is also a hard task to accomplish, and it is even harder in the MANET case since the physical topology changes quite frequently. Therefore, multicast protocols designed for a MANET have to take topological changes into consideration. In this section, we discuss two multicast routing protocols, namely AODV Multicasting and ODMRP, proposed within the MANET [MANET] working group at the IETF [IETF].

3.8.1. AODV Multicasting (MAODV)

The AODV multicast algorithm [94] uses similar RREQ and RREP messages as in unicast operation. The nodes join the multicast group on-demand, and a multicast tree is created in the process. The tree consists of the group members and nodes connected to the group members. This enables a recipient host to join a multicast group even if it is more than one hop away from a multicast group member. The unicast operation of the protocol also benefits from the information that is gathered while discovering routes for multicast traffic. This cuts down the signaling traffic in the network.

3.8.2. On-Demand Multicast Routing Protocol (ODMRP)

ODMRP (On-Demand Multicast Routing Protocol) is a mesh-based, instead of tree-based, multicast protocol that provides richer connectivity among multicast members. By building a mesh and supplying multiple routes, multicast packets can be delivered to destinations in the face of node movements and topology changes. In addition, the drawbacks of multicast trees in mobile wireless networks (e.g., intermittent connectivity, frequent tree reconfiguration, traffic concentration, etc.) are avoided. To establish a mesh for each multicast group, ODMRP uses the concept of forwarding group [95]. The forwarding group is a set of nodes responsible for forwarding multicast data on shortest paths between any member pairs. ODMRP also applies on-demand routing techniques to avoid channel overhead and improve scalability. No explicit control message is required to leave a group.

3.9. Medium Access Control (MAC) Protocols Issues

Maybe not as much as ad hoc routing protocols, but MAC protocols have also been receiving attention from the research community. There are still many issues that need to be addressed in order to design an efficient MAC protocol to be used in a wireless ad hoc network environment [94]. There are several MAC protocols which can be employed for multi-hop ad hoc networking including IEEE 802.11, Bluetooth [Bluetooth] and HiperLAN. Usually, the IEEE 802.11 standard is the platform employed to experiment multi-hop networking. However, it does not support multi-hop as is.

3.9.1. Hidden Terminal Problem

In CSMA, every station senses the carrier before transmitting, and if it detects carrier then the transmission is deferred. Carrier sense attempts to avoid collisions by testing the signal strength in the vicinity of the transmitter. However, collisions occur at the receiver, not the transmitter; i.e., it is the presence of two or more interfering signals at the receiver that constitutes a collision. Since the receiver and the sender are typically not co-located, carrier sense does not provide the appropriate information for collision avoidance.

3.9.2. Reliability

Wireless links are prone to errors. Actually, packet error rates of wireless mediums are much higher than that of their wired counterparts. As a result, some protocols - which were originally designed to work in wired world - suffer performance degradation when operating in a wireless environment. A classic example of this problem is TCP (which has been designed and fine-tuned for wired networks) that assumes transmission timer expiration as an indication of network congestion. This event triggers the execution of TCP congestion control mechanisms which ultimately decreases the transmission rate aiming at reducing the network congestion. As a matter of fact, this is often true in wired environments since wired media are usually very reliable. However, in wireless environment this is often not the case. Due to effects such as multipath fading, interference, shadowing, distance between transmitter and receiver, etc., packet losses occur every now and then. As a result, when a packet loss takes place in a communication using TCP, it erroneously assumes that the loss was due to congestion and enters its congestion control mechanisms. There have been some proposals to cope up with this TCP behavior in a MANET.

As for the MAC protocol issues, a common approach to reduce packet loss rates experienced by upper layers is to introduce acknowledgment (ACK) packets. Returning to our earlier example of Figure 16, whenever node B received a packet from node A, node B sends an ACK packet to A. In case node A fails to receive the ACK from B, it will retransmit the packet. This approached is adopted in many protocols. As an example, the IEEE 802.11 DCF (Distributed Coordination Function) uses RTS-CTS to avoid the hidden terminal problem and ACK to achieve reliability.

3.9.3. Collision Avoidance

The radios used in the wireless mobile nodes employed in wireless communications are half-duplex. This is to say that these radios are not able to transmit and receive at the same and, thus, collision detection is not possible. To minimize collisions, wireless MAC protocols, such as CSMA/CA, often use collision avoidance techniques in conjunction with a carrier sense (be it physical or virtual) mechanism. Carrier sense is the mechanism whereby nodes wishing to transmit data first have to check whether the medium is idle or busy. The idea is that a station cannot transmit until the channel is idle. Collision avoidance is implemented by mandating that, when the channel is sensed idle, the node has to wait for a randomly chosen duration before attempting to transmit. This mechanism drastically decreases the probability that more than one node attempts to transmit at the same time, hence, avoiding collision. Of course there will be cases where more than one node initiates their transmission at the same time. In these cases, transmissions are corrupted and the corresponding nodes retry later on.

3.9.4. Congestion Avoidance

Congestion avoidance is another aspect of fundamental importance in wireless MAC protocols. In IEEE 802.11 DCF, when a node detects the medium to be idle, it chooses a back off interval between [0, CW], where CW is called contention window which usually has a minimum (CW_min) and maximum value (CW_min). The idea is that the node will count down the back off interval and when it reaches zero the node can transmit the RTS. In case the medium becomes busy while the node is still counting down the back off interval, the countdown process is suspended.

3.9.5. Congestion Control

As it has already mentioned earlier, the number of nodes attempting to transmit simultaneously may change with time. Therefore, some mechanism to manage congestion is needed. In IEEE 802.11 DCF, congestion control is achieved by dynamically choosing the contention window CW. When a node fails to receive CTS in response to its RTS, it assumes that congestion has built up and, as a consequence, doubles its contention window up to CW_max. When a node successfully completes its transmission, it restores its contention window to CW_min. This mechanism of dynamically controlling the contention window is called Binary Exponential Back-off, since the contention window increases exponentially with failed CTS.

Figure 3.8 - example of the back off mechanism in DCF

3.9.6. Energy Efficiency

Since many mobile hosts are operated by batteries, there is an increasing interest for MAC protocols that conserve energy. The current proposals in this area usually suggest turning the radio off when it is not needed. IEEE 802.11 has a Power Saving (PS) mode whereby the Access Point (AP) periodically transmits a beacon indicating which nodes have packets waiting for them. Each PS node wakes up periodically to receive the beacon transmitted by the AP. In case a node has a packet waiting for it, it sends a PS-POLL packet to the AP after waiting for a back off interval in [0, CW_min]. Upon receipt of the PS-POLL packet, the AP transmits the data to the requesting node. Using this procedure, it is possible to extend the battery life of mobile nodes for a longer period of time.

3.10 Power Management in IEEE 802.11

IEEE 802.11 [96] takes advantage of switching off the transceiver as a means to conserve energy. It employs two powers saving modes, "doze" (sleep) mode, and an "awake" (full power) mode. The standard describes two scenarios for power conservation. The first scenario addresses mobile nodes connected in an infrastructure type of network. Nodes in this type of network connect directly with an access point (AP). Nodes that want to go into doze mode and conserve energy must inform the AP of their intention so that the AP can buffer data frames addressed to the dozing node. Dozing nodes have to periodically wake up and stay awake. During the wake up period, the AP sends a traffic indication map (TIM) with every beacon that contains a list of nodes for which it has buffered data frames. For the above communication to occur, IEEE 802.11 provides a timing synchronization function. This function helps the nodes, especially the dozed nodes, to wake up on time slightly before the beacon and the TIM arrive.

The second scenario addresses an ad hoc network where no AP is present. In this scenario, power management is more of a challenge. In ad hoc networks, nodes need to coordinate among themselves to buffer frames for dozing nodes. Either they designate a specific node to buffer the frames or each node that has frames to send to a dozing node must buffer the frames until the next wake up period. Nodes that have buffered data frames announce the list of nodes for which they have buffered data in an ad hoc traffic indication map (ATIM) when all the power conserving nodes are awake during an ATIM window. In ad hoc networks, different nodes can generate a beacon. In this case all the nodes within the beacon's reception area wake up at the same time and stay awake for the ATIM period. When IEEE 802.11 was standardized, saving power was not a major concern, even though limited powers saving features are specified. Nodes in IEEE 802.11 always transmit at the highest power possible (unless manually configured to transmit at a specific lower power).

This could result in delays, especially for nodes that are located at the edge of the transmission range of another ongoing communication and overhear the traffic exchanged. In this case the nodes at the edge of the transmission range have to wait for the channel to become idle before starting communication. Moreover, non-destination nodes that overhear a communication will end up depleting their energy resource from overhearing others. Woesner, et al. [2] [97] have shown that the fixed size ATIM window degrades throughput and energy consumption. With a large ATIM window, nodes will be awake longer than necessary, while with a small ATIM window; fewer packets will be announced and transmitted.

3.11 Energy conservation in mobile network:

Mobile devices rely on batteries for energy. Battery power is finite, and represents one of the greatest constraints in designing algorithms for mobile devices [98] [99] [100] Projections on progress in battery technology show that only small improvements in the battery capacity are expected in next future [101]. Under these conditions, it is vital that power utilization be managed efficiently by identifying ways to use less power, preferably with no impact on the applications. Limitation on battery life, and the additional energy requirements for supporting network operations (e.g., routing) inside each node, make the energy conservation one of the main concern in ad hoc networking [102]. The importance of this problem has produced a great deal of research on energy saving in wireless networks in general [103], and ad hoc networks in particular [103,104]. Strategies for power saving have been investigated at several levels of a mobile device including the physical-layer transmissions, the operating system, and the applications [104]. Ref. [105] points out battery properties that impact on the design of battery powered devices.

Power-saving policies at the operating system level include strategies for CPU scheduling [106] [107], and for the hard-disk management [108]. At the application-level, policies that exploit the application semantic or profit of tasks remote execution have been proposed [109]. However, in small mobile devices, networking activities have a major impact on energy consumption. Experimental results show that power consumption related to networking activities is approximately 10% of the overall power consumption of a laptop computer, but it raises up to 50% in handheld devices [110]. The impact of network technologies on power consumption has been investigated in depth in [111]. The key point in energy-aware networking is the fact that a wireless interface consumes nearly the same amount of energy in the receive transmit and idle state; while in the sleep state, an interface cannot transmit or receive, and its power consumption is highly reduced. For example, measurements of 802.11 ''Wi-Fi'' wireless interfaces [112], [113], [114], [115] show that the ratio between power consumption in the transmit and idle state is less than two (the receiving state being intermediate); furthermore, the idle-state power consumption is about one order of magnitude greater than that in the sleep state. Hence, to reduce energy consumption of a network interface, it is necessary to define network protocols that maximize the time the interface spends in a power saving mode (e.g., the sleep state) by eliminating/ reducing the network interface idle times. This approach has been extensively applied in infrastructure-based wireless networks where effective policies have been defined at all layers of the protocol stack by moving the communication and computation efforts on the fixed infrastructure, and maintaining the network interface of the mobile device in the sleep state for most of the time, see e.g., [116] and references herein. This is not a viable approach in an ad hoc network however, where such fixed elements generally do not exist. In addition, self-organization introduces a new metric for measuring the energy savings: the network lifetime. In an infrastructure wireless network, energy management strategies are local to each node, and are aimed to minimize the node energy consumption. This metric is not viable for ad hoc networks where nodes must also cooperate to network operations to guarantee the network connectivity. A greedy node that remains most of the time in a sleep state, without contributing to routing and forwarding, will maximize its battery I. Chlamtac et al. / Ad Hoc Networks 1 (2003) 13-64 41 lifetime but compromise the lifetime of the network. We can, therefore, identify (at least) two classes of power-saving strategies for ad hoc networks: local strategies, that typically operate on small time scales (say milliseconds), and global strategies that operate on longer time scales.

LOCAL STRATEGIES operate inside a node and try to put the network interface in a power saving mode with a minimum impact on transmit and receive operations. These policies typically operate at the physical and MAC layer, with the aim to maximizing the node battery lifetime without affecting the behavior of the high-level protocols. By focusing on power saving at the transmission level, some authors have proposed and analyzed policies (based on monitoring the transmission error rates), which avoid useless transmissions when the channel noise makes low the probability of a successful transmission [117] [118]. Similar policies have been proposed for random access-based MAC protocols [119] [120]. Specifically, at the MAC layer, power-saving strategies are designed to avoid transmitting when the channel is congested, and hence there is a high collision probability.

These policies achieve power consumption by reducing the energy required to successfully transmit a packet. By applying these policies to the IEEE 802.11 MAC protocol, in [120] it has been shown that optimal tuning of the network interface for achieving the minimal energy consumption almost coincides with the optimal channel utilization.

This behavior is associated with the energy consumption model of WLANs interface in which the receive, transmit, and idle states are almost equivalent from a power consumption standpoint.

In general, power saving in CSMA-based protocols is achieved by using the information derived from the media access control protocol to find intervals during which the network interface does not need to be listening. For example, while a node transmits a packet, the other nodes within the same interference and carrier-sensing range must remain silent. Therefore, these nodes can sleep with little or no impact on system behavior. For example, PAMAS [121] turns off a nodes radio when it is overhearing a packet not addressed to it.

Ref. [122] presents a comparison of a number of MAC-layer protocols from the energy efficiency standpoint. In [123] the authors consider low-cost large-scale devices and present a new approach to energy-efficient MAC protocols based on a pseudorandom protocol, which combines the fairness from random access protocols with the low energy requirements of classical TDMA.

The IEEE 802.11 standard includes a power saving mechanism effective for one-hop ad hoc networks. This scheme maintains synchronization among nodes that therefore can wake up at the same set of time instants, exchange traffic and other management information, and then return to a sleeping state. Additional details on the 802.11 power saving mechanism can be found in [124], while [125] [126] analyze its effectiveness. The 802.11 approach is suitable for static single-hop networks in which nodes_ synchronization can be achieved with a limited effort. This requirement is not feasible in dynamic multi-hop ad hoc networks.

GLOBAL STRATEGIES: The aim of global strategies is to maximize the network lifetime. These are based a network-wide approach to power saving, and on the idea that when a region is dense in terms of nodes, only a small number of them need to be turned on in order to forward the traffic. To achieve this set of nodes is identified which must guarantee network connectivity (to participate in packets routing and forwarding), while remaining nodes can spend most of the time in the sleep state to maximize energy saving. Nodes participating in packet forwarding may naturally exhaust their energy sooner, thus compromising the network connectivity. Therefore, periodically, the set of active nodes is recomputed by selecting alternative paths in a way that maximizes the overall network lifetime. Identifying the networks dominating sets is a typical goal of a global strategy. A dominating set is a subset of network nodes such that each node is in the set, or it has a neighbor in that set. Dominating sets, if connected, constitute the routing/forwarding backbone in the ad hoc network. As the computation of the minimal dominating set is computationally unfeasible, in the literature several distributed algorithms exist to approximate suitable dominating sets, see for example [127] [128] [129] [130] [131] [132]. Span [127] is a distributed algorithm 42 I. Chlamtac et al. / Ad Hoc Networks 1 (2003) 13-64 to construct dominating sets using nodes local decisions to sleep, or to join the routing backbone. Nodes participating in the backbone are named coordinators. Coordinators are always in an active state, while non-coordinator nodes are normally in the sleep state, and wake up to exchange traffic with the coordinators. Periodically, the coordinator set is recomputed. The effectiveness of Span depends on the energy consumption in the idle and sleep state: Span benefit increases with the increase of the idle-to-sleep energy-consumption ratio [133].

Span integrates with the 802.11 power saving mode, thus guaranteeing that non-coordinator nodes can receive packets that are buffered by the coordinators while they are sleeping. Nodes physical position (obtained for example via GPS) is used in the GAF algorithm to construct the

routing/forwarding backbone. A grid structure is superposed on the network, and each node is associated with a square in the grid using its physical position. Inside the square only one node is in the non-sleeping state [132]. AFECA [131] is an asynchronous distributed algorithm for constructing a routing backbone. Nodes alternate between active and sleep states, where in principle a node remains in the sleep state for a time proportional to the number of its neighbors, thus guaranteeing, in average, a constant number of active nodes.

Controlling the power of the transmitting node is the other main direction for achieving power saving in ad hoc networks. In addition, a reduced transmission power allows spatial reuse of frequencies, which can help increasing the total throughput of network and minimize interference. In wireless systems, the existence or lack of a link between two nodes mainly depends (given the acceptable bit error rate) on the transmission power and the transmission rate. By increasing the transmission power the number of feasible links is increased, but at the same time this increases the energy consumption and the interference [134]. Recently, several studies focused on controlling network topology by assigning per-node transmit powers that guarantee network connectivity, and minimize the transmit power [125] [135] [136] [137] [138].

The algorithmic aspects of topology control problems are discussed in [139]. Transmission power is highly correlated with energy consumption. It determines both the amount of energy drained from the battery for each transmission, and the number of feasible links. These two effects have an opposite impact on the energy consumption. By increasing the transmission\ power we increase the per-packet transmission cost (negative effect), but we decrease the number of hops to reach the destination (positive effect) because more and longer links become available.

The trade-off between minimum transmission power and number of hops further complicates the design of routing algorithms. A large part of recent work on energy efficiency in ad hoc networks is concentrated on routing [140] [137] [141] 142], where the transmitting power level is an additional variable in the routing protocol design [143]. This problem has been addresses from two different perspectives: (i) energy is an expensive, but not a limited resource (battery can be recharged/replaced), or (ii) the energy is finite. The former case applies to mobile ad hoc network in general, while the latter appears to be a suitable model for sensor networks. In case (i), energy consumption must be minimized; typically, this translates in the following target: minimize the total energy consumed per packet to forward it from source to destination. The minimization of per-packet energy does not maximize network lifetime, as residual energy of the nodes are not taken into consideration. On the other hand, in case (ii), the energy is a hard constraint [144], and the maximum lifetime is the target. Minimum-energy routings minimize the energy consumed to forward a packet from the source to the destination [145] [146] [147]. Similarly to proactive routing algorithms [148] [147] try to find I. Chlamtac et al. / Ad Hoc Networks 1 (2003) 13-64 43 minimum energy routes for all nodes, while PARO [145] behaves as a reactive algorithm by minimizing the energy consumption of ongoing flows. In PARO, nodes intermediate to the source-destination pair elect themselves to forward packets, thus reducing the aggregate transmission power consumed by network devices. PARO attempts to maximize the number of redirector nodes between source-destination pairs, thereby minimizing the transmission power.

On-line maximum-lifetime routing is a complex problem [149]. In [150], for a static network with known and constant flows, the maximum lifetime routing is modeled as a linear programming problem. The solution of this model provides the upper bound on the network lifetime that is used to analyze the effectiveness of the algorithms. For a single power level, an optimal algorithm is presented; while, for the general case, the authors present an algorithm that selects routes and adjusts the corresponding power levels achieving a close to the optimal lifetime. A balance between minimum-energy and maximum lifetime is the target of the CMMBCR strategy [151]. CMMBCR applies a conditional strategy that uses the minimum energy route, if the nodes residual energy is greater than a given threshold. Otherwise, a route that maximizes the minimum residual energy is selected.