AODV with intelligent priority flow scheme for multi-hop ad hoc networks

With the advancement of wireless technology, people have witnessed an ever-increasing popularity of wireless networks in recent years. Wireless local area networks, or Wi-Fi hotspots, have been widely deployed in cities, college campus, airports, coffee bars, conference halls, hotels, and many other public places. Nevertheless, wireless local area network is limited to one-hop communication between clients and access points. It restricts wireless access to a small range. If communication devices are allowed to forward packets for others, a multi-hop ad hoc network can be formed, and the range of wireless access to Wi-Fi hotspots can be significantly extended. This kind of wireless multi-hop communication could be used in many applications, such as environmental monitoring and health care.

In multi-hop ad hoc network, nodes communicate with each other using wireless links of each node. Each node acts as a host as well as a router and forwards data packets for other nodes. A central challenge in the design of multi-hop ad hoc networks is the development of dynamic routing protocol that can efficiently find routes between two communication nodes. Many protocols, such as dynamic destination sequenced distance vector (DSDV) [1], dynamic source routing (DSR) [2], ad hoc on-demand distance vector (AODV) [3], temporally ordered routing algorithm (TORA) [4], and zone routing protocol (ZRP) [5], etc, have been proposed. However, we focus on another challenge in the efficiency of data transmission for multi-hop ad hoc networks. Wireless media is a shared and scarce resource in an ad hoc network. How to efficiently control the access to this shared media becomes an important and complicated issue. For multi-hop ad hoc networks, nodes have to cooperate to forward each other’s packets through the network. Due to the contention for the shared channel, the throughput of each single node is limited not only by channel capacity itself but also by the transmissions in neighborhood. That is to say, the transmission at each hop has to contend the channel with upstream and downstream nodes. This effect results in congestion at some nodes along the routing path and seriously limits the performances of multi-hop ad hoc networks. Li et al. [6] have found that the IEEE 802.11 mechanisms fail to achieve the optimal scheduling for all multi-hop flows, and its performance greatly degrades under the chain topology with heavy load.

To alleviate the congestion, several dynamic load balancing algorithms were proposed. Lee and Gerla presented a dynamic load-aware routing algorithm (DLAR) [7] which uses the traffic load of the intermediate nodes as route selection criterion. It periodically monitors the status of active data sessions and dynamically reconfigures the routes that are being congested. Lee and Campbell presented a hotspot mitigation protocol (HMP) [8], where hotspots represent transient but highly congested regions. HMP balances resource consumption among neighboring nodes by suppressing new route requests and controlling TCP flows rate. These solutions focus only on routing algorithms and do not fully consider the MAC layer contentions which result in different problems of channel access at the neighboring nodes. Recently, intelligent algorithms, such as genetic algorithm (GA), ant colony optimization (ACO), and particle swarm optimization (PSO), have shown good performances in various problems [9‐13]. A flexible genetic algorithm for optimizing channel assignment in mesh wireless networks was proposed by Vanhatupa et al. [10]. In Alba [11], a specialized cellular multi-objective genetic algorithm was used for finding an optimal broadcasting strategy in urban mobile ad hoc network (MANET). ACO has been successfully adapted for implementing new routing protocols for MANET [12]. Huang et al. [13] proposed a new routing protocol based on a PSO to make scheduling decisions for reducing the packet loss rate. In this paper, AODV with intelligent priority flow scheme for multi-hop ad hoc networks is proposed. In the proposed approach, ABCA will be used to calculate the contention window size of the nodes along the routing path. It can avoid data collision in MAC layer, and can result in getting better performances of data transmission.

The remaining part of this paper is organized as follows. In Sect. 2, we briefly review AODV protocol, IEEE 802.11 DCF standard, and ABCA algorithm. Section 3 introduces the proposed AODV with intelligent priority flow scheme. The simulation results are presented in Sect. 4. Finally, we conclude this paper in Sect. 5.

