Routing is the main research issue in the development of Wireless Mesh Networks (WMNs). Many of the routing approaches have been borrowed from Mobile Ad hoc Networks (MANETs) to achieve routing solutions in WMNs but are not ideal or optimal and do not utilize the characteristics of WMNs to fulfill their benefits. Moreover, these approaches dont take into account the cognitive radio environment. In this study, we propose an improved hierarchical AODV routing protocol based on cognitive radio (CIH-AODV) for cognitive wireless mesh network, which exhibits better scalability and performance in the network and incurs less routing overhead for finding alternate routes when a route is lost. Furthermore, we present a novel technique for CIH-AODV termed fresh route detection which is designed to support cognitive radio. We make comparison between AODV and CIH-AODV in our simulation using NS-2. Simulation results show that the metrics of CIH-AODV are better than or comparable to AODV in hybrid WMNs and the protocol is suitable for the cognitive radio environment.
PDF Abstract XML References Citation
How to cite this article
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:
|•||CR users may optimize their channel use over a number of constraints, such as channel quality, access time, observed Primary Users (PUs) activity, network load. However, these parameters are not known to the CR users in advance at the start of the network operation|
|•||Spectrum bands that are currently used for data transfer may suddenly become unavailable when a PU appears. While, the data communication is interrupted, the affected CR users need to coordinate a new spectrum that does not interfere with the PUs on either end of the link. The control information used in the new spectrum selection must be sent reliably, so the CCC is always needed|
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:
|•||Fresh route detection: This is a novel technique for CIH-AODV. It designs for quick routing discovery for the nodes which join the cluster and can increase speed and efficiency of the route discovery. During the route maintenance, it is also useful. The details will be presented in the following sections|
|•||Coexist with AODV: AODV is a widely accepted protocol. There are several implements version of AODV reported. One of the important principles in designing CIH-AODV is the coexistence with AODV. It means nodes that implement AODV protocol can work collaboratively with nodes that implement our protocol in the same network. To achieve this, we keep all AODV route control packets and add some new control packets as needed. We mark the nodes that are static in order to minimize the discovery delay|
|•||Local route repair: A local repair mechanism optimized the AODV as described by Perkins et al. (2003). However, it is suitable for situations where link failures occur near the destination. As a network growing, routes between sources and destinations become longer, this way could not work well anymore. CIH-AODV let the nodes upstream of the break link perform a local repair instead of issuing the RERR. If the local repair is successful, a RREP will be returned either by the destination or by a node with a valid route to the destination. In the event that a RREP is not returned, the local repair is not successful and a RERR message is sent to the source node|
|•||Suitable for the cognitive radio: Spectrum resources are pre-allocated and fixed in traditional wireless communications. The license based on static spectrum policy results in poor utilization and spectrum holes. One promising solution is Cognitive Radio Technology, which enable unlicensed users to sense, identify and intelligently access the unused radio resources. It will be the tendency to apply the cognitive radio technology to current wireless network. So, we design the routing protocol suitable for the cognitive radio environment|
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 nodes 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:
|•||Each node maintains lists of locally available channels (channelSet As) that are not occupied by primary users|
|•||The source node transmits the RREQ using the common control channel toward the downstream WP node, with its channelSet As|
|•||As the WP node receives the RREQ, it first checks whether the destination is in the CMLT or not. If not, the WP node extracts the channelSet As, comparing with the channelSet of itself and the new channelSet which is the set of channels owned by both nodes, will be rewritten to the RREQ. Simultaneously, the channelSet As is compared with the channelSet of all normal nodes in the CMLT and the Mt is calculated respectively defined as the number of identical frequency channels|
|•||WP node transmits the RREQ to the normal nodes with the largest Mt|
|Fig. 1:||Route discovery|
|•||The normal node receiving the RREQ is treated as source node and the operations are repeat until the RREQ reach the destination node|
|•||At the destination node, the channelSet As is compared with the sequence number of destination node, when the destination node has received the RREQ. Then one frequency channel is selected by destination node randomly from the available frequency channels and its sequence number is written to the RREP|
|•||The RREP return the source node with the sequence number of the frequency channel through the route indicated in RREQ and all the nodes in the route must locate in the frequency channel, so there is a route established in the cognitive mesh network which is referred as MRP. The MRP is considered as the most reliability path, because it contains the most available channels. While PUs appear suddenly, the network will have more frequency channel to choose|
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:
|•||The two ends of failure link coordinate the spectrum opportunity (SOP) using Common Control Channel (CCC)|
|•||After coordination between two ends, a new frequency channel is determined|
|•||The initiator buffers data packets it receives that use the route under repair. If the repair succeeds, the initiator transmits the buffered data packets|
|•||Because of the inconsistency of frequency channel, the switching delay will be caused at the two ends of the link. So, if there are several links changed, the total switching delay of the route will not endure. In this situation, the source node will start the route recovery phase applying the above-mentioned method|
|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.
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:
|•||Packet delivery ratio: The ratio of the data packets delivered to the destinations to those generated by the sources|
|•||Average control overhead: The control packet overhead that for route discovery, clusters maintenance and route repair, etc.|
|•||End-to-end delay: The average delay includes all possible delays caused by route discovery, propagation and transfer time, etc.|
|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:
|•||End-to-end delay: The average delay includes all possible delays caused by route discovery, propagation and transfer time, etc.|
|•||Packet dropped rate: The ratio of the dropped data packets to those data packets generated by the sources|
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.
In this study, we proposed a new routing algorithm CIH-AODV, which maintains nodes hierarchically based on AODV for cognitive WMNs. Our routing scheme is hybrid in nature as it uses both flat and hierarchical approaches for finding the routes to the destination.
Simulation results show that CIH-AODV provides better packet delivery rate with less route latency and overhead. Moreover, the performance of protocol is satisfied under the cognitive radio environment. The results confirm that our scheme achieves significant improvement on keeping the merits of AODV.
Admittedly, the secure and energy balance between WP and CM nodes and some other problems have not been considered in CIH-AODV, we will keep on our work in future to make the improved route protocol more reliable and available.
This research is partly supported by National Nature Science Foundation of China (Grant No. 61070180) and Open Fund Project of Key Laboratory in Hunan Universities(Grant No.09K041).
- Bruno, R., M. Conti and E. Gregori, 2005. Mesh networks: Commodity multihop ad hoc networks. IEEE Commun. Mag., 3: 123-131.
- Su, H. and X. Zhang, 2007. Opportunistic MAC protocols for cognitive radio based wireless networks. Proceedings of the 41st Annual Conference on Information Sciences and Systems, March 14-16, Baltimore, MD, pp: 363-368.
- Akyildiz, I.F., W.Y. Lee and K.R. Chowdhury, 2009. CRAHNs: Cognitive radio ad hoc networks. Ad Hoc Networks, 7: 810-836.
- Xin, C., B. Xie and C.C. Shen, 2005. A novel layered graph model for topology formation and routing in dynamic spectrum access networks. Proceedings of the 1st IEEE International Symposium on New Frontiers in Dynamic Spectrum Access Networks, Nov. 8-11, USA., pp: 308-317.