Pipelined Back Off Scheme for Bandwidth Measurement for MANETS

1. INTRODUCTION

Mobile communication has received tremendous attention during the last few years due the recent advances in mobile computing devices and wireless technology. Wireless networks provide a flexible and instantaneous communication support. Hence, there is an increasing demand towards wireless communication for connecting the Internet, conducting conferences, meetings etc. To satisfy these needs, MANET (Mobile ADHOC NETwork) has emerged and it is on the basis of IEEE 802.11 standard. They can be deployed in areas where it is difficult to lay cables. They can be installed anytime anywhere without any external infrastructure required. Each node of a MANET is the destination of some information packets although it can act as an intermediate node at the same time for other packets to reach their final destination. Nodes are computing and communication devices which can be PDAs (Personal Digital Assistants), laptops, mobile phone or even sensors. As mobile ADHOC networks are being increasingly considered for more and more complex applications, the various QoS attributes for these applications must also be satisfied as a set of pre-determined service requirements. These types of networks are being envisioned to be supported in commercial applications, in addition to increase the use of ADHOC networks for military/police [1, 2, 3]. Routing is one of the main communications functions between two nodes that are not directly connected to each other. The routing protocols plays a significant role to make some critical decisions such as optimal route from source to destination because the mobile nodes operate on battery power. In fact, ADHOC network has the capability of making communications even between two nodes that are not in direct range with each other. It is even possible to exchange the packets between these nodes and forwarded by intermediate nodes. • Network topology can keep changing randomly and rapidly at unpredictable times, due to node movements. • The bandwidth available is limited and may vary due to fading, noise, interference, etc. • Most mobile devices are powered by batteries; thus, energy consumption plays a vital role. • It is necessary to transfer the data with minimal delay so as to consume less power. • QoS support is also required to reduce end-to-end delays and increase the delivery ratio of the packets. • Unfortunately, most of those existing routing protocols endure a number of drawbacks • Scalability problem with growing network size. • Security problem with communications • Performance is only optimal under certain network conditions such as mobility. • Unreliability in delivering packets

Wireless ADHOC networks use a wide range of energy conserving techniques. The PAMAS (Power Aware Multi-Access protocol with Signaling) protocol [4] uses a separate signaling channel to determine when and how long the nodes can power off themselves. In PSM [5] (Power Saving Mode) of 802.11, whenever a node transmits or receives an ATIM (ADHOC Traffic Indication Map) frame over an ATIM window, it has to be in active mode for the whole beacon interval, resulting in a much higher power consumption. In DPSM [5] (Dynamic Power Saving Mechanism) scheme, the ATIM window size is adjusted dynamically based on current network conditions. A NPSM [6] (New Power Saving Mechanism) introduces some parameters indicating the amount of data in each station. Power saving mechanism is hard to be implemented in partially connected like mobile multi-hop network. In On Demand Power Management technique (ODPM) [7], soft state timers are set or refreshed on-demand based on control Topology-Adaptive Network) improves ODPM in which PS (Power Saving) nodes sleep for longer duration and save energy [9]. Rcast [10] technique incorporates randomized overhearing but not randomized retransmission. Quick wake-up mechanism [11] is introduced so that route discovery latency is limited. Random Cast [12] substantially outperforms ODPM, the most efficient method built for multihop networks using on-demand routing algorithms without impacting the overall efficiency of the network. such as PDR. Moreover, it eliminates redundant retransmissions for each transmitted packet, and thus saves more resources. This Random Cast algorithm is part of the DSR routing protocol. In DSR, overhearing tends to bad situation because the idea of a stale route is introduced to all unconditional overheard nodes and wasting energy resource when transmitting, receiving, retransmitting and overhearing DSR transmits control packets which waste channel capacity because redundant rebroadcasts are produced. For energy-efficient methods, therefore, AODV and AOMDV (ADHOC On demand Multipath Distance Vector) routing protocols are proposed. Despite its simplicity, low computational complexity and low overhead processing, AODV has attracted considerable attention.. It is an on demand routing protocol, so a path is discovered only when a source node needs it. This removes regular updates of routing, and propagates only the necessary information to reduce overhead power. In AODV, each node keeps a routing table to monitor routing information received from [13] routing packets. AODV needs a new discovery of the route when a path breaks. Frequent discoveries of the route create a delay because of the latency of path discovery. A multi-path routing protocol is suggested to resolve this problem which gives the alternate path instantly. Through finding and choosing reliable paths it will ensure efficient communication.