In this section, an overview of two related protocols and ACBA algorithm is given. As our target network is a multi-hop ad hoc network, AODV routing protocol is adopted to find routing path in the network layer, IEEE 802.11 distributed coordination function (DCF) is used as the medium-access control protocol in the MAC layer, and ACBA algorithm uses to calculate the contention window size of the nodes along the routing path.

In this paper, AODV with the intelligent priority flow scheme for multi-hop ad hoc networks is proposed. In the proposed approach, all the routing algorithms (e.g., route discovering and path maintaining) are set as the same as original AODV protocol in network layer. In the IEEE 802.11 DCF standard, the contention window (CW) is an important variable to determine back-off time of each node. Thereafter, ABCA is used to calculate the CW size for each node along the routing paths. Then, the CW size is descending from source node to destination node. This strategy of the proposed approach could achieve optimal packet scheduling, avoid data collision in MAC layer, and result in getting better performances of data transmission in network layer. In AODV with the intelligent priority flow scheme, the CW and back-off time are performed as follows: L total hop count of routing path, D the remain hop count of AODV routing table, n the number of data retransmitted times.If (transmit successfully), then reset CW = CWMin

Descending CW from source node to destination node

Back-off time = int [CW * random()] * slot time

random(): a random real number between 0 and 1

int [expression]: the lowest integer for expression

where \(\alpha \) is the upper bound integer value determined by ABCA; \({\varvec{\beta }}\) is the lower bound integer (1 \(\le {\varvec{\beta }} \le \)10) for CWMin determined by ABCA; \(\gamma \) is a descending integer (1 \(\le \gamma \le \)10) for CW determined by ABCA.

Thereafter, ABCA is performed to find the best values for above three parameters (\(\alpha , {\varvec{\beta }},\gamma \)). First, the initial population and solutions for all employed bees are generated in ABCA. The employed bee goes to a solution and determines a neighbor source, as shown in Eq. (2), then evaluates its quality of solution. Each onlooker watches the dance of employed bees and chooses one of their sources, and then goes to that source, as shown in Eq. (3). Abandoned food sources are determined and are replaced with the new food sources discovered by scouts, as shown in Eq. (4). The maximum number of iterations (MNI) is used to control the number of iterations as the termination criterion. ABCA will be repeated until the output of the value of fitness reaches the pre-defined threshold value or the number of iterations meets MNI. Two metrics of performance are evaluated to illustrate as the value of fitness. One is packet delivery ratio, and the other is end-to-end throughput. Packet delivery ratio (PDR) is defined as the percentage of data packets that can received by the destination. End-to-end throughput (ETEH) is defined as total amount of data that can be received by the destination in a given time interval. Frame cost of destination per data (FCDPD) is defined as the ratio of total frames, including RTS, CTS, ACK, RREQ, RERR, RREP, and CBR data, delivered by the source, to the number of CBR data received successfully by destination. RREQ number of route discovery (RREQN) is defined as how many number of RREQ packets were sent by the source node during data transmission. RERR number of route maintenance (RERRN) is defined as how many number of RERR packets were received by the source node during data transmission. In the proposed AODV with the intelligent priority flow scheme, the value of fitness is set as follows:

