A Cognitive Improved Hierarchical AODV Routing Protocol for Cognitive Wireless Mesh Network

INTRODUCTION

A recent report by the FCC challenges for the first time the common belief of spectrum scarcity by indicating that at any given time and in any geographic locality, less than 10% of the available spectrum is being utilized. To exploit underutilized portion of the spectrum (a.k.a, white spaces, spectrum holes, etc.), the report advocates the need for a new generation of smart, programmable radios that are capable of interference sensing, environment learning and dynamic spectrum access. These so-called Cognitive Radios (CRs) have recently been the forefront of wireless communication research. They promise to provide reliable and programmable wireless communications as well as adaptive sharing of the radio spectrum.

Much of the research on CR Networks (CRNs) protocols has dealt with the MAC and physical layers (Zhao et al., 2007; Su and Zhang, 2007). However, due to the special situations under the cognitive radio environment, the research on routing protocol should be taken into account. In the cognitive radio, the secondary cognitive terminals transmit the signals on the frequency band assigned to the primary system by sensing the radio frequency band.

Wireless Mesh Networks (WMNs) (Bruno et al., 2005) is also an emerging technology which is being adopted as the wireless internetworking solution for the near future. Characteristics of WMN such as rapid deployment and self configuration make WMN suitable for transient on-demand network deployment scenarios. The form of mesh network that is of most commercial interest is often called hybrid mesh network (Akyildiz et al., 2005).

Compared to MANETs, nodes in WMNs have relatively fixed positions and communicate to the Internet through one or more gateways. Although traditional MANETs routing algorithms can be used in WMNs, their performance is typically less than ideal. The problem is that such algorithms make assumptions (such as very high node mobility and no infrastructure) which are no longer true in WMNs and can have a significant impact on the routing performance in mesh environments. A number of routing protocols have been proposed for WMNs. Proactive protocols propagate topology information periodically and find routes continuously, while reactive protocols such as Dynamic Source Routing (DSR) protocol (Johnson and Maltz, 1996) and Ad-hoc On-demand Distance Vector routing protocol (AODV) (Perkins et al., 2003) find routes on demand. Generally, reactive protocols outperform proactive protocols in terms of packet delivery ratio, routing overhead and energy efficiency. However, in flat routing protocols, a route is maintained at the grain of the whole path, i.e., from the source to the destination. This approach works well for small networks where routes are typically short. When the network grows, routes become longer and break more often. If routes are still maintained at the grain of the whole path, the routing overhead will be high because new routes are discovered and discarded frequently. The problems mentioned above are inherent in flat routing protocols.

Hierarchical routing protocols are developed to solve the problems in flat routing protocols. In these protocols, the network is divided into groups and a subset of nodes is assigned special functionalities, typically, coordinating roles. Clusterhead-Gateway Switch Routing (CGSR) (Chiang et al., 1997) is a typical hierarchical routing protocol. CGSR divides the network into clusters that are circular regions with the radius of a predefined hop count. After the network is divided into clusters, local route maintenance activities will only affect a few neighboring clusters, while other clusters remain untouched. Way Point Routing (WPR) (Bai and Sighal, 2006) is an improved hierarchical routing protocol, which maintains a hierarchy only for active routes and a number of intermediate nodes on a route are selected as way points and the route is divided into segments by the way points. Though achieving the scalability, hierarchical routing protocols always have very complex algorithms which make it difficult to apply. Furthermore, these algorithms are not suitable for utilizing for the cognitive radio under the interference from the primary system. Therefore, the basic routing technique is not effective for applying to the cognitive mesh networks.

In this study, we propose a novel routing algorithm for cognitive mesh network under the fluctuated interference from the primary system. The novel routing algorithm aims to provide a lightweight hierarchical based AODV. As WMNs itself is a hybrid network solution among MANETs and static networks, we make different parts of the hybrid WMNs’ nodes with the different functions and then divided them into clusters within hop count (just as CGSR) according to the different functions. Inside the clusters, there are no cluster head anymore; instead we define the special nodes named way point (just as WPR). Outside the clusters, we still use AODV for routing. On the concept of our strategy, we combine CGSR and WPR in AODV as an improved hierarchical routing protocol. Furthermore, the routing protocol also considers the special situation under the cognitive radio environment. We term this protocol as a cognitive improved hierarchical AODV routing protocol (CIH-AODV).

The traditional AODV routing algorithm is based on the flooding method for establishing the route from the source node by using a route request packet (RREQ) and a route reply packet (RREP). In this method, one route with minimum-hop is established before the data transmission. However, in the cognitive networks, the route is often interfered because the primary users can transmit the signals in the same frequency band. Due to the high fluctuation on available frequency bands, the classic flooding method will lead to congestion in the network without taking advantage of the characteristics of mesh network. In order to solve these problems, we adopt Common Control Channel (CCC) (Akyildiz et al., 2009) and abandon the flooding method. The Common Control Channel (CCC) supports the transmission coordination and spectrum related information exchange between the CR users. The operation of the CCC is different from the data transmission over the licensed band in the following aspects:

