the_handbook_of_ad_hoc_wireless_networks_8

Chia sẻ: Kata_8 Kata_8 | Ngày: | Loại File: PDF | Số trang:50

Thêm vào BST

Báo xấu

77
lượt xem 17
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài liệu 'the_handbook_of_ad_hoc_wireless_networks_8', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: the_handbook_of_ad_hoc_wireless_networks_8

Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 21 GPS-Based Reliable Routing Algorithms for Ad Hoc Networks Abstract 21.1 Introduction 21.2 Ad Hoc Routing Protocols Dynamic Source Routing (DSR) Protocol • Ad Hoc On- Young-Joo Suh Demand Distance Vector (AODV) Routing Protocol Pohang University of Science and 21.3 Global Positioning System Technology 21.4 Reliable Route Selection Algorithms Won-Ik Kim Stable Zone and Caution Zone • AODV-RRS Protocol Electronics & Telecommunications Description • Effect of Stable Zone Radius • Variations of Research Institute AODV-RRS • Extensions to Other Ad Hoc Routing Protocols Dong-Hee Kwon 21.5 Performance Evaluation 21.6 Conclusions Pohang University of Science and Technology References Abstract The routing protocols designed for wired networks can hardly be used for mobile ad hoc networks due to unpredictable topology changes, and thus several routing protocols for mobile ad hoc networks have been proposed. The goal of this chapter is to select the most reliable route that is impervious to failures due to topological changes caused by host mobility. To select a reliable route, we introduce the concept of stable zone and caution zone and then apply it to the route discovery procedure of the existing ad hoc routing protocols. The concept of the stable zone and caution zone, which are located in a mobile node’s transmission range, is based on a mobile node’s location and mobility information received by the Global Positioning System (GPS). We evaluated the proposed algorithms by simulation in various conditions, and we obtained an improved performance in route maintenance time, the number of route disconnec- tions, and packet delivery ratio. 21.1 Introduction Mobile multi-hop wireless networks, called ad hoc networks, are networks with no ﬁxed infrastructure, such as underground cabling or base stations, where mobile nodes are connected dynamically in an arbitrary manner. Thus, nodes in such networks function as routers, which discover and maintain routes to other nodes. A central challenge in the design of ad hoc networks is the development of dynamic routing protocols that can efﬁciently ﬁnd routes between the source and destination. The routing pro- tocols must be able to keep up with the high degree of node mobility, which often changes the network topology drastically and unpredictably [6,15]. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Routing protocols in conventional wired networks generally use either distance vector or link state routing protocols, both of which require periodic routing advertisements to be broadcast by each router [7]. However, such protocols do not perform well in dynamically changing ad hoc network environments. The limitations of mobile networks, such as limited bandwidth, constrained power, and host mobility, make designing ad hoc routing protocols particularly challenging. To overcome these limitations, several source-initiated on-demand routing protocols, including Dynamic Source Routing (DSR) [8] and Ad- hoc On-demand Distance Vector (AODV) [9,10], have been proposed. These protocols create routes only when the source node has data to transmit. When a node requires a route to a destination, it initiates a route discovery procedure. This procedure is completed once a route has been found or all possible route permutations have been examined. Once a route has been established, it is maintained by a route maintenance procedure until either the destination becomes inaccessible or the route is no longer desired. During the route discovery procedure, some of the existing source-initiated routing protocols such as DSR and AODV attempt to choose a route having the minimum number of hops among available routes. However, the route having the minimum number of hops is not always the best routing path. Although the route having the minimum number of hops may be faster than other routes in packet delivery, it may be highly probable that the spatial distance between any two intermediate nodes in the route may be larger than those in other routes. The larger distance between neighboring nodes may give rise to shorter link maintenance time, which in turn shortens the route maintenance time [13,16]. If there are frequent route failures due to host mobility, it will require additional time to reconﬁgure the route from the source to destination, which results in increased amounts of control packet ﬂooding. Therefore, it may not be said that a route with the smallest hop count is necessarily optimal. The goal of our work is to select the most reliable route that is impervious to link failures by topological changes by host mobility, where a route discovery is performed with the location and mobility information received by Global Positioning System (GPS). To accomplish this goal, we propose new route discovery algorithms referred to as Reliable Route Selection (RRS). In this chapter, we assume that each node is aware of its current location through the use of GPS receivers with which each node is equipped. GPS has been successfully employed for determining a mobile node’s position and speed. It is expected that the proliferation of GPS-based positioning technology will proceed at a fast pace, and the accuracy of this technology will be dramatically enhanced [12,14]. The remainder of this chapter is organized as follows. Section 21.2 brieﬂy describes related works — DSR and AODV routing protocols. Section 21.3 provides some background on GPS. Section 21.4 describes the proposed GPS-based reliable route selection algorithms. The performance of the proposed algorithms is evaluated and compared in Section 21.5. We summarize our results in Section 21.6. 21.2 Ad Hoc Routing Protocols 21.2.1 Dynamic Source Routing (DSR) Protocol The DSR protocol [8,18] uses source routing, where a packet carries in its header the complete list of nodes through which the packet must pass [6,8]. DSR is composed of two mechanisms: route discovery and route maintenance. Route discovery and route maintenance operate on demand. Route discovery is the mechanism by which a node S wishing to send a packet to a destination D obtains a source route to D. When node S does not know a route to node D, S initiates a route discovery by transmitting a Route Request (RREQ) message as a single local broadcast packet, which is received by all nodes currently within transmission range of S. Each RREQ message contains a unique request ID and a record listing the addresses of each intermediate node through which the RREQ has been forwarded. When a node receives a RREQ message, if it is the target of the route discovery, it replies with a Route Reply (RREP) message to node S. Otherwise, if the node receiving the RREQ message recently saw another RREQ from the same initiator having the same request ID, or if it ﬁnds that its own address is already listed in the route record in the RREQ message, it discards the RREQ message. If not, the node appends its own address to the route record in the RREQ message and forwards it. On receiving the RREP message © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com that includes the route from node S to node D, node S caches the route included in the RREP message. When node S sends a data packet to node D, the entire route is included in the packet header (hence source routing). Intermediate nodes use the source route included in the packet to determine to whom the packet should be forwarded. Route maintenance is the mechanism by which the sender node S detects whether the network topology has been changed such that it can no longer use its route to D because a link along the route no longer works. Each forwarding node is responsible for conﬁrming the receipt of each packet by the next hop node by a link-layer acknowledgment. If a packet is retransmitted the maximum number of times and no receipt conﬁrmation is received, the node returns a Route Error message to original sender S, identifying the link over which the packet could not be forwarded. Node S then removes the broken link from its cache. If node S has another route to D in its route cache, S can send packets using the new route immediately. Otherwise, S may perform a new route discovery. In the DSR protocol, a node forwarding or overhearing any packet may add the routing information to its own route cache, which can speed up a route discovery and reduce the propagation of route requests. But stale caches can adversely affect the performance of DSR. With passage of time and host mobility, cached routes may become invalid. A sender host may try several stale routes before ﬁnding a good route [11]. 21.2.2 Ad Hoc On-Demand Distance Vector (AODV) Routing Protocol The AODV routing protocol [9,10,18] supports multi-hop routing among mobile nodes for establishing and maintaining an ad hoc network. Unlike DSR, which uses source routing, AODV uses hop-by-hop routing. AODV is based on the Destination Sequence Distance Vector (DSDV) routing protocol [7]. The main difference is that AODV is reactive, while DSDV is proactive. AODV requests a route only when it is needed, but it does not require mobile nodes to maintain routes to the destination that are not actively used. AODV retains the desirable feature of DSR that routes are maintained only between nodes that need to communicate. When node S wants to send a packet to node D, it checks its route table to determine whether it has a route to D. If S has a route to D, S forwards the packet to the next-hop node toward D. If S does not have a route to D, S initiates route discovery. Source node S ﬂoods a Route Request (RREQ) message, which contains source address, destination address, sequence number, and broadcast ID. After sending the RREQ message, S sets a timer to wait for a reply. When a node receives a RREQ message, it checks whether it has already seen the RREQ message by noting the source address/ broadcast ID pair. If so, it discards the message. Otherwise, it sets up a reverse path pointing towards the source. A node can send a Route Reply (RREP) message provided that it has an unexpired entry for the destination in its route table, and it knows a more recent path than the one previously known to sender S. To determine whether the path known to an intermediate node is more recent, a destination sequence number is used. A new RREQ message by a node is assigned a higher destination sequence number. If the node cannot send a RREP message, it increments the RREQ’s hop count and then broadcasts the RREQ message to its neighbors. When the intended destination receives a RREQ message, it replies by sending a RREP message. When an intermediate node receives the RREP message, it sets up a forward path entry to the destination in its route table. The RREP travels along the reverse path set up when the RREQ message was forwarded. Source node S can begin data packet transmissions as soon as the ﬁrst RREP is received and later update its routing info if it discovers a better route. Figure 21.1 shows an example of a route discovery by the AODV routing protocol. As shown in Fig. 21.1a, a RREQ message from node S is ﬂooded through the network until it reaches node D. On its way through the network, the RREQ initiates the creation of temporary route table entries for the reverse path at all the nodes it passes, as shown in Fig. 21.1b. Next, a RREP message from node D is transmitted back to node S along the temporary reverse path, as shown in Fig. 21.1c. When the RREP message is routed back along the reverse path, all nodes on this route set up a forward path by pointing to the node that transmitted the RREP message. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com S S S RREQ RREP D D D (a) RREQ flooding (b) Reverse Path Setup (c) Forward Path Setup FIGURE 21.1 Route discovery procedure of AODV. A route selected by the route discovery procedure is maintained as follows. If a route is broken due to the movement of the source, the source reinitiates route discovery to ﬁnd a new route to the destination. If a route is broken due to the movement of either the destination or an intermediate node on the route, the node upstream of the break transmits a Route Error (RERR) message to the source node. When the source node receives the RERR message, it can reinitiate a route discovery if a route is still needed. Neighborhood information is obtained from hello messages periodically transmitted by neighboring nodes. Each time a node receives a hello message from a given neighbor, it updates the info associated with the neighbor in its route table. Hello messages can be used to maintain the local connectivity of a node. When a mobile node uses its shared link layer protocol such as IEEE 802.11, instead of using hello messages, the node may listen to the retransmission of data packets to ensure that the next-hop node is still within its transmission range [9,10]. 21.3 Global Positioning System The Global Positioning System (GPS) is a worldwide radio navigation system formed from a constellation of satellites and their ground stations [12]. The system provides accurate, continuous, worldwide, three- dimensional position and velocity information to GPS receivers. The satellite constellation consists of 24 satellites arranged in six orbital planes with four satellites per plane. The ground stations are spread worldwide and monitor the status of the satellites. The satellites are used as reference points to calculate positions accurate to a matter of meters. GPS can provide service to an unlimited number of users since the user receivers operate passively, much like television sets. GPS utilizes the concept of one-way time of arrival (TOA) ranging. Satellite transmissions are refer- enced to highly accurate atomic frequency standards onboard the satellites, which are synchronized with an internal GPS system time base. The satellites broadcast ranging codes and navigation data on two frequencies using a technique called code division multiple access (CDMA). That is, there are only two frequencies in use by the system, called L1 (1575.42 MHz) and L2 (1227.6 MHz). Each satellite transmits on these frequencies, but with different ranging codes from those employed by other satellites. These codes are also called “pseudo random number,” and they have low cross-correlations with respect to one another. The navigation data provide the means for the receiver to determine the location of the satellite at the time of signal transmission, whereas the ranging code enables the user’s receiver to determine the propagation delay of the signal from the satellite to a GPS receiver. With that information, a GPS receiver can determine the satellite-to-user range. This technique requires that the user receiver also contain a © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com clock. Utilizing this technique to measure the receiver’s three-dimensional location requires that TOA ranging measurements be made to four satellites. If the receiver clock is synchronized with the satellite clocks, only three measurements would be required. The results of TOA ranging measurements are applied to the “triangulation method,” and then the location information with some error can be calculated. The errors are due to the fact that the signal is deteriorated by ionospheric and tropospheric effects, noisy channel, and clock inaccuracy during its travel from the satellite to the receiver. Basically, GPS provides two services: the Standard Positioning Service (SPS) and the Precise Positioning Service (PPS). The SPS is designated for the public and provides a predictable accuracy of at least 100 m (2 drms, 95%) in the horizontal plane and 156 m (95%) in the vertical plane. The distance root mean square (drms) is a common measure used in navigation. The value of 2 drms is the radius of a circle that contains at least 95% of all possible ﬁxes that can be obtained with a system at any one place. The PPS is used for military purposes and provides predictable accuracy of at least 22 m (2 drms, 95%) in the horizontal plane, 27.7 m (95%) in the vertical plane. Since SPS and PPS do not provide exact location information, the Differential GPS (DGPS) system has been introduced to provide more accurate location information. In the basic form of DGPS, a reference station with a precisely known location is used. The reference station also performs GPS signal calculation. By comparing the result of location information obtained by GPS signal with the preknown location information, the reference station can produce error correction information. The error correc- tion information is broadcast by the reference station and used for error correction of DGPS receivers, which can hear signals both from the satellites and the reference station. Some DGPSs can provide exact location information with no more than 1 m error. 21.4 Reliable Route Selection Algorithms In AODV, the source node transmits its data through the route determined by the ﬁrst RREQ that arrived at the destination. The selected route generally has the lowest hop count, which means that any two intermediate nodes on the route may be remotely located from each other, and thus the route maintenance time may not last long, causing a link failure in an ad hoc network environment where mobile nodes frequently move. If a link in the selected route is broken, a route reconstruction procedure is initiated by on-demand routing protocols. During the time a route reconstruction procedure is being performed, the source cannot transmit its data, and control messages generated to reconstruct the route may degrade the network performance. Therefore, selecting a reliable route during route discovery is important. To achieve reliability of the selected route, we propose new route selection algorithms using the concept of a stable zone and a caution zone based on a mobile node’s position, speed, and direction information obtained from GPS. The proposed algorithm is ﬁrst applied to the AODV routing protocol and then applied to other ad hoc routing protocols. 21.4.1 Stable Zone and Caution Zone For the proposed algorithms, we introduce the concept of virtual zone, where the transmission range of a node can be divided into two zones: stable zone and caution zone. Stable zone is the area in which a mobile node can maintain a relatively stable link with its neighbor node since they are located close to each other. Caution zone is the area in which a mobile node can maintain an unstable link with its neighbor nodes since they are located relatively far from each other. These zones are used for deciding whether or not the link state between any two nodes is reliable. The stable zone and the caution zone change dynamically depending on a mobile node’s speed and direction. As mentioned previously, we know the position, speed, and direction of mobile nodes using the GPS information (i.e., latitude, longitude, and altitude). For simplicity, we assume that all mobile nodes have the same altitude value and transmission range. Figure 21.2 shows the two zones. In the ﬁgure, the radius of the transmission range is R, the stable zone is a smaller inner circle with a radius of r in the transmission range, and the caution zone is the transmission range excluding the stable zone. The inner circle that indicates the stable © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Stable Zone Stable Zone Caution Zone Node A’s direction Current Position of Transmission A Mobile Node A Range A R Radius o f R r Transmission Range Caution Zone Stable Zone Center r Stable Zone Radiu s FIGURE 21.2 Stable zone and caution zone. zone is inscribed in an outer circle that indicates the transmission range. The stable zone radius (r) is determined from the speed of a mobile node. If a mobile node’s speed is zero, r will be the same as R, and it becomes smaller when a mobile node starts to move. If the mobile node increases its speed, then the value of r becomes smaller in proportion to the speed of the mobile node, and vice versa. In the proposed algorithm, adequate selection of stable zone radius (r) for a node’s speed is very important. This will be discussed in detail later. In addition to a mobile node’s speed, its moving direction is also important. Even when a mobile node is located in the border range of a neighbor node, if the two nodes progress to the face-to-face direction, the link between the two nodes will be stable. In Fig. 21.2, since node A moves to the right, the location of the stable zone center is to the right of node A’s current location and on the line of the mobile node’s movement direction. Thus, the moving direction of a node will be the direction pointing from the node’s current location to the stable zone center. 21.4.2 AODV-RRS Protocol Description Now we describe the proposed protocol called AODV-RRS, which is obtained by applying the Reliable Route Selection (RRS) algorithm using the concept of stable zone and caution zone to the AODV routing protocol. In AODV-RRS, the following additional GPS information is included in each RREQ control packet: • mobile_node_position (x,y) • stable_zone_center (x',y') • stable_zone_radius (r) The mobile_node_position (x,y), stable_zone_center (x',y'), and stable_zone_radius (r) indicate the cur- rent position of a mobile node, the center of the stable zone, and the radius of the stable zone, respectively. The GPS information is used to decide whether or not a link between two nodes is stable. The route discovery mechanism of AODV-RRS is very similar to that of AODV, but AODV-RRS requires the following additional steps: 1. The source node or an intermediate node (e.g., node S) ﬂoods a RREQ message, which includes its own GPS information, to all nodes within its transmission range. 2. If a node (e.g., node M) receives the RREQ message, it calculates whether or not it is in the stable zone of node S, using its own GPS information and the GPS information included in the received RREQ message (i.e., GPS information of node S). • If node M is located in the stable zone of the node that transmitted the RREQ message and it is not the ﬁnal destination, node M inserts its own GPS information in the RREQ message and then ﬂoods it. • Otherwise, node M drops the RREQ message. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com D RREQ B C RREQ A RREQ Mobile Node Direction of Node A E Flooding of RREQ FIGURE 21.3 Route discovery using AODV-RRS. Figure 21.3 shows an example of route discovery by AODV-RRS, where node A is the source node or an intermediate node entitled to forward a RREQ message, and the shaded area indicates the stable zone of node A. Four nodes — B, C, D, and E — are located in node A’s transmission range, with nodes B and D located in the stable zone and nodes C and E located in the caution zone. When node A transmits a RREQ message, B, C, D, and E receive the message. Then each node calculates whether or not it is in the stable zone of node A. Since nodes B and D are in the stable zone, they insert their own GPS information into the RREQ message and then ﬂood the message. Although nodes C and E receive the RREQ message, they drop the message since they are located in the caution zone of node A. Figures 21.4a and 21.4b show how a RREQ message is ﬂooded by AODV and AODV-RRS, respectively. When a route discovery is performed by AODV, an intermediate node ﬂoods the RREQ to other nodes as soon as it receives the message, except when a duplicated RREQ is received or when the node is the destination. If two neighboring nodes on a selected route are located near the border of each other’s transmission range (that is, caution zone) as shown in Fig. 21.4a, then a small movement of a node may cause the node to be out of the other node’s transmission range and thus cause a route failure. Frequent route failures cause overheads such as time delay and ﬂood of control packets to reconstruct a new route. Thus, it is not desirable for a mobile node to set up a link with a node located near the border of each other’s transmission range. With the proposed algorithm, on the other hand, when a mobile node receives a RREQ message from a neighbor node located in its caution zone, the node ignores the message and thus does not ﬂood the RREQ. This provides a reliable route that is not easily broken, even though the two nodes move in opposite directions as shown in Fig. 21.4b. Thus, the proposed algorithm reduces the control overhead required to reconstruct a new route. Direction of RREQ flow Direction of (Modified) RREQ flow Stable Zone Physical distance of hop (d,d’) Node’s movement direction D D d > d’ B A S S Transmission range d d’ Caution Zone (a) Normal AODV (b) AODV using RRS algorithm FIGURE 21.4 Comparison of RREQ ﬂow between AODV and AODV-RRS. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Stable Zone Caution Zone Direction of Node A Direction of Node A A A A R R R r r r (a) 0m/sec (b) 5m/sec (c) 10m/sec FIGURE 21.5 Variation of stable zone radius and center according to the mobile node’s speed. 21.4.3 Effect of Stable Zone Radius In the proposed algorithm, determining the optimum value of the stable zone radius variation rate due to node mobility is very important since it affects several performance parameters such as the number of hops between the source and destination, the time delay until a route is constructed, and route reliability. Figures 21.5a, b, and c show the stable zone size (or stable zone radius) when the speed of node A is 0, 5, or 10 m/sec, respectively. When node A does not move, the stable zone extends to the whole transmission range as shown in Fig. 21.5a. But the stable zone shrinks with the increase of node A’s speed as shown in Figs. 21.5b and c. The relation between the speed of a mobile node (S), transmission range radius (R), and stable zone radius (r) can be expressed as r = R – βS, where β is the parameter determining the variation rate of the stable zone radius due to host mobility. If we use a very high value of β, then the stable zone size shrinks drastically with a small increase of node speed, which can construct a more reliable route that cannot be easily broken. However, the cost of reliability is the increased number of hops between the source and destination. As shown in Fig. 21.4, the average length of a link in a selected route by AODV-RRS is shorter than that by AODV (that is, d' ≤ d), which increases the number of hops in a route between the source and destination. Another problem is that if there are a small number of nodes in a network, a very small stable zone size due to a large value of β may cause no route construction. However, AODV-RRS has the important feature that the maintenance time of the selected route lasts considerably longer (and the route is thus more reliable) than the route selected by AODV. Thus, a tradeoff between reliable route construc- tion and the optimal number of hops in each source–destination pair is needed, and our goal is ﬁnding the optimum value of β without causing much increase in the number of hops. We studied it for several β values, and it is discussed in Section 21.5. 21.4.4 Variations of AODV-RRS As mentioned above, the variation rate of the stable zone radius due to host mobility (β) is an important parameter. In the proposed AODV-RRS algorithm, the value of β is ﬁxed. Thus, a route may not be found by using a large value of β, although there are less reliable routes through nodes in caution zones. A less- reliable route may be better than no route in several applications. To solve this problem, we propose a variation of AODV-RRS. In the algorithm, there is a “β value ﬁeld” in the RREQ message. When a source node transmits a RREQ message, the predetermined value of β (β_max) is recorded at the β value ﬁeld. If the source fails to ﬁnd a route to the destination within a predetermined time, it decreases the β value and then starts a route discovery process again. This process repeats until the source ﬁnds a route to the destination. If a route is found with β = 0, then the route is the same route found by AODV. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com AODV-RRS may require more time delay until the source node constructs a route to the destination. However, this variation of AODV-RRS can ﬁnd the best route ever possible (although it may not actually be stable) to the destination. In the worst case, the route found by the algorithm is the same route that will be found by AODV. Thus, this scheme using carefully selected values of β_max and the number of levels between β_max and zero may show better performance than AODV and AODV-RRS. When there are a small number of nodes in a network, another variation of AODV-RRS may be a good solution. When a source node initiates a route discovery process, the route is searched by AODV- RRS. If a route cannot be found within a predetermined time or predetermined number of hops, the algorithm is switched to AODV, and then another route discovery process starts. 21.4.5 Extensions to Other Ad Hoc Routing Protocols The proposed RRS algorithm can be applied to other ad hoc routing protocols. Here, we give examples of such extensions of the RRS algorithm to existing protocols. Destination-Sequence Distance Vector (DSDV) [7] is one of the well-known proactive ad hoc routing protocols. The RRS algorithm can easily be applied to DSDV. When a node updates its routing table from the routing control packets from its neighbor node, it can determine whether or not to update the routing table based on the RRS algorithm. If the neighbor node that sent the routing control packet is in the caution zone, the packet can be silently discarded without any update to its routing table. This makes sense because if a link between any of two neighboring nodes is likely to break easily, then it may be desirable to think that those nodes are not within each other’s transmission range. Thus, RRS for DSDV can reduce the number of route update control packets while providing a reliable route to a destination. Dynamic Source Routing (DSR) is one of the well-known reactive ad hoc routing protocols. Since its basic route discovery mechanism is very similar to that of AODV, the proposed RRS algorithm can easily be applied to the route discovery procedure of DSR except for some optimizations such as the promis- cuous mode. The promiscuous mode is an on-the-ﬂy packet overhearing technique used for efﬁcient route cache update for a node. But we can apply the RRS algorithm to the technique, i.e., modify the overhearing rule such that a node decides according to the RRS algorithm whether or not it learns route information or updates its route cache from the route information contained in the overheard packet. 21.5 Performance Evaluation We studied the proposed AODV-RRS protocol by simulation in various situations and compared it to AODV. For the simulation study, we used the Network Simulator (ns) [1] and a mobility extension of ns (i.e., ns-2) [2]. We assumed that initially 75 mobile nodes are distributed randomly in a ﬂat area of 2250 m × 450 m. Each node in a location moves to a randomly selected location (we call it the target location) with a predetermined speed. Once a node reaches the target location, another random target location is selected. We ran our simulations with movement patterns generated by ﬁve different speeds (2.5, 5, 7.5, 10, and 12.5 m/sec). The reason why we limited the node’s speed to 2.5 ~ 12.5 is that an ad hoc network is not applicable to the extremely high or low speed environment. Each simulation was executed for 300 seconds. Among 75 nodes, 30 nodes were randomly selected as source nodes, and they generated continuous bit rate (CBR) trafﬁc. The packet size was 64 bytes, the packet generation rate was 4 packets/sec, and the bandwidth of each link was 2 Mb/sec. The radio transmission range (R) of each node was 250 meters. To study the effect of β value, we used three values of β: β = 2, β = 3, and β = 4. Table 21.1 summarizes the parameters used in our simulation study. The mobility pattern of a mobile node followed a randomly selected scenario ﬁle. Multiple runs with different seed numbers were conducted for each scenario, and output data were averaged over those runs. These simulations of random scenarios are very similar to the approaches in [3–5]. For fair comparison, identical mobility and trafﬁc scenarios were used for AODV and AODV-RRS. Both protocols detect a link breakage using a feedback from the MAC layer, and no additional network layer mechanism such as hello messages is used. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com TABLE 21.1 Simulation Environments Parameters Value Transmission range 250 m 2250 m × 450 m Network size Simulation time 300 sec Number of mobile nodes 75 Number of trafﬁc sources 50 Bandwidth 2 Mb/sec Packet transmission rate 4 packets/sec Trafﬁc type Constant bit rate β 2, 3, and 4 Figure 21.6 shows the average route maintenance time per source node as a function of node mobility (speed). The average route maintenance time is an average period of time from the time when a route is established to the time when the route is broken. As shown in the ﬁgure, AODV-RRS shows longer route maintenance time than AODV, which indicates that the route established by AODV-RRS is more reliable than that established by AODV. Note that AODV-RRS shows longer route maintenance time when β values are large. This is due to the fact that the stable zone size becomes smaller with a large value of β, and thus a route lasts a longer period of time before it breaks. The average route maintenance time gets smaller as the speed is increased. For all classes of speed, AODV-RRS outperforms AODV in route maintenance time. Figure 21.7 shows the average route recovery latency per source node as a function of speed. The average route recovery latency is an average period of time from the time when a route is broken to the time when a route is reconstructed, which includes the route discovery latency. The average route recovery latency of AODV-RRS is longer than that of AODV. This is because the number of hops in a route constructed by AODV-RRS is generally larger than that in a route constructed by AODV, and the probability that no route is found by AODV-RRS is higher than that of AODV, especially when the number of nodes in a network is very small. The average route recovery latency of AODV-RRS increases as the β value increases, since a high value of β generally causes an increased number of hops in a route. From Figs. 21.6 and 21.7, we can see that there are tradeoffs between the average route maintenance time and the average route recovery latency. However, the differences between the average route main- tenance time of AODV-RRS and that of AODV are on the order of seconds, while the differences in the average route recovery latencies of the two algorithms are on the order of milliseconds. 26 24 AODV Avg. Route Maintenance Time (second) AODV-RRS(2) 22 AODV-RRS(3) 20 AODV-RRS(4) 18 16 14 12 10 8 6 4 2.5 5 7.5 10 12.5 Speed(m/sec) FIGURE 21.6 Average route maintenance time per source node. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 3 AODV Avg. Route Recovery Latency (second) 2.5 AODV-RRS(2) AODV-RRS(3) 2 AODV-RRS(4) 1.5 1 0.5 0 2.5 5 7.5 10 12.5 Speed (m/sec) FIGURE 21.7 Average route recovery latency per source node. Figure 21.8 shows the number of route disconnections per source node during the whole simulation time. As illustrated in the ﬁgure, AODV-RRS shows a smaller number of route disconnections than AODV. This is due to the fact that AODV-RRS constructs very stable routes, and thus the routes are not easily broken when nodes move to other locations. Although the number of route disconnections increases with the increase of node speed, the difference in the number of disconnections of the protocols becomes larger when node speed becomes higher because AODV-RRS constructs routes through nodes located very close to each other even when nodes move fast, and thus the routes last a longer period of time, while routes constructed by AODV are fragile even with a small movement of nodes. According to an analysis of the effects of mobility on TCP performance in mobile ad hoc networks [17], mobile nodes’ movements result in frequent route disconnections, which in turn cause signiﬁcant TCP throughput degradation. Although we did not conduct a TCP performance study, we expect that AODV-RRS also improves the TCP performance since it reduces the number of route disconnections. From Figs. 21.6–21.8, we can expect that the characteristics of AODV-RRS with a reasonably chosen β value are especially good for multimedia applications that require constant delay jitters without frequent disconnections. While it is generally true that the delay bound for packet delivery is critical to multimedia applications, in ad hoc networks, how long a route remains connected will also be an important factor for determining service quality. 45 AODV 40 Avg. Number of Route Disconnections AODV-RRS(2) 35 AODV-RRS(3) AODV-RRS(4) 30 25 20 15 10 5 2.5 5 7.5 10 12.5 Speed FIGURE 21.8 Number of route disconnections per source node. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 1.35 AODV 1.33 AODV-RRS(2) 1.31 AODV-RRS(3) 1.29 AODV-RRS(4) 1.27 Hop Ratio 1.25 1.23 1.21 1.19 1.17 1.15 2.5 5 7.5 10 12.5 Speed (m/sec) FIGURE 21.9 Normalized number of actual hops of a route. Figure 21.9 shows the normalized number of the actual hops of a route. It is an average value of the ratio of the actual number of hops to the optimal number of hops for successfully arrived packets at destinations. As shown in the ﬁgure, as the β value increases, the number of hops of AODV-RRS also increases. This is due to the fact that AODV-RRS tries to maintain a more reliable route at the sacriﬁce of an increased number of hops. But the difference between AODV-RRS and AODV is not so signiﬁcant, at most about 0.13 hops even when a mobile node’s speed is 12.5 m/sec and β = 4. Figure 21.10 shows the average packet delay as a function of speed. The average packet delay is the average period of time from when the sender transmits a packet to when the packet arrives at the destination. As shown in the ﬁgure, AODV and AODV-RRS show very comparable packet delays. This can be explained as follows. If there are no link failures, a route constructed by AODV will have a shorter packet delay than a route constructed by AODV-RRS, since the route constructed by AODV has the smaller number of hops. However, the increased number of link failures in a route constructed by AODV lengthens the packet delay. Thus, frequent link reconstructions by AODV lengthen the average packet delay. 0.9 AODV 0.8 AODV-RRS(2) 0.7 AODV-RRS(3) Avg. Packet Delay (second) 0.6 AODV-RRS(4) 0.5 0.4 0.3 0.2 0.1 0 2.5 5 7.5 10 12.5 Speed FIGURE 21.10 Average packet delay. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 0.98 0.97 0.96 0.95 Avg. Delivery Ratio (% ) 0.94 0.93 0.92 AODV 0.91 AODV-RRS(2 ) 0.9 AODV-RRS(3 ) 0.89 AODV-RRS(4 ) 0.88 2.5 5 7.5 10 12.5 Speed (m/sec) FIGURE 21.11 Average packet delivery ratio. Figure 21.11 shows the average packet delivery ratio as a function of speed. This ratio is the number of packets that arrived at the destination successfully divided by the number of packets transmitted by the sender. The packet delivery ratios of the protocols generally become smaller as the node speed increases. When a mobile node’s speed is low (e.g., 2.5 or 5 m/sec), the average delivery ratios of the protocols are comparable. But when the speed of a mobile node becomes higher, the average delivery ratio by AODV-RRS is better than that by AODV since the number of link disconnections increases signiﬁcantly with host mobility. 21.6 Conclusions In ad hoc networks, network topology changes drastically and unpredictably due to host mobility. Existing protocols for ad hoc networks have the problem of a fragile route. Consequently, a selected route comes to have a short route maintenance time, which causes the overhead of reestablishing a new route. To solve the problem, we propose new route selection algorithms to establish a reliable route that does not break easily due to the frequent topological changes caused by mobile nodes’ mobility. We have introduced the concept of stable zone and caution zone. These zones change dynamically depending on a mobile node’s speed and direction. Our simulation study shows that a route selected by AODV-RRS lasts a considerably longer period of time than that selected by AODV, and the number of route disconnections by AODV-RRS is smaller than that by AODV. References [1] K. Fall and K. Varadhan, ns notes and documentation, The VINT project, UC Berkeley, LBL, USC/ ISI, and Xerox PARC, May 1998. [2] The CMU Monarch Project, The CMU Wireless and Mobility Extensions to ns, URL: http:// www.monarch.cs.cmu.edu/. [3] S.-J. Lee, M. Gerla, and C.-K. Toh, A Simulation Study of Table-driven and On-Demand Routing Protocols for Mobile Ad Hoc Networks, IEEE Network, 1999, pp. 48–54. [4] S.R. Das, C.E. Perkins, and E.M. Royer, Performance Comparison of Two On-Demand Rout- ing Protocols for Ad-hoc Networks, Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2000), Tel Aviv, Mar. 2000, pp. 3–12. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com [5] P. Johansson, T. Larsson, and N. Hedman, Scenario-Based Performance Analysis of Routing Protocols for Mobile Ad-hoc Networks, Proceedings of the Fifth Annual ACM/IEEE Interna- tional Conference on Mobile Computing and Networking (MobiCom ’99), Seattle, WA, Aug. 1999, pp. 195–206. [6] E.M. Royer and C.-K. Toh, A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks, IEEE Personal Communications, Apr. 1999, pp. 46–55. [7] C.E. Perkins and P. Bhagwat, Highly Dynamic Destination-Sequenced Distance-Vector Rout- ing (DSDV) for Mobile Computers, ACM Comput. and Commun. Rev. (ACM SIGCOMM ’94), Oct. 1994, pp. 234–244. [8] D. Johnson and D. Maltz, Dynamic source routing in ad-hoc wireless networks, in T. Imielinski and H. Korth, Eds., Mobile Computing, Kluwer Academic Publishers, Dordrecht, 1996, Chap. 5. [9] C.E. Perkins, Ad Hoc On Demand Distance Vector (AODV) Routing, Internet Draft, Nov. 1997. [10] C.E. Perkins and E.M. Royer, Ad-hoc On-demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA ’99), Feb. 1999, pp. 90–100. [11] S. Basagni, I. Chlamtac, and V.R. Syrotiuk, Dynamic Source Routing for Ad-Hoc Networking Using the Global Positioning System, Proceedings of the IEEE Wireless Communications and Networking Conference 1999 (WCNC ’99), Sep. 1999, pp. 301–305. [12] E.D. Kaplan, Understanding the GPS: Principles and Applications, Artech House, Norwood, MA, Feb. 1996. [13] S. Basagni et al., Route Selection in Mobile Multimedia Ad-hoc Networks, Proceedings of the IEEE International Workshop on Mobile Multimedia Communications (MoMuC ’99), Nov. 1999, pp. 97–103. [14] Y.-B. Ko and N.H. Vaidya, Location-Aided Routing (LAR) in Mobile Ad Hoc Networks, Proceedings of ACM/IEEE International Conference Mobile Computing and Networking Confer- ence (MobiCom ’98), Dallas, TX, Oct. 1998, pp. 66–75. [15] C.-K. Toh, Wireless ATM and Ad-hoc Networks: Protocols and Architectures, Kluwer Academic Publishers, Dordrecht, 1997. [16] W.-I. Kim, D.-H. Kwon, and Y.-J. Suh, A Reliable Route Selection Algorithm Using Global Positioning Systems in Mobile Ad-hoc Networks, Proceedings of the IEEE International Con- ference on Communications (ICC ’2001), June 2001. [17] G. Holland and N.H. Vaidya, Analysis of TCP Performance over Mobile Ad Hoc Networks, Proceedings of the Fifth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom ’99), Seattle, WA, Aug. 1999, pp. 219–230. [18] C.E. Perkins, Ed., Ad Hoc Networking, Addison-Wesley, Reading, MA, 2001. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 22 Power-Aware Wireless Mobile Ad Hoc Networks Abstract Ahmed M. Safwat 22.1 Introduction 22.2 Medium Access and Energy Conservation Queen’s University, Canada 22.3 Routing and Energy Efﬁciency in Wireless Hossam S. Hassanein Ad Hoc Networks Queen’s University, Canada 22.4 Application-Level Energy Conservation Hussein T. Mouftah 22.5 Summary and Conclusions References Queen’s University, Canada Abstract Power-aware protocol design is important due to the limited battery capacity of the mobile devices making up the ad hoc wireless network. The performance of the medium access control (MAC) scheme not only has a signiﬁcant effect on the performance of the routing method employed, but also on the energy consumption of the wireless network interface card (NIC). Thus, a thorough energy-based com- parative and performance study is essential to any bandwidth-based study. We explore the shortcomings of the MAC schemes proposed for ad hoc wireless networks in the context of power awareness herein. In addition, we investigate the potential energy consumption pitfalls of non–power-based and power- based routing schemes. Moreover, we introduce a thorough energy-based performance study of power- aware routing protocols for wireless mobile ad hoc networks. Our energy consumption model is based on an implementation of the IEEE 802.11 physical layer convergence protocol (PLCP) and MAC sublayers. We also present the statistical performance metrics measured by our simulations. 22.1 Introduction Most of the research performed in the ﬁeld of wireless ad hoc networks has focused on the problems of routing and medium access control (MAC). Nevertheless, the limited battery capacity of the mobile devices making up the ad hoc network draws our attention to the importance of power awareness in wireless ad hoc network design. Hence, ad hoc routing and MAC protocols ought to be energy conser- vative. A thorough energy-based comparative and performance study is essential to any bandwidth-based study. The simulation studies carried out for ad hoc networks fall short of examining essential power- based performance metrics, such as average node and network lifetime, energy-based protocol fairness, © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com average dissipated energy per protocol, and standard deviation of the energy dissipated by each individual node. In wireless ad hoc networks, the nonexistence of a centralized authority complicates the problem of medium access control. The centralized medium access regulation procedures, undertaken by base sta- tions in cellular networks, have to be enforced in a distributed, and hence collaborative, fashion by mobile stations in the ad hoc network. Mobile stations may contend simultaneously for medium access. Con- sequently, transmissions of packets from distinct mobile terminals are more prone to overlap, resulting in packet collisions and energy losses. Likewise, the performance of the MAC scheme has a great effect on the performance of the routing method employed and on the energy consumption of the wireless network interface card (NIC). In a multi-hop ad hoc network, or in a wireless LAN operating in independent basic service set (IBSS) mode, wireless stations must always be in standby mode to be able to receive incoming trafﬁc from their neighbors. Due to the nonexistence of a ﬁxed infrastructure, the wireless stations must always be awake. On the contrary, in a wide area or local area cellular environment, wireless nodes may be scheduled to sleep. Base stations and wireless access points, being central controllers, will be in charge of buffering all incoming packets to sleeping nodes. Thus, in a wireless ad hoc network, wireless stations may not sleep. All of the wireless nodes will consume power unnecessarily due to overhearing the transmissions of their neighboring nodes. Although this obviously wastes an extensive amount of the total consumed energy throughout the lifetime of the wireless station, on-demand routing protocols require that nodes remain powered on at all times so as to participate in on-the-ﬂy route setup using route request broadcasts and route reply packets. Besides, table-driven protocols also require constant operation in the active state in order to exchange periodic updates and participate in packet routing. Utilizing a set of clusterheads, or virtual base stations, so as to reduce the idle time power consumption by having a fraction of the nonbackbone nodes sleep at a time has not been studied yet.There is an obvious tradeoff between energy conservation and routing accuracy. As in other cellular systems, the basic service set (BSS) and the extended service set (ESS) modes of operation in wireless LANs enable the mobile terminals to reduce their network interface–related energy consumption. Due to the large channel acquisition overhead, small packets have disproportionately high energy costs. However, in wireless ad hoc networks, other means need to be exercised so as to obtain power-efﬁcient operation. Idle power consumption reﬂects the cost of listening to the wireless channel. This chapter is organized as follows. Section 22.2 surveys the proposed MAC schemes for ad hoc networks and discusses their shortcomings in the context of power awareness. Section 22.3 presents a thorough comparative study of non–power-based and power-based routing schemes for ad hoc networks. In Section 22.4, two proposed application-level energy conservation techniques are described, and their potential for power conservation is examined. Finally, Section 22.5 presents the chapter summary and conclusions. Recommedations for power-efﬁcient protocol design in ad hoc networks are also discussed. 22.2 Medium Access and Energy Conservation The wireless stations in an ad hoc network must cooperatively resolve the problem of simultaneous medium access. Likewise, wireless ad hoc stations must resolve the problem of hidden terminals. A neighbor of the destination that is out of the wireless range of the source may interfere with the transmissions of the source. In Fig. 22.1, H is the hidden terminal; either H or S may transmit to D at a time, otherwise a collision will take place. It is noteworthy that neither the source nor the interferer will be aware of the collision. It is only the lack of a positive acknowlegment (ACK) from the destination that triggers the source to retransmit. Accordingly, the source will be aware of the occurrence of a collision or data corruption. On the other hand, a node that is in range of the sender but not the receiver is called an exposed terminal. Nevertheless, an exposed terminal can transmit at the same time as the sender, without causing a collision to occur. In spite of that, using the traditional carrier sense multiple access (CSMA) scheme, the exposed terminal will defer from accessing the channel. As a result, the capacity of the wireless ad hoc network will be reduced. Hence, energy is wasted groundlessly. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com H S D FIGURE 22.1 The hidden terminal problem in wireless networks. In [1], a scheme that solves the hidden terminal problem using a busy tone is proposed. The protocol, named busy tone multiple access (BTMA), was developed for cellular networks. A busy tone is sent only while the base station is receiving. Thus, transmitters are prevented from accessing the channel. All nodes, including hidden terminals, within the cell site receive the busy tone and back off. Wireless nodes are allowed to transmit only in the absence of busy tones. Once a node detects a busy tone on the secondary channel, it cannot use the data channel even if no signal was detected on it. This implies that a node is allowed to use the data channel even while another node’s transmissions are being heard. Apparently, the BTMA protocol cannot be used in a multi-hop wireless ad hoc network since there are no base stations. In addition, BTMA uses two widely separated channels instead of one and increases the hardware costs and complexity of the NIC. In contrast with BTMA, dual busy tone multiple access (DBTMA) [2] uses two busy tones instead of one. In particular, the hidden terminal problem is resolved using the receive busy tone signal, whereas the exposed terminal problem is overcome by using the transmit busy tone signal. DBTMA wastes battery capacity by forcing the wireless node to continuously sense the medium for the transmit busy tone and the receive busy tone signals. A more energy-efﬁcient MAC protocol would consider turning off the transceiver during standby time to save power. In multiple access collision avoidance (MACA) [3], a node wishing to transmit a data packet to a neighbor ﬁrst sends a request-to-send (RTS) frame to the neighbor. All nodes that receive the RTS are not allowed to transmit. Upon reception of the RTS, the neighbor that the RTS was sent to replies with a clear-to-send (CTS) frame. Also, any node that hears the CTS transmission is prevented from using the channel. Hence, the RTS-CTS message exchange clearly alleviates the hidden terminal problem present in wireless networks. Due to this scheme, data frames are, at least in theory, delivered collision-free. As a result, collisions can only affect control packets. In this case, the IEEE exponential backoff is used to resolve MAC contentions for control packets. In practice, however, collisions may still affect data frames. Nodes that do not properly receive a CTS frame are eligible to use the medium and their transmissions might overlap with those of the source. Hence, this MAC scheme will only decrease the probability of data collisions and the data remains vulnerable to corruption. From the standpoint of energy consump- tion, corrupted CTS frames will result in idle time energy losses for those neighbors that successfully receive the CTS frame. The neighborhood-wide energy loss is proportional to the number of neighbors of the sending station. On the downside also, MACA does not use link-layer positive or even negative ACKs, but rather end-to-end ACKs. It is worthy of notice, however, that the transmission of an RTS frame considerably reduces the energy costs of data collisions. RTS frames result in a favorable reduction in the consumed energy in case of a collision, as compared with the consumed energy in addition to the larger delay due to collision time, if it were the actual data frame for which the RTS is being sent. These delay and energy savings will be achievable in most cases. The use of the RTS frame is nulliﬁed whenever the size of data is comparable to that of the RTS frame. A threshold is used to specify the size of the data frames for which an RTS frame ought to be sent. MACAW [4], on the other hand, uses link layer ACKs to increase data throughput. The IEEE 802.11 MAC and PHY standard [5–7], as in MACAW, utilizes link layer positive ACKs for all unicast trafﬁc. Manifestly, the ACK frame allows the conveyance of fast ACKs, and fast recovery in the event of its absence. ACK frames may only be used with the unicast trafﬁc. ACK frames sent in response to a broadcast message will have a large collision probability and will waste unnecessary energy and network bandwidth. © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com Blocked by CTS Blocked by RTS 1 2 S D 5 4 3 FIGURE 22.2 MACAW suffers from the exposed terminal problem. In a wireless ad hoc network, almost all the proposed routing protocols rely to a large extent on broadcasts. Periodic updates in table-driven schemes, and route discovery, route setup, and route maintenance messages in on-demand protocols, are all examples of network-level broadcasts. An extensive amount of battery capacity would be wasted on ACK transmissions and ACK collisions throughout the wireless network. Apparently, because of the use of explicity ACKs, the exposed terminal problem was reintro- duced, and thus the energy supply of the wireless nodes is gradually depleted by idle time power consumption. If node 1 or node 4 in Fig. 22.2 wants to send a data packet to node 5, it will needlessly wait until the end of the transmission. This contributes to increasing the total idle time energy. In MACA by invitation (MACA-BI) [8], data must be foreseen beforehand by the receivers. Hence, MACA-BI may only be used in periodic and not unpredictable trafﬁc. In the presence of bursty trafﬁc, more efﬁcient protocols have to be used. This is true since it will be impossible for the receivers to predict the instances at which the transmitters will send their data frames. Incorrect predictions will cause all the neighboring nodes to waste an amount of energy that is proportional to the size of the ready-to- receive (RTR) frame, which is sent by the receiver in place of the CTS frame. The sender then responds with the actual data, and the use of the RTS frame is rendered obsolete. In a wireless ad hoc environment, in which nodes are allowed to move freely at all times, anticipation of a source’s transmissions would be extremely difﬁcult due to the unpredictable patterns of contention for medium access by nodes neigh- boring to the source. Therefore, it would still not help the receiver to know the transmission schedule of the sender. Complex application-level and contention prediction schemes would be required. The authors claim that the RTR-DATA dialogue achieves improved performance over MACAW. As previously mentioned, the efﬁciency of this scheme relies on the ability to predict when the sources have data to send. In all the above MAC schemes, nodes will consume most of their battery capacity while in their idle states, that is, while doing nothing. No special MAC-based energy conservation measures were adopted by any of them. In [9], measurements show standby:receive:transmit ratios of 1:1.05:1.4. Ratios of 1:2:2.5 [10] and 1:1.2:1.7 [11] are reported elsewhere. Consider, for example, a single-hop ad hoc network (such as the one shown in Fig. 22.3) consisting of k nodes and a MAC scheme that uses an RTS-CTS-DATA-ACK message exchange sequence. Any transmission by one node will be heard by all the k – 1 other nodes. Consequently, a single successful packet transmission and reception would consume E_RTSTx + (k – 1) E_RTSRx + E_CTSTx + (k – 1)E_RTSRx + E_P-2-P_DataTx + (k – 1)E_P-2-P_DataRx + E_ACKTx + (k – 1) E_ACKRx. This is in addition to the energy dissipated by all k nodes during the defer/back-off period. Unlike other approaches that employ information from above the MAC layer to control radio power, the power-aware multi-access protocol with signaling (PAMAS) [11] is an energy conservative MAC protocol proposed for wireless ad hoc networks. In addition to the primary data channel, PAMAS uses a secondary channel, called the signaling channel, to carry control trafﬁc. The neighbours of the trafﬁc pair are prohibited from using the channel during an ongoing transmission via an RTS-CTS dialogue. A node sets its wireless NIC to sleep mode in case it overhears a neighbor’s transmission. It is not clear if the energy-conserving behavior of PAMAS would negatively affect the end-to-end delay or not. In this © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com 1 3 2 FIGURE 22.3 Wireless NIC energy consumption in a single-hop scenario. scheme, a current receiver can force a neighbor to defer using the medium by sending a busy tone over the signaling channel. This can be used to force the sender of an RTS to defer. All nodes that successfully receive the busy tone are prevented from using the medium for the period of the data transmission over the primary channel. Even if the RTS is detected by the receiver, its CTS transmission will be corrupted by that of the busy tone since they will both be sent simultaneously over the control channel. Since most of the consumed energy in a wireless ad hoc network is attributed to the idle time, PAMAS will obtain high energy-conservation gains only in networks with high trafﬁc loads. In networks with low to modest trafﬁc, the energy-based performance of PAMAS will be close to that of other CSMA protocols. Therefore, nodes running PAMAS will still consume most of their battery capacity while in their idle states. Based on the aforementioned, PAMAS takes no measures so as to reduce idle time energy consumption unless there is an ongoing transmission. 22.3 Routing and Energy Efﬁciency in Wireless Ad Hoc Networks Routing protocols in wireless mobile ad hoc networks can be classiﬁed as table-driven and on-demand. In table-driven routing protocols, all the mobile stations are required to have complete knowledge of the network through their periodic and incremental/triggered updates. Unnecessary periodic updates may have a negative effect on energy conservation. Table-driven routing is also known as proactive routing. Examples of table-driven routing protocols include global state routing (GSR) [12] and destination- sequenced distance vector (DSDV) [13]. Nodes running GSR exchange link states packets (LSPs) with their neighbors. In DSDV, sequence numbers are used to provide a means to enable mobile nodes to distinguish old routes, as a result of mobility, from new ones. Thus, the formation of loops is avoided. On-demand routing requires that routes be built between nodes only as desired by source nodes. Hence, the terms on-demand and reactive can be used interchangeably. On-demand routing has two major components: route discovery and route maintenance. In route discovery, a source uses ﬂooding to acquire a route to its destination. This degrades system-wide energy conservation. The transit nodes, upon receiving a query, learn the path to the source and enter the route in their forwarding tables. The destination node responds using the path traversed by the query. Route maintenance is responsible for reacting to topological changes in the network, and its implementation differs from one algorithm to the other. On-demand protocols include ad hoc on demand distance vector routing (AODV) [14] and dynamic source routing (DSR) [15]. In on-demand protocols, route discovery and maintenance may become inefﬁcient under heavy network load since intermediate nodes will have a higher probability of moving due to the delay in packet transmissions attributed to MAC contention. Hence, routes will also have a higher probability of breaking as a result of mobility. This wastes battery power, and thus the lifetime of the wireless nodes decreases. Moreover, ﬂooding of route request and route reply packets in on-demand © 2003 by CRC Press LLC
Simpo PDF Merge and Split Unregistered Version - http://www.simpopdf.com routing protocols may result in considerable energy drains under a realistic energy consumption model that takes idle time and promiscuous mode power into account. Every station that hears the route request broadcasts will consume an amount of energy proportional to the size of the broadcast packet. In addition, stations that hear a corrupted version of a broadcast packet will still consume some amount of energy. Besides, the simulation studies carried out for table-driven and on-demand routing protocols fall short of providing necessary power-based performance metrics, such as average node and network lifetime, average dissipated energy per protocol, standard deviation of the energy dissipated by each individual node, etc. In cluster-based routing protocols, the nonclusterhead wireless nodes rely on the elected clusterheads to route the data packets to their destinations. Our virtual base stations (VBS)-based routing architecture in [16] is one example. The wireless mobile ad hoc network relies on the wireless mobile infrastructure created by VBS to provide communications between any pair of wireless stations. In VBS routing, only the nodes that form the dynamic infrastructure participate in the process of routing. Hence, those nodes will be more vulnerable than others to unfairly losing their remaining battery capacity. In [17], we propose a novel infrastructure for wireless mobile ad hoc networks. In our proposed architecture, namely, the Power-Aware Virtual Base Stations (PA-VBS) architecture, a mobile node is elected from a set of nominees to act as a base station within its zone based on its residual battery capacity. A wireless station is chosen by one or more stations to act as their PA-VBS based on a couple of energy thresholds. Unlike other clustering schemes, PA-VBS allows the mobile nodes to use their valuable battery power fairly; it does not drain all the battery capacity of the clusterheads since it introduces the concept of service denial, and, hence, it attains fair clustering. Moreover, it balances the load among the wireless nodes regardless of the carried routing load. Consequently, PA-VBS can be utilized as a basis for routing in ad hoc networks. Moreover, PA-VBS can form the cornerstone for the wise distribution of the network load among all the viable paths between a source and destination pair. It is shown that the proposed scheme attains load balancing and fair clustering. PA-VBS is also shown, in our simulation experiments, to react positively, from an energy-aware perspective, to different routing loads. PA-VBS may be utilized for routing and medium access regulation. Any routing protocol may nonetheless be used with it. A number of routing proposals for ad hoc networks took energy conservation into consideration so as to extend the lifetime of the wireless nodes by wisely using their battery capacity. In [18], minimum total power routing (MTPR) is proposed. If the total transmission power for route R is PR, then the route can be obtained from PMTPR = minR∈S PR, where S is the set containing all possible routes. On the downside, this routing approach will in most cases tend to select routes with more hops than others. This is realizable due to the fact that transmission power is inversely proportional to distance [18]. Thus, more energy may be wasted network-wide since a larger number of nodes is now involved in routing, as all nodes that are neighbors to the intermediate nodes will also be affected, unless they were in sleep mode. Minimum battery cost routing (MBCR) [19] utilizes the sume of the inverse of the battery capacity for all intermediate nodes as the metric upon which the route is picked. However, since it is the summation that must be minimal, some hosts may be overused because a route containing nodes with little remaining battery capacity may still be selected. Min-max battery cost routing (MMBCR) [19] treats nodes more fairly from the standpoint of their remaining battery capacity. Smaller remaining battery capacity nodes are avoided and ones with larger battery capacity are favored when choosing a route. The route is found using the equation PMMBCR = minR∈S [ maxn∈R ( 1/B attery_Capacity n) ] However more overall energy will be consumed throughout the network because minimum total trans- mission power routes are no longer favored. In [20], MTPR is used when all the nodes forming a path (note that one path is sufﬁcient) have remaining battery capacity that is above a so-called battery protection threshold, and MMBCR is used if no such path exists. The combined protocol is called conditional max-min battery capacity routing (CMMBCR). The performance evaluation study carried out in [20] does not use a realistic power © 2003 by CRC Press LLC

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn