This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
The performance of Wireless mesh network is highly dependent on routing protocol. AODV (Ad Hoc on Demand Distance Vector Routing) is a popular protocol for wireless networks; it uses an on-demand mechanism and discovers routes only when a source node needs them. It's able to maintain routes even when the topology of the network is dynamic. AODV is well suited for wireless mesh networks in that it has low processing & memory overhead and low network utilization. Additionally AODV provides loop freedom for all routes through the use of sequence numbers. In AODV source initiate route discovery by broadcasting Route Request (RREQ) packet, neighbouring nodes will forward RREQ until either destination is reached or RREQ arrived at the node that has a fresh route to destination. Thus a Route Reply (RREP) is returned. Once the source receives a RREP, it can begin using that path for data packet transmission.
Since its initial design, AODV has evolved in a number of ways for improved performance, robustness and better scalability. Nevertheless it has a problem of poor scalability. Research
has demonstrated its performance bottleneck both theoretically and through simulation experiments. Because AODV use flooding as the basic mechanism to propagate route control messages and to discover route, it leads to network congestion when number of nodes is high. It's thought that building a hierarchical network is a very promising way to achieve scalability, so SEE-AODV routing protocol has been presented which is based on AODV and gradually became a hierarchical protocol in working, besides this I have also implemented a Blocking Expanding Ring Search Algorithm to improve the energy efficiency by reducing packets flooding.
3.2 SEE-AODV (AODV-Clustering Protocol with Blocking Expanding Ring Search algorithm)
3.2.1 Design Goals
The design goal of SEE-AODV routing protocol  is to improve the scaling potential of AODV and to make it energy efficient. The main feature of AODV-Clustering includes:-
The protocol first works on AODV method, then gradually changes to a clustering route protocol. We have several considerations about it: First, there is central control node in mesh network; second, using this method can also allow AODV nodes coexisting with AODV-Clustering nodes; third, it can reduce the overhead caused by frequently changing of cluster.
(ii) Coexist with AODV
AODV is a widely accepted protocol. There are several implemented version of AODV reported. One of the important principles in designing AODV-Clustering is the coexistence with AODV; it means nodes which 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 need. In fact AODV-Clustering let all nodes that haven't joined a cluster works on AODV method.
(iii) Route Discovery Mechanism
In AODV-Clustering, there are two route discovery mechanisms for the nodes which join the cluster, one is Blocking-ERS it can increase speed and efficiency of the route discovery; the other is traditional RREQ flooding route discovery mechanism which extends from AODV. Normally Blocking-ERS is used first, if a suitable route can't be found before timeout, then traditional route discovery mechanism is used.
(iv) Local Route Repair
To reduce the number of lost data packets, when the route broke due to mobility, AODV-Clustering let the node 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.
3.2.2 AODV-Clustering Routing Scheme
(i) Route Discovery
At the beginning the status of all nodes is "unassigned". Source node broadcast  RREQ message to find a route, destination node or intermediate node that has fresh route to destination reply with RREP message to source. On the way which RREP pass by, one or several nodes are selected as cluster head (CH) using a defined rule. CH node will broadcast CH message to its neighbours, the neighbour nodes which receive this broadcast will act differently according to its roles.
(a) For node whose status is "unassigned", it will issue a Join Cluster Request to the broadcasting CH and can become an ordinary cluster member after receiving the acknowledgment from this CH. In AODV-Clustering, CH node can reach all his members by one hop, so the protocol's architecture is one level hierarchy.
(b) For node which is an ordinary cluster member, it will judge if the broadcast message sender is its original CH, if yes, no action needed; else, send Join Cluster Request to the CH and become gateway node after receiving acknowledgement from it. Being a gateway, it will send Gateway Message to all CH nodes which it connect directly, let them put its address in their Gateway Table.
(c) For node which is a gateway, it will check its Gateway Node Table whether there is a entry for this broadcasting CH node, if yes, no action needed; else, send Join Cluster Request to it and put its address into Gateway Node Table after receiving acknowledgement from it. Gateway nodes have two tables, one is Gateway Node Table which contains cluster head address which it connect directly, another is Joint Gateway Table, which contains address of the CH nodes which can be reached by 2 hops and also the nodes which help to reach these CHs which are called Joint Gateway. To generate this table, gateway nodes need send Joint Gateway Message to their neighbours; neighbours will reply if their CH node is different. The replied neighbours will become joint gateway. After joining a cluster, nodes can use Blocking-ERS to find out destination node then:
If the issuer of RREQ is an ordinary cluster member, first it will check whether destination is among its neighbours through sending RREQ which Time To Live (TTL) is 1, if yes, route is found, else Blocking-ERS is used. The node set a fast forward flag in RREQ and sends RREQ to its CH, the CH will check its route table, if no fresh route is found, it will forward RREQ to its gateway nodes. Gateway nodes will forward RREQ to neighbour CHs or joint gateways. If route can't be found before timeout, AODV route discovery mechanism is used then.
To avoid loop in path, we let the RREQ with fast forward flag record the CH nodes that have been visited before, the forwarding node will discard RREQ if its CH node has been visited. In AODV-Clustering, the role of cluster member may change under certain condition. For example, CH node returns its status to "unassigned" only when there are no members in cluster. Ordinary cluster member can change to gateway when receive the acknowledgement of Gateway Message from CH node; and returns its status to "unassigned" if the node receive RERR and find its CH node in RERR's unreachable list. Gateway node may become ordinary cluster member when there is only one CH node entry left in its Gateway Node Table. As more and more nodes join clusters, Blocking-ERS will be used more frequently, RREQ flooding will be reduced and Average Route Acquisition Latency will be shortening.
(ii) Route Maintenance
AODV-Clustering extends many features from AODV for route maintenance, for example, use "hello" message to confirm the existence of neighbours, use RERR message to inform the nodes affected by the link breakage. In addition to it, AODV-Clustering adds some cluster related maintenance operations, include keeping the information of cluster allow the node joining cluster, leaving cluster and changing its status.
(a) Joining Cluster
The nodes whose status is "unassigned" will join the cluster after receiving the CH Broadcasting Message. To reduce overhead, no periodic CH Broadcasting is used. Instead, a "on demand" method is used for new nodes to join cluster: when the node whose status is "unassigned" broadcast RREQ to its neighbours, a specific mark is set in RREQ, the mark will inform neighbouring CHs to let him join the cluster. Using this way, unassigned node that newly comes will have a chance to join the nearby cluster when it has data to send.
(b) Leaving Cluster
If the ordinary cluster member finds its CH node unreachable, it will change its status to unassigned. This means the node leaving the cluster. CH node should change its status to unassign when it has no cluster members.
(c) Changing Cluster
In AODV-Clustering, the change of cluster is not occurred immediately. When the node leave the cluster, its status become "unassigned", it works on AODV method until new CH node appear nearby and it has a chance to join the cluster.
3.3 Route discovery approaches in wireless mesh networks
In Wireless mesh networks, nodes cooperating for delivery of a successful packet form a communication channel consisting of a source , a destination and possibly a number of intermediate nodes with fixed base station. Each node communicates directly with the destination or neighbour intermediate nodes within wireless transmission range. Mesh networks are hardly realised in practice unless energy efficient communication are in place due to limited battery life of mobile devices. Protocols determine how the nodes communicate and the existing protocols can be modified to become more energy efficient. It is known that the communication between nodes consumes substantial amount of energy in wireless networks. In this dissertation some inefficient elements have been found in well known reactive protocols AODV and propose a new approach for rebroadcasting in Expanding Ring Search. This leads to the Blocking-ERS scheme, as we call it, which demonstrates improvement in energy efficiency at the expense of route discovery time in comparison to conventional route search method. We assume that routing protocol can be carried out much faster than the topological changes.
3.3.2 Expanding Ring Search techniques
Reactive routing protocols in Mesh networks such as DSR and AODV are often supported by a so-called Expanding Ring Search (ERS). During the route discovery stage, the RREQ (Route REQest packet) is broadcasted by flooding and propagated from one intermediate node to another to find the route information from the source to the destination node. Figure 3.1, 3.2 and 3.3 show how the broadcasts and propagation form searching 'rings' in such a route discovery process. In Figure 3.1 a RREQ is broadcasted by the source and two neighbour intermediate nodes receive the message. Each arrow line represents a send-receive relationship between the broadcasting source and one neighbour node. Each broadcast is issued with a hop number which is a serial number indicating the sequence of the nodes alone a route from the source. In Figure 3.2 for example, a RREQ is broadcasted with a hop number '1' by the source and five intermediate nodes receive the message and are given the same hop number. If none of them has the route information to the destination node, the five nodes rebroadcast the RREQ with an incremental hop number 2 in Figure 3.3. In this way, the nodes with the same hop number from the source node form a circle i.e. the search rings. As the route discovery in progress, the diameter of the searching ring increases. Utilising the route cache during routing is widely adopted in mesh networks to achieve time and energy saving routing. A node in mesh networks broadcasts RREQs and the intermediate nodes within the broadcast range cooperate the route discovery process by checking their own route caches for requested route information and maintaining an updated list of known routes.
Fig. 3.1 Propagation of RREQs
Fig. 3.2 Formation of a ring
Fig. 3.3 Expanding ring search
An intermediate node that has the requested route information towards the destination is defined as a route node. Efficient route discovery relies largely upon how quickly a route node can be found. When a RREQ is received, an intermediate node searches for the requested route information in its route cache. If there is route information to the destination node in its route cache, the route node would stop rebroadcasting the RREQ and sends a RREP to the source node with the complete route information consisting of the cached route in itself and the accumulated route record in the RREQ. In this way, the route may be established much quicker and the total delivery time and energy consumption are saved. Here in next section two techniques of ERS has been explained.
(i) TTL Sequence-Based Expanding Ring Search
The goal of the expanding ring search is to find nodes that have the required route information to the destination node in their route cache by propagating RREQs. The propagation of RREQs is, on one hand an efficient way for route discovery. It on the other, may lead to ineffective flooding. Nodes in mesh networks, for example can be trapped in a loop of actions and end up asking each other for routing information for a long time without any solutions. To control the flooding in mesh networks, TTL (Time to Live) sequence-based Expanding Ring Search is frequently used. The TTL sequence-based ERS restrains its searching range by giving RREQs a pre-defined TTL number. The TTL number corresponds to the radium of a searching area. Each time it fails to find any node that has route information to the destination node or the destination node itself, the source node rebroadcasts the RREQ in the next round with an increased TTL number to allow the RREQ to reach the remote nodes in further distance. The TTL number increases linearly with a specified value. Figure 3.4 shows how TTL controls the RREQ relay range by predefined TTL values of 1, 2 and 3.
Fig. 3.4 TTL sequence-based ERS
Historically, TTL sequence-based mechanism was broadly adopted to reach all nodes in the networks to ensure successful route discovery in one round of flooding. Later an optimally chosen set of TTL was introduced to solve the generic minimal cost flooding search problem. However it has been shown that there is no significant advantage from the optimal TTL sequence-based route discovery compared to the basic route discovery mechanism in terms of route discovery enhancement. In addition, optimal TTL sequence-based discovery causes longer delay than the basic route discovery mechanism. As it can be seen from Figure 3.4 in TTL sequence-based ERS, the source node issues and rebroadcasts a RREQ with increased TTL number if no RREP is received after a certain amount of time. The route discovery procedure repeats until the whole network is covered or until it finds the nodes that have the route information to the destination node or the destination node itself. This can also cause the overheads over the network area. More energy will inevitably be consumed during the route discovery if the route discovery process starts from the source node every time. It is especially costly when a larger area of the network needs to be searched.
An alternative ERS scheme has been proposed to support reactive protocols such as DRS and AODV and it is called Blocking Expanding Ring Search  (Blocking-ERS for short). The Blocking-ERS integrates, instead of TTL sequences, a newly adopted control packet, stop instruction and a hop number (H) to reduce the energy consumption during route discovery stage. We derive new route discovery algorithms (Algorithm 1, 2 and 3 for the source, intermediate and destination node respectively and Algorithm 4 for blocking procedure). The basic route discovery structure of Blocking-ERS is similar to that of conventional TTL sequence-based ERS. One of the differences from TTL sequence-based ERS is that the Blocking-ERS does not resume its route search procedure from the source node every time when a rebroadcast is required. The rebroadcast can be initialised by any appropriate intermediate nodes. An intermediate node that performs a rebroadcast on behalf of the source node acts as a relay or an agent node. Figure 3.5 shows an example of our Blocking ERS approach in which the rebroadcasts are initialised by and begins from a relay node M in rebroadcast round 2 and another relay node N in round 3 and so on. In Figure 3.5 the source node broadcasts a RREQ including a hop number (H) with an initial value of 1. Suppose that a neighbour M receives the RREQ with H=1 and the first ring was made. If no route node is found, that is, no node has the requested route information to the destination node, the nodes in the first ring rebroadcast the RREQ with an increased hop number, for example RREQ with H=2 is rebroadcast in this case The ring is expanded once again just like the normal expanding ring search in AODV (see also Figure 3.3), except with an extended waiting time.
Fig. 3.5 Blocking-ERS
We can define the waiting time as
WaitingTime = 2 Ã- HopNumber
The nodes in Blocking-ERS receiving RREQs need to wait for a period of 2H, i.e. 2Ã-their hop-number unit time before they decide to rebroadcast, where the 'unit time' is the amount of time taken for a packet to be delivered from one node to one-hop neighbouring node. In the example (Figure 3.5) the second ring has been made because there is no route node is found in the first ring. The node N receives RREQ and waits for, in this case a period of 4 unit time since the hop number of the RREQ packet that the node N received is 2. Two 'stop' signals are used in Blocking-ERS to control the flooding. One is the RREP, which can be sent by any route node to the source. The other is called 'stop instruction' which can only be sent by the source node. The RREP informs the source node that 'a route node has been found and therefore 'flooding should be stopped', while the 'stop instruction' is an order to everyone involved in the flooding to terminate the route discovery process. If there is no 'stop instruction' message after 4 unit time has passed, it means that no node has the route information to the destination node in the second ring either. Then every node in the second ring rebroadcasts to make the third ring. If a node finds the route information to the destination node in its route cache, this intermediate node is a route node and it broadcasts the
Algorithm 1: Source node
1: broadcast 'RREQ, H = 1 and max j'
2: wait until a RREP is received
3: broadcast the 'stop instruction' and H to everyone within the ring where it sent following conventional TTL scheme
4: use the 1st RREP for the data packet and save 2nd RREP as a backup
5: drop any later RREPs
Algorithm 2: Intermediate node
1: listen to RREQ
2: check the max j after receiving the RREQ
3: if the H is bigger than the max j then
4: drop the RREQ
6: check the route cache after receiving the RREQ
7: if there is route information in the cache (i.e. being the Route Node) then
8: send a RREP and H to the source node
10: wait for a period of 'waiting time' (i.e. 2 Ã- HopNumber)
11: while waiting do
12: if receive a 'stop instruction' then
13: call the blocking procedure (see Algorithm 4)
14: erase the source-destination pair in the route cache
15: else if receives a 'RREP' then
16: forward it to the source node
17: end if
18: end while
19: if receives no 'stop instruction' then
20: increase the hop serial number by 1 and rebroadcast RREQ
21: end if
22: end if
23: end if
RREP message to the source node and the source node broadcasts a 'stop instruction' message to all the nodes involved in flooding. To improve the time efficiency a 'stop instruction' is sent via conventional TTL scheme. The automatic flooding takes place until the 'stop instruction' message reaches all the nodes that have the same hop number as the route node that originated the RREP in the first place. To limit the flooding in Blocking-ERS in case there is no route node is found, the source node sends a maximum journey value (max j) with a RREQ packet. When an intermediate node receives a RREQ, the node compares the maximum journey value of the RREQ with its H. If the H is bigger than the max j, then the intermediate node drops the RREQ packet.
Algorithm 3: Route or destination node
1: wait for the first arriving RREQ
2: if receive a RREQ then
3: send the RREP and the H to the source route (contained in the RREQ packet)
4: end if
Algorithm 4: Procedure of blocking
1: compare Hr with H
2: if Hr is bigger then
3: forward the stop instruction and
4: erase the source-destination pair in the route cache
6: drop the stop instruction and
7: stop rebroadcasting and
8: erase the source-destination pair in the route cache
9: end if
To develop these ideas further, we have derived four algorithms Algorithm 1, 2 and 3 for the source, intermediate and destination (or route) nodes respectively and Algorithm 4 gives the details of the blocking procedure. The source node in Algorithm 1 covers the actions of a source node for the route discovery process. This includes initialising a route discovery process by first sending a RREQ (line 1), sending a 'stop instruction' after a RREP is received (line 3) and handling the route information in RREPs (line 5, 6). Similarly, Algorithm 2 summarises the actions taken by intermediate nodes which can be classified into route nodes and the rest. Once the route node is identified, a RREP will be sent with the current hop number to the source node (line 7, 8). Other intermediate nodes need to wait for a period of 'waiting time' (line 11-18) and start flooding if no 'stop instruction' is received (line 19-21). During the waiting-time period, the intermediate nodes need to forward a 'stop instruction' (line 11-12) or the RREP (line 8-10) because it might be the 2nd RREP for the source node as a backup. Finally, Algorithm 3 highlights the actions by a route or destination node. It simply completes route information and sends it together with the RREP to the source (line 2-4).
3.4 Chapter Summary
In this chapter Scalable Energy Efficient-AODV routing protocol in wireless mesh network has been proposed which is an improvement over existing AODV routing protocol. By using Clustering and Blocking Expanding Ring Search approaches, there is improvement in scalability of AODV and it became more energy efficient.
By using traditional ERS to discover route there is lot of energy consumption because every time rebroadcasting is done from source again and again until destination node not found. But in Blocking-ERS rebroadcasting can be done from intermediate nodes to find out destination node, so in this way there is saving of energy by using B-ERS approach. In the next chapter, implementation details are given.