THE CIH-AODV ROUTING PROTOCOL IN COGNITIVE MESH NETWORK

Motivation: WMNs was developed for reliable data communication and load balancing. The limitations urge a need of a routing protocol specifically tailored for them. In AODV, the route search procedure may involve significant control traffic due to global flooding. This, together with the long setup delay, may make pure AODV routing less suitable for real-time traffic. As the mobility of many nodes in WMNs is low, if we could decrease the active nodes during the route discovery phase by dividing the nodes into clusters, the delay before sending a packet may be shorten and the scalability problem also be solved because new nodes are more easy to join together due to the cluster mechanism.

The design goal of CIH-AODV routing protocol is to improve the scaling potential of AODV when keeping the merits of it and making it suitable for the cognitive radio environment. The main features of CIH-AODV include:

CIH-AODV routing scheme
Route discovery: Our proposed mechanism is for hybrid wireless Mesh networks. Some assumptions are as following: first of all, as there are many static nodes in the networks, we define them as way point nodes (WP), while other nodes are termed cluster member nodes (CM). Second, as to the CR ability of each node, each node can individually detect its Spectrum Opportunity (SOP) (Xin et al., 2005), a set of frequency bands currently unoccupied and available. Third, at the beginning of the route discovery, we suppose there is an initialized cluster

The WP nodes are function nodes in a cluster. They have the same characteristic as that in traditional AODV but maintain a Cluster Member List Table (CMLT). In every cluster, there are two WP nodes named start-WP and end-WP. Two neighboring clusters share a common WP node, which acts as the end-WP node of the upstream cluster and the start-WP node of the downstream cluster. What we should pay attention to is that the two WP nodes can connect directly if they are in hop count length. In the CMLT, it includes the number of the cluster members and their fresh level. While the cluster member is used once, the number that initialized as zero add one. The value of fresh level is used to determine the freshest path used in cluster, which just like the sequence number used in entire network in AODV to determine the freshest route to a destination. We define the mechanism above as fresh route detection.

The cluster member nodes are normal nodes worked as following: When a normal node(source node) requires a route for data forwarding, it sends small Hello packets to its hop count neighbor nodes. WP nodes receive the message and then check the node whether in the CMLT or not. If not, feed back a Reactive Message (RM) to invite the node join into the cluster, while the node receives the start-WP node and the end-WP node’s RM respectively, it send Join Request (JR) and join into the cluster. At the same time, all the new CMs must send the information about their available channels (those not used by primary users) to the WP. Then the source node establishes the route as follows:

Fig. 1:	Route discovery

Figure 1 gives an example of source node e how to find the route to destination node d. We select nodes S, A, B and C as WP nodes and the source node S is just included. Nodes from d to l are CM nodes and the destination node d is included. A cluster can be simply identified by its start and end WP nodes. In Fig. 1, there are three clusters: S-e/f-A, A-g/h/i-B and B-j/k/l/d-C. To distinguish WP nodes from CM nodes, we use uppercase letters to label WP nodes and lowercase letters to CM nodes. Following the route discovery schemes above, a route can be found as: e-A-h-B-d.

Route maintenance: Due to the dynamic characters of CM nodes, links on a route may fail. Route maintenance is the mechanism to handle route breaks. CIH-AODV extends many features from AODV for route maintenance, for example, use RERR message to inform the nodes affected by the link breakage. In addition to, CIH-AODV add some cluster related maintenance operations, including fresh route detection and local route repair. Fresh route detection is not only used for route discovery but also for route maintenance. When a link failure occurs, the hop count WP node checks its CMLT firstly and then finds the freshest path except the break one.

If this way can not work because of the update of the CMLT, local repair will be the second level of route repair. The update of the CMLT means that the old cluster may be changed, so local route repair is tried and works in the range of one cluster (Perkins et al., 2003). During the period from initiating the route repair to know the result of the repair, the initiator buffers data packets that it receives using the route need repair. If the repair succeeds, the initiator transmits the buffered data packets, otherwise, it tries typical repair in AODV and keeps buffering undeliverable data packets. The local route repair tries to establish a new path between the start and the end WP nodes of a broken cluster. If it succeeds, the WP nodes on the repaired route will not changed and the source node will not be notified because data packets can be forwarded along the same WP nodes. However, because the network is under the cognitive radio environment, while the PUs emerge suddenly, some frequency bands will not be used. The link of the path also faces failure. In this situation, the proposed route repair procedure is shown below:

Fig. 2:	Route repair

Figure 2 shows an example in which the original path for cluster A-g/h/i-B is A-h-B and the link between h and B breaks. The link breaks for the mobility of nodes in Fig. 2a and for the interference from primary user in Fig. 2b. In Fig. 2a, as fresh route detection succeeds and the new path for cluster A-g/h/i-B is A-g-B. So, a new route is established as e-A-g-B-d. In Fig. 2b, as a new frequency channel is determined, the original path for cluster A-g/h/i-B is recovered.

PERFORMANCE EVALUATION