The simulation was implemented under the network simulator NS2 2.29, which can simulate a layered network protocol stack and wireless channel [17]. The simulation scenario is conducted in a 7-nodes chain topology of multi-hop ad hoc networks, as shown in Fig. 3. The distance between neighboring nodes is 200 m, which allows a node to connect only to its neighboring nodes. The same distance between neighboring nodes ensures that the nodes act equally in the simulation. The number of employed bees and onlooker bees were set to 10. The MNI was set to 2000. The IEEE 802.11 DCF is used as the medium-access control protocol. All nodes communicate with identical, half duplex, and wireless radios that have a bandwidth of 1 Mbps, an effective transmission radius of 250 m and the interfering range of 500 m. Each node has a queue called interface queue (IFQ) for packets waiting to be transmitted by the network interface, which holds up to 10 packets and is managed in a drop tail fashion. The two-ray ground reflection model is used for propagation. AODV routing protocol is adopted to find routing path in network layer. In this paper, constant bit rate (CBR) traffic is used to simulate the UDP performance. Every CBR packet size is 1200 bytes, and the packet sending rate is varied in each run to change the offered traffic load (0.01, 0.2, 0.3, and 0.5 Mbps) in the network. To demonstrate the performance of the proposed approach in a fair comparison, ABCA is performed to find the best values for three parameters \((\alpha ,\beta ,\gamma )\) first. Thereafter, all compared simulations take 100 s. Simulation will evaluate and compare the performances between the original AODV base on the IEEE 802.11 DCF and our proposed scheme (AODV-SPF). In the following figures, our scheme will be referred to as basic access with priority and RTS/CTS with priority relative to the traditional mechanisms of the IEEE 802.11.

A. End-to-end throughput

Figure 4 shows that our scheme improves the end-to-end throughput of AODV for both basic access and RTS/CTS mechanisms under heavy traffic load. The throughput of CBR packet based on basic access is little higher than that for priority flow mechanism under light traffic load, but the delivery ratio is less than that for priority flow, as shown in Fig. 5. It means that the traditional basic access mechanism sends more CBR packets than our scheme, and some of them are lost. The throughput of CBR packet with priority flow is much higher and more stable than that for RTS/CTS mechanism over all traffic loads, and the delivery ratio is obviously larger than that for RTS/CTS, as shown in Fig. 6.

B. Packet delivery ratio

Figure 5 shows that the AODV-SPF has much higher packet delivery ratio than original AODV for both basic and RTS/CTS mechanisms independent of traffic load. The packet delivery ratio of CBR data for our scheme is much higher than that for basic access mechanism all the time without increasing the overhead cost of CBR data, as shown in Fig. 6. Moreover, it is almost approach to 100 transmission for RTS/CTS. That is to say, both kinds of priority flow mechanisms may suffer less collision than the traditional mechanisms the whole time while transmitting CBR packet.

C. Normalized control overhead

Figure 6 shows that AODV-SPF keeps normalized control overhead small and stable, and has the difference of frame cost between source and destination much smaller than that of original AODV. This verifies that our scheme reduces a lot of collisions in MAC layer, and saves unsuccessful RTS/CTS negotiations or RREQ, RREP, and REPP route control packets. The original AODV has a much higher normalized control overhead, which increases rapidly with the offered load for multi-hop flow. This implies that the AODV-SPF is a better choice than the traditional schemes for the multi-hop flow in the shared wireless channel environment and is scalable for larger network.

D. Probability of link failure

Figures 7 and 8 show that the AODV-SPF has absolutely smaller number of route control packets, e.g., RREQ and RERR, than original AODV based on the IEEE 802.11. In Fig. 8, the maximum number of RREQ sent by source node is about 5 packets in AODV-SPF, but 190 packets in original AODV based on RTS/CTS, and about 35 packets based on basic access mechanism. Relatively, as shown in Fig. 8, the maximum number of RERR received by source node is about 4 packets in our scheme, but 163 packets in original AODV based on RTS/CTS, and about 16 packets based on basic access mechanism. Based on the above description, we prove that our scheme is superior to the original AODV.

In this paper, we discuss the intra-flow contention which causes poor performance of the IEEE 802.11 DCF MAC protocol in multi-hop ad hoc network. To alleviate this contention, we propose a framework of media access scheduling algorithm based on the hop count number that packets have traversed. In the proposed approach, these best values of parameters are performed by ABCA. Simulation results verify that the proposed AODV with the intelligent priority flow scheme could achieve obviously better performance of data transmission, such as more stable and higher throughput, better packet delivery ratio, lower routing load, and decreasing the control packet number of RREQ and RERR than the original AODV. In view of the above descriptions, it is shown that the proposed approach is superior to original AODV.