Figure 1: Serial Packet Transmission in BEB Serial transmission is followed by Binary Exponential Backoff (BEB). Due to this new serial transmission, channel idle time and overhead

contention consumes bandwidth on the channel. Therefore time spent on channel contention is decreased when collision probability is smaller. But it's hard to do, because channel contention can't start until the current transmission is over. Access to a slot isn't standard either. Just the winners get the opportunity to access the channel again and again. This contributes to impact of channel capture. In a highly contentious network, the probability of collisions increases which degrades the efficiency. The key objective is therefore to apply the pipelining technique to the DCF back off algorithm in order to minimize the overhead collision and increase the usable bandwidth. The concept of pipelining is to divide the total task into many sub-tasks and executing these sub-tasks in parallel. This idea is applied to channel contention procedure of MAC (Medium Access Control) protocol. When two nodes share the channel, the remaining nodes start parallel channel contention procedure for the next packet transmission. Pipelined back-off masks idle time on the channel and reduces the likelihood of collision. It also regulates the number of contending nodes.

Hence to minimize the idle time of channel and overhead associated with collision, implicit pipelined back off algorithm is proposed. In implicit pipelining there is no separate control channel. It implicitly pipelines the channel contention stages as stage1 and stage2. Stage1 functions as a filter to select few nodes to contend for channel in stage2 as shown in figure 2. Figure 3 shows that there are more contending nodes (white and red) in stage1 and less number of pipelined nodes (red) in stage2. Among eight nodes in stage1, five (red) are contending for channel access. Only three nodes successfully enter into stage2. Finally, one can win and start packet transmission. Others may either return to stage1 or stage2 depending on its channel status.

channel utilization.

Let CW1 be the contention window for stage1, bc1 be the backoff counter value. It has CW1min and CW1max. The initial value of CW1 is CW1min. The value of bc1 is randomly selected from the interval [0, CW1]. If bc1 is less than or equal to zero the node becomes the pipelined node and enters stage2. The value of bc1 is updated as follows. After a successful packet transmission bc1 value is reduced by F. The value of F depends on the number of successfully transmitted packets (tp) heard by contending nodes in stage1 i.e. F=2tp - 1. If the value of F is bigger, the probability of becoming a pipelined node is more. Bandwidth is wasted when the channel is idle and no nodes are ready to transmit packets. To avoid this, bc1 is also linearly decreased by 1 after each idle slot. When bc1 reaches zero it enters into stage2. CW1 is updated in the following way. If any pipelined node wins the channel in stage2 and transmits its packets successfully then set CW1 to max [CW1 / 2, CW1min+1], tp to 1 and recalculate bc1 from the interval [0, CW1] and return to stage1. If it loses the channel in stage2, its CW1 is set as min [2*CW1, CW1max+1], then recalculates bc1 from [0, CW1], resets tp to 1 and returns to stage1.

Let CW2 be the contention window of stage2, bc2 be the back off counter, CW2min be the minimum value of contention window and CW2max be the maximum value of contention window. Initial value of CW2 is CW2min for all nodes entering into stage2. Back off counter bc2 is calculated from the interval [0, CW2]. As in stage1 bc2 value is also reduced by 1 after each idle slot. Whenever bc2 reaches zero, transmission is allowed. The pipelined node has to wait for the channel to be idle for DIFS duration before back off procedure starts. If bc2 reaches zero and channel is idle it begins its transmission. Otherwise bc2 is decremented by 1 after each idle slot. Before bc2 reaches zero if a frame is sent by other nodes then this pipelined node loses channel access and returns to stage1. When collision occurs CW2 is doubled and new bc2 is calculated from the interval [0, CW2]. Colliding nodes and pipelined nodes stay in stage2 and the same procedure is repeated. If a pipelined node wins the channel, it transmits the packets successfully, then resets CW1 to max[CW1 / 2, CW1min+1], CW2 to max[CW2 / 2, CW2min+1], tp to 1, calculates bc1 from interval [0, CW1] and goes back to stage1. When a pipelined node loses the channel, it doubles CW1 and reset CW2, tp to 1, then calculates bc1 and goes back to stage1. Thus a node has two ways of reducing bc1. one. This pipelined back off algorithm is given below.