Simulation: The simulations are performed using Network Simulator 2 (NS-2) (Fall and Vardhan, 2001), particularly popular in the wireless networking community. The performance of CIH-AODV is evaluated by comparing it with AODV protocol in the same condition. Meanwhile, we also evaluate the performance of CIH-AODV under the cognitive radio environment.

In our simulation, unless specified otherwise, we assume that the traffic sources are Constant Bit Rate (CBR). MAC protocol is the IEEE standard 802.11 Distributed Coordination Function (DCF) (Committee, 1997).

The source-destination pairs are spread randomly over the network. Initially the nodes are evenly distributed throughout the simulation area. Half of nodes are static, half of nodes move with a random mobility model. For mobile nodes, velocities range from 0 and 20 m sec^-1, while the pause time is set to 30 sec. The data packet size is 512 bytes. Each node is equipped with a single half-duplex cognitive radio for transmission and a single half-duplex normal radio for control transmission. The available spectrum is divided into 10 channels. Each cognitive radio can access one channel with channel switching delay of 80us at a time, while primary users can claim multiple channels simultaneously. Both the cognitive and control radios are configured for a data rate of 12 Mbps. In our simulation, we consider two situations. First, the network is not under the cognitive radio environment. We evaluate the performance of IH-AODV protocol compared with traditional AODV. Second, the network is under the cognitive radio environment. We evaluate whether the performance of protocol is suitable for the cognitive radio.

Under the normal radio environment: We conducted two sets of scenarios. First, with the number of CBR flows as 20 constantly, the nodes in the network increase from 100 to 1000 gradually. The size and the area are selected (as is shown in Table 1) so that the nodes density is approximately constant, which would properly reflect the scalability of routing protocols. Second, we studied the performance of the protocols when the CBR flows from 20 to 60 in networks with 400 nodes. Each simulation was run for duration of 900 sec. Each sample data we use is an average of 5 simulations. We evaluated three performance metrics:

Table 1:	Network sizes and network areas

Under the cognitive radio environment: In this situation, we kept the basic scenario, but placed three primary users on the grid and let them moving randomly. While one of them occupy channels 1 to 6 and other primary users occupy channels 5 to 10. In the last situation, due to the absence, there is no channel switch. However, in this situation, because of the presence of primary user, the spectrum availability will be impactive. We evaluate two performance metrics:

Results and analysis
Under the normal radio environment: In the first scenario, we studied the scalability of the protocols.

The results are shown in Fig. 3. As shown in Fig. 3a, both CIH-AODV and AODV show high packet delivery ratio even for networks with 1000 nodes. But CIH-AODV consistently delivers about 1-2% more data packets than AODV.

Fig. 3:	(a) Packet delivery ratio, (b) average control packets and (c) end-to-end delay

Fig. 4:	(a) Packet delivery ratio, (b) average control packets and (c) end-to-end delay

CIH-AODV maintains routes hierarchically, an additional CMLT and repairs a broken route locally. Thus, an active route in CIH-AODV usually lasts longer and more data packets can be delivered.

Figure 3b shows the route overhead of the comparing route protocols. After the nodes are more than 200, the overhead of AODV increase rapidly. CIH-AODV has very light overhead as it use the WP routing hierarchy. WP enables the localization of the route maintenance activities. The low control overhead is critical for CIH-AODV to scale to large WMNs.

The end-to-end delay is shown in Fig. 3c. While, the nodes are less than 400 nodes, the delay of CIH-AODV is a little more than AODV because of the cluster forming. As the network becomes large the situation is changed. CIH-AODV shows a smaller end-to-end delay in large network because the fresh route detect and route repair mechanism recovers a broken route quickly and data packets do not have to wait for another round of route discovery before transmission.

The above results show that CIH-AODV indeed incorporates good aspects of AODV and hierarchy and exhibits promising performance, especially in medium to large networks.

In the second scenario, Fig. 4a-c show comparisons between the route protocols on the basis of three metrics, using different number of CBR flows mentioned before. Fig. 4a is the comparison of packet delivery ratio. In AODV, the value drops as the number of flows increases because the network becomes more congested. Nevertheless, CIH-AODV still works well.

Figure 4b shows the average control overhead. We observe that CIH-AODV can save a little control packets per flow compared to AODV. This is mainly because of the cost of CMLT and cluster maintains in CIH-AODV.

Figure 4c shows the comparison between the route protocols on the basis of end-to-end delay. CIH-AODV is much better than AODV while the flows increase. The reason is that it has CMLT, which makes a node easier to find a route than AODV before transmitting packets. However, the establishment of the cluster and CMLT may cause more delay.

Fig. 5:	(a) Packet dropped ratio and (b) end-to-end delays

The above results show that CIH-AODV works well when the network becomes congested.

Under the cognitive radio environment: Figure 5a shows the packet loss rate between the traditional AODV and CIH-AODV under the cognitive radio environment. We observe that the packet dropped rate reduced by switching channel, while the link status changed.

Figure 5b shows the comparison of end-to-end delay. It can be seen from the figure that the end-to-end delay of AODV increases sharply with 4 links failed. However, the end-to-end delay of CIH-AODV remains at a certain level. This is because that the CIH-AODV can switch the channel over the available channels and the switching delay is small.