additional field. The addition of QoS to routing protocols helps improve traffic performance on the network. Route discovery procedure of AODV finds the route between sender and receiver that satisfies the bandwidth requirement. This routing protocol specifies the path between source and destination by comparing the bandwidth stored in nodes with the requested bandwidth. Once again source initiates path discovery process in the case of a route failure. Frequent route breaks cause intermediate nodes to drop packets when no immediate alternate path to the destination is available. This impacts the throughput, the distribution ratio of the packets and increases latency. But multipath routing protocol seeks several paths throughout single route discovery process for a destination. In the case of a connection failure, source can turn to an alternate path rather than initiate another route discovery.

The modified pipelined algorithm is also incorporated into a routing protocol called improved link disjoint multipath AODV (AOMDV) to find the routes from given source to destination based on available bandwidth. Improved AOMDV modifies the route discovery mechanism of the base AODV protocol, allowing the discovery of multiple link-disjoint routes for a single source node. In order to discover link-disjunct routes, each node requests only one route to the destination during the route discovery process; furthermore, it retains a queue of the previous hop nodes for each RREQ obtained from a specific neighbor of the source. Consider the node structure in figure 6.5, there are 5 nodes namely A, B, C, D and E. The source node denotes be A, and the destination denotes be E. There are multiple paths [A-B-E, A-C-E, A-D-E] that exist in the network which is shown in figure 5.

message towards the source. Once the source node receives the RERR, it switches its primary path to the next best alternate link-disjoint path. It is designed mainly for highly dynamic ADHOC networks when route breaks and link failures occur frequently.

In this phase, pipelining idea is applied to back off procedure. Separate contention window sizes are maintained for each stage. Results are generated based on time, different number of nodes and various contention window sizes. The chosen values for CWmin and CWmax for stage1 are 31 and 1023 respectively. Range of CW values for stage2 are 15-1023.

This algorithm is tested with 125 nodes. Figure 6 shows the throughput performance. It is compared with ABM and pipelined schemes. The proposed algorithm increases throughput performance. Number of packets received is significantly higher in pipelined scheme than that of ABM. Figure 7 shows that the packet delivery ratio for pipelined scheme is better compared to ABM. Thus packet loss is reduced in pipelined scheme. End-to-end delay varies up to 2.0ms in ABM where as in multipath pipelined ABM, it reduces to 1.62ms which is shown in figure 8. Figure 9 shows that energy consumption is much lower than ABM. Energy consumption is reduced by minimizing collisions. Also energy is conserved by reducing the number of redundant packet transmissions. Figure 10 shows number of packets received by the destinations. Bandwidth consumption is reduced about 12% than ABM as shown in figure 11. This leads to a more significant effect of the pipelined algorithm.

This algorithm is also tested for different number of nodes. The experiment is run for 25, 50, 75, 100 nodes. The performance metrics are compared with ABM-AODV. Figure 6.12 shows throughput performance. ABM-AODV has closest performance to pipelined ABM when the number of nodes is less, where ABM obtains 24.3 kbps throughput and pipelined ABM achieves 24.5 kbps throughput. When number of nodes is increased pipelined ABM achieves 23.6 kbps throughput and ABM gets 23.9 kbps throughput. This is due to the fact that packet drop rate is more in ABM. Figure 13 shows that PDR for pipelined ABM is better compared to ABM. PDR for ABM is 93.9% while for pipelined ABM is 95.9% for 100 nodes. Pipelined ABM not only improves throughput but also reduces end-to-end delay and energy consumption. End-to-end delay of a packet includes the medium waiting time and the time spent on packet retransmission. In pipelined ABM more number of retransmissions is avoided due to reduced collision. Medium waiting time is also decreased. It has less end-to-end delay for large number of nodes. When n=100, delay for pipelined ABM is 1.69ms while ABM has 2.1ms which is shown in figure 14. As number of retransmissions is reduced, pipelined ABM consumes less energy. Initially, 1000 joules is assigned to every node. Pipelined ABM consumes 218 joules but ABM consumes more energy which is 237 joules as shown in figure 15. Number of packets dropped in pipelined ABM is less compared to ABM. This is because of reduced collision probability. Figure 16 shows the bandwidth consumed is less to achieve maximum throughput for pipelined ABM.

Performance analysis of pipelined ABM is carried out by varying contention window sizes in stage1. This algorithm is tested with 50 nodes. Simulation results present throughput, delay, energy, PDR for different values of CW parameters. It is observed from the graph that the optimal range of CW is 31-1023. This algorithm is tested by varying contention window ranges such as 31-1023, 127-1023 and 511-4093 and keeping window size for stage2 as 15-1023. This is because number of contending nodes is more in stage1 than number of pipelined nodes in stage2. The performance metrics with respect to number of nodes, speed and pause time are shown for three sets of contention window sizes. Figure 17 shows that the throughput for 31-1023 window range is better than the other CW ranges.

Pipelined Back off Algorithm with AOMDV discussed in this chapter helps to overcome the problem of channel capture effect. Pipelined back off stages consume minimum bandwidth which is negligible. QoS routes are traced with the help of Link Disjoint AOMDV with bandwidth as an additional field. In case of a link failure, AOMDV provides alternate path immediately to provide end-to-end reliability. Finding multiple routes is beneficial in mobile wireless networks where routes are disconnected frequently because of mobility and poor link quality. This work analyses the performance of QoS metrics for different number of nodes, various contention window sizes and network traffic.

1. Grunde Eikenes and Ole Erik Grostøl (2003). Management of Quality of Service and other functions in mobile Ad Hoc networks. Master‘s Thesis in Information and Communication Technology Agder University College Grimstad. 2. J. N. Al-Karaki and A. E. Kamal (2004). Quality of service routing in mobile ad hoc networks: Current and future trends in 3. Abdullah M.S. Alkahtani, M.E. Woodward and K. Al-Begin (2003). An Overview of Quality of Service (QoS) and QoS Routing in Communication Network PGnet. 4. Suresh Singh and C. S. Raghavendra. PAMAS - power aware multi- access protocol with signaling for ad hoc networks. In MOBICOM '98, October 1998. 5. Eun-Sun Jung and Nitin H. Vaidya (2002). Energy Efficient MAC Protocol for Wireless LANs. IEEE INFOCOM 2002, New York, U.S.A. 6. Eun-Sun Jung and Nitin Vaidya (2002). A Power Saving MAC Protocol for Wireless Networks. Technical Report. 7. R. Zheng and R. Kravets (2003). On-Demand Power Management for Ad Hoc Networks. In Proc. IEEE INFOCOM, pp. 481-491. 8. Z. Li and B. Li (2005). Probabilistic Power Management for Wireless ADHOC Networks. Mobile Networks and Applications, Vol. 10, No. 5, pp. 771-782. 9. C. Sengul and R. Kravets (2005). Conserving Energy with On-Demand Topology Management. Proc. Second IEEE Int'l Conf. Mobile Ad Hoc and Sensor Systems (MASS '05), pp. 10-19, 2005. 10. S. Lim, C. Yu and C. Das (2005). Rcast: A Randomized Communication Scheme for Improving Energy Efficiency in Mobile Ad Hoc Networks. Proc. 25th IEEE Int'l Conf. Distributed Computing Systems (ICDCS '05), pp. 123-132. 11. J. Dorsey and D. Siewiorek (2004). 802.11 Power Management Extensions to Monarch ns. Technical Report CMU-CS-04-183, School of Computer Science, Carnegie Mellon University. 12. S. Lim, Chansu Yu and Chita R. Das (2009). Random Cast: Energy- Efficient Communication Scheme for Mobile Ad Hoc Networks. IEEE Transactions on Mobile Computing, Vol. 8, No. 8, pp. 1039- 1051, August 2009. 13. S. Motegi and H. Horiuchi (2004). AODV-based multipath routing protocol for mobile ad hoc networks. IEICE

Research Scholar, Department of Computer Science, Sri Satya Sai University of Technology & Medical Sciences, Sehore, M.P.