SMAODV: A Novel Smart Protocol for Routing in Ad-hoc Wireless Networks Using the PageRank Algorithm

Generally, the wireless networks in view point of required equipment to implementation is divided into two categories: 1. The structural networks that will be needed, some equipment for implementing such as mesh nodes in MANET networks. 2. The network without infrastructure, as you can see its sample in Figure 1. These networks are the set of mobile nodes and they do not rely on fixed infrastructure and so the nodes can change their position within it dynamically and establish the communication together in the network.

This paper explores characteristic of Ad-Hoc networks and deals with routing issues. The main contribution of this paper is to present the relationship between the webranking algorithms and routing protocols. More precisely, we introduced two new routing protocols, SOADV and SMAODV, in Ad-Hoc wireless networks which are based on the AODV protocol. They find the multi-paths with the lowest length between the source and destination. In the first method, packets will be sent sequentially in the multi-paths but in the second method. We will use the PageRank algorithm of webpages that presents a special mechanism for guiding the packets which guaranties energy saving and controls the traffic at nodes.

The rest of the paper is organized as follows. In Section I we presented the general classification of routing protocols in Ad-Hoc networks. In Section II we describe the basic concepts of PageRank algorithm. Section III presents the PR-RAM plan in wireless networks without infrastructure. The next two sections IV, V concern with the details of our two proposed protocols SAODV and SMAODV for routing in Ad-hoc wireless networks using the PageRank algorithm and with special mechanism for sending data packets. Section VI describes the experimental evaluations and deals with simulation results in the NS-2 network simulator. We conclude the paper in Section VII.

Fig.1. A sample for Ad-hoc networks

• II.    Ad-Hoc Networks and Routing Protocols

In this section we first review some basic characteristics of Ad-hoc networks very shortly and then focus on the AODV routing protocol.

Ad-hoc networks have the following basic properties:

• 1.    Dynamic topology: In such networks, the nodes are free  and move arbitrarily;  the dynamic

• 2.    Bandwidth restriction with variable capacity: The wireless communication lines have less capacity than wired lines. Hence, the capacity of lines must be adjusted in order to improve the congestion (compression) in network.

• 3.    Power restriction: All the nodes or some of the nodes that exist in Ad-hoc networks, rely on battery power for energy, so for several nodes, preservation of powers is design criteria. Indeed, the restriction of power nodes restricted the transmittal radius of radio.

• 4.    Limited physical security: The mobile wireless networks are more at risk of physical security of communication and reducing the security risk is a challenging issue.

topology  is to multi-hop and  may change randomly at unpredictable times. Adjustment of sending and receiving parameters can affect topology. By the nodes mobility, the structure of Ad-hoc network is separable.

The method of AODV protocol [4] is based on sending stage of request packets by source and sending stage of response packets by destination. In this protocol, the source node begins the rout discovery operation with sending RREQ packets. Each node that received the route request packet, if the packet isn’t repetitive and the sender packet isn’t itself, will relay it and this action continues until receiving the packet on the destination. With reception of RREQ packet in destination address, it is clear that the destination will send data and after the reception of RREQ packet, it will store the path through and with sending the RREQ to some node A, it informs A the pathway where sending data was started.

The routing protocols of Ad-hoc networks are divided into four categories, which are discussed below. Our proposed protocols belong to the third category where we apply our changes to AODV and offer a new algorithm. Our proposed algorithms are proactive and reactive routing techniques.

• A.    Proactive Routing [7]

These protocols start with a path from all of network nodes and maintain it. This method is based on local networks or conventional extensive cable network inside it. The routing information spread out between all the network nodes at the time of system performance. In these protocols the amount of overflow is always fixed and there is no connection to the packet data. Distance vector protocols are of this kind of type.

• B.    Reactive Routing [1, 2]

Since in an Ad-hoc network it may not be necessary that a node sends a packet to all nodes on the network so that the protocol is applied only when it receives the routing information and in this way the information would not distribute continuously between the nodes of the network. In this method just the routing information related on active pathways are gathered.

• C.    Hybrid Routing [1]

These protocols try to make a good compromise between the prevention and response plans. The main idea of integrated protocols is to restrict the prevention function in the small territory to reduce the maintenance of overflow and use response function for routing between the territories. Territory in prevention routing is named scope or cluster , and the clustering technique called cluster method .

• D.    Location Base Routing [6]

These algorithms need the information about physical location of nodes that wish to communicate with others. In general, each node determines its position with use of GPS or any other location finder service. The transmitter used a packet from a location service to determine a closed position to be stored in the destination address field before sending. Then routing decisions in each node is adopted based on the neighbor positions.

• III.    The PageRank Algorithm

  This algorithm is one of the most widely used algorithms for allocation of rank based on links analysis [3]. The amount of rank in PageRank algorithms is the numeric value that determines the importance of a web page. When a page is linked to another page, it shows its effective vote to that page. We can say generally that a page is important when it mentioned with another important pages. Such scenario can be extracted from a graph G=(V, E) where V is the set of all web pages and E is the links between them. Below is the simple Page Rank formula introduced by LaryPage and SergeyBrin in 1996:

p_R (Л) = (^₊... ₊ ^)        (1)

• ^V V C (Tl)            C(Tn) /                 ^v '

Where

PR(A) is the page rank of page A.

PR(Ti) is the page rank of Ti that is linked to A.

C(Ti) is the number of links that are outside of Ti.

We can simply say that the rank of each page is calculated from total incoming links divided between outbound linked pages. As we said, this algorithm used to rank the webpages and will assign ranks to pages, which is defined as the priority of pages in order to be displayed to users. Revisiting the PageRank algorithm, we conclude that one page takes a high ranking if it has been mentioned by other important pages. The importance of external links is depended to rating page itself directly, and indirectly it is depended to ranking related pages. If we suppose that the above mentioned graph for which their nodes are workstation with a link to a node that is in the frequency range, one can say that a node v takes a high score if it has high in-degree: incoming degree or incoming degree of its neighbors. We can conclude that a workstation gets a high rank if it is in the situation on the way that there are many nodes. Rechecking the Weighted Page Rank algorithm we can adopt a method in Ad-hoc networks that with sending control packets, the pathways must be used with lower rank nodes than higher rank nodes. This will lead to better control of the traffic and energy consumption and hence increase the whole network lifetime.

• IV.    Pr-Ram Plan: Routing In Wireless Networks Without Infrastructure

In this section, PR-RAM plane that is a routing protocol of networks without infrastructure with use of PageRank is illustrated [8]. PR-RAM is a kind of routing protocols with minimum Hop-count routing protocol. The PR-RAM’s goal is to transmit the data packets more efficiently on view of the variance of entire nodes energy.

In this method, at first the source node finds the minimum hop routing paths. The source node has the rank of 1 as its initial value. Then the rank of source node is divided among its next-hop links and the sum of these values becomes the rank of next-hop node. This process is carried to completion. During this process the intermediate nodes work as relay nodes to the source node.

• A.    The Relation between Rank and Access Possibility

The rank of a node means the measure of the importance of that node in a wireless network without infrastructure. It will be used in routing higher ranking nodes than the lower ranking nodes. Now, we can review the relation between the ranking and access possibility to next node.

Figure 2(a) illustrates the access to node AP from nodes with the same rank which is 1. Every node (A, B, C, D) want to transmit the data to AP. Every node has the value of 1 as its rank. Because every node has the same rank, every node gets the same chance to access to AP. In traditional routing algorithms, every node gets the same chance to simultaneously transmit the data packets to a destination node as it is shown in Figure 2(a).

Figure 2(b) describes the example of the access to AP of nodes of different ranks. Every node (A, B, C, D, E, F) want to try to transmit the data packet to AP.

• A, B, C, E, F has the value of one as their ranks. But node D has rank value of 3 that is summed to node E, F’s rank value and node D’s rank. Here just four nodes (A, B, C, D) directly transmit the data directly to destination node, AP. In other words, node E and F transmit the data packet to AP through the relay node D. That is, try approaching to the next-hop node, using the access probability.

  

  (a)                              (b)

  Fig.2(a). The access of nodes of same rank. (b). The access of nodes of different rank

  
  

The nodes with higher ranks have more chance to access AP than the nodes with lower rank. In this method, the accessing possibility of a node is defined as follows:

р =

1 access

RankofPresentNode RankofNextNode

Paccess is access possibility to the next node. Access possibility to a node decides what the next node in the path is going to be.

• V. Our First Proposed Protocol SAODV

Our first proposed protocol is a multipath protocol that acts as reactive and at any moment that a node needs to send data to a specified target, it begins to route the pathway and find the shortest route between the source and destination and broadcast the packets in designated routes.

For the sake of completeness, we describe our protocol in three steps.

• B.    Routing table [10]

The routing table consists of the following fields:

.

• C.    Control Packets [5]

Before explaining the pathway discovery operation, at first we describe the request packets:

• •    Hello Packet

In the route discovery operation, we must find the neighbour nodes and then send a Hello message to neighbour nodes. That way, each node will be informed about its neighbours and will fill the table of its neighbour nodes. Thus if one node that is in transmission path can listen to Hello message by its neighbours, then it will store their information.

• •    Route Request Packet (RREQ)

When a source node needs to communicate with another node that it is not in its neighbour’s table, it sends a RREQ packet with the following items to its neighbour nodes:

• •    Route Reply Packet(RREP)

When a destination node was succeeded to find a suitable route, it sends the RREP packets reversely to the source node:

Life Time: A time in milliseconds for recovering the RREP node and recognizing the authentic route.

• •    RERR Packet

This packet is produced by a higher node that its connection is interrupted and then will be sent to source from where the rerouting is being started.

• D.    The Route Discovery Process in SAODV

When a source node has a request of routing to a destination node for sending data packets, it checks the routing table. If there isn’t a route to the desired destination, the route discovery process will be started and RREQ will be sent to neighbors. When a middle node received RREQ, it is checked whether it already received it or not. In the case of not receiving, it records its number and continues broadcasting operation. Otherwise, it drops the RREQ packet.

This process will be repeated till RREQ reaches to the target node. When the destination node received the first RREQ, it produces RREP immediately for sending to transmitter and from receiving RREQ routes that makes reversely it sends them back to the source node. We must consider that if the target node received another RREQ from their neighbors after sending RREP for the first RREQ it replies them and for each of them produce a unique RREP. According to this procedure, the source node begins sending the data until receiving the first RREP to produce the first route. If there is one route between the source and destination, they will have the same operation as AODV and if there are more than one route between the source and target, the transmitter sends the RREP’s sequentially.

In the rest, the route discovery process will be further explained with a sample.

According to Figure 3(a), node S as source, wants to send some data to D, as destination node. After checking the routing table and lack of direct routing to the intended destination, it began to discover the route operation and according to Figure 3(b), it propagates the RREQ packet to B, E, C nodes. After receiving the RREQ packets, because they don’t have direct path to destination, as in Figure 3(c), they began to broadcast RREQ, this packets will be received by A, F, G, H nodes, and these nodes in the next phase according to Figure 3(d) broadcast RREQ packets and imply to F,I, K, J nodes. Because node F already received RREQ packet, it will be dropped, but other nodes broadcast the route request in the next phase. RREQ packet reached to D and M nodes. Because node M isn’t the destination and it doesn’t know a route to destination, it begins to broadcast RREQ packets. But since D is the destination receiving RREQ packet form two neighbors (J, K), it begins sending two unique packets in the reverse path to source and according to Figure 3(g) the source node S begins sending the data form these two paths sequentially with accordance of mechanism of SAODV method.

Fig.3(a). Node S wants to send the data to node D

Fig 3(b). Sending RREQ packet by node S

Fig.3(c). Sending RREP packets to S and broadcast RREQ packets

Fig.3(d). Continue broadcast RREQ packets

Fig.3(e). Node D receives RREQ packets

Fig.3(f). Sending unique RREP packets by node D

Fig.3(g). Sending data packets among discovery paths

• VI.    Our Second Proposed Protocol SMAODV

This protocol is a multipath protocol the same as SAODV that act reactive and at any moment that a node needs to send data to destination, began routing and finding the shortest path between the source and destination. SMAODV uses a special mechanism enjoying the information that each node has from its neighbors by sending the controlling packets. It began to send information so that bad division in route use most optimized routes as we can see it in the following more precisely.

• A.    How to Send Control Packets

In normal mode, the nodes begin sending Hello packets in scope of their access and in this way they find their neighbor’s situation and update their routing table. Through these packets if a node was added to the neighbors list, they add it in the table and if a node was moved away from a neighbor it will be deleted from table.

In the initial state all of the nodes that are information transmitter and receiver, get score of one, and the nodes divide their scores on the amount of neighbors. By adding a field to hello sending packet and putting the score in the field, they broadcast it in their accessing environment towards the neighbor. For example, if in the initial state a node has two neighbors, it divides its 1 score to two and sends 0.5 values in control packets towards the neighbors that are in routing table:

PR(U) = Z^ iPR(P)            (3)

PR (U): The page score of U

N: The number of adjacent pages of page U

In this way, each node that is in the route of many nodes gets a higher score and this shows the importance of that node.

• B.    Route Discovery Process in SMAODV

When a node has a request for sending the data packets, it checks the routing table. If there isn’t a route to destination, the process of pathway discovery will be started and RREQ packets will be sent to its neighbors. When a middle node received RREQ packet, it checks whether it has already received it or not. If not, it records its number and continues the broadcasting operation. Otherwise it discards RREQ.

This process is repeated until RREQ will be reached to the destination node. When the destination node received RREQ, it immediately produces a RREP to the target node. When the target node receives RREQ, it immediately produces a RREP to transmitter for sending. From receiving route of RREP, it sends positive replies reversely to the source node. Accordingly the source node begins sending the data for receiving the first RREP and first route. If there is one way between the source and destination, it will have same operation as AODV and if there are more than one path between source and destination, they will divide the load by the mechanism that will be explained below.

• C.    How the Packet Passes by Nodes

Generally after detecting the multiple routes at a node, if it has a neighbor for sending a packet to destination, it sends a packet towards it. If we know more than one node in its neighbors for sending a packet to the target, we compute the average neighbor load for the amount of packets by the aid of the following method:

Input: Source PR (V), list of PR (U _{i= 1} , ₂ , _{3 n} ) Output: list of W (U ,-i,2,3 n )

For i = 1 to | U |

Sum = Sum + PR(U,)

AVR = Sum / | U |

For i = 1 to | U |

If (PR (U _i ) < AVR)

W (U _i ) = (PR (V) /|U |) + ((AVR - PR ( U ₍ )) / Sum)

Else If (PR(UJ > AVR)

W ( U _i ) = (PR (V) /1U |) + (((PR ( U _i ) - AVR) / Sum)

Else

W ( U i ) = (PR (V) /1U |)

Return W (U i-1,2, ₃ n )

Where |U| is the number of neighbor nodes that have a path to destination and PR(Ui) is the rank of node U .

• VII.    Experimental Evaluation And Analysis

• A.    Simulation Environment

With respect to the following properties in the network simulator software NS-2 , we used it to test the following hypothesis.

Scenario production: This property enables users to evaluate their protocol under various conditions. Scenario production consists of automated production of network topology, traffic patterns and dynamic events. Automated scenario production plays a key role in carrying the systematic test, in this protocol (STRESS).

Expansion capability: Adding a new library expands existing protocols in NS-2 which is simply possible without needing to change the other protocols.

All of the parameters that are considered in the simulation of our proposed protocols are summarized in this following table.

Table 1. Simulation Parameters

Parameter	SMAODV	SAODV	AODV
MAC protocol	802.11	802.11	802.11
Routing protocol	SMAODV	Sequential AODV	AODV
Number of nodes	100	100	100
Mobility model	Random way point	Random way point	Random way point
Transmission range	250m	250m	250m
Terrain range	1000m *1000m	1000m *1000m	1000m *1000m
PHY layer	Phy Wireless	Phy Wireless	Phy Wireless
Queue type	DropTail/PreQ	DropTail/PreQ	DropTail/PreQ
Simulation	100s	100s	100s

• B.    The Test of Remaining Energy of Network

One of the basic parameter in network efficiency is the subject of energy consumption in network nodes. Our proposed protocols spend the suitable process. In Figure 4 one can see that the amount of remaining energy after using SAODV or SMAODV protocols with 100 nodes are much more acceptable than the basic AODV protocol.

• C.    The Amount of Remaining Energy of Network Nodes

In our simulated network there are 100 nodes that their coordinates is determined randomly. Our testing for the remaining energy of network nodes comprises of selecting 10 nodes and averaging their remaining energy after 10 times of test. The variance of remaining energy of nodes had been minimized, especially with our proposed protocols, which finally leads to the stability of the network; see Figure 5.

■ AODV ■ SAODV ■ SMAODV

Fig.5. Testing the remaining energy of 10 network’s nodes

• D.    Testing the Delivery Rate of Network Packets (PDR)

PDR is calculated in percent and it is expressed by the following formula:

PDR =

∑ Recieved Packets ×100 ∑ Send Packets

PDR is the ratio of receiving informational packets on the number of transmitted packets in the network. Whatever this amount is higher, the resultant of network is better. As the results are illustrated in Figure 6, in both of our proposed protocols, there has been nearly 5 percent recovery.

60 о га 40 cc

SMAOD SAODV   AODV

V

PDR 79.61     80.38     75.38

Fig.6. The graph of the number of routing packets in 100 seconds

Since in the basic method AODV, each node uses single path for sending packets, it takes a lot of time for sending the first packet to the latest. Mean-time if a node has been moved from the created path or the path is broken, some of the sent packets will be lost and the sending operation must be redone, which is definitely costly.

E. Testing the Delay Average of End-To-End Network

The average amount of time that one packet takes from source to destination, is specified as the delay packet. End-to-End delay of packets is characterized by these parameters: propagation delay, queuing delay, transmission delay and processing delay; see Figure 7(a), 7(b).

=

∑ Arrive time— ∑ Send time

∑ Number of connections

ETE Delay 49.825    47.998    55.805

Fig.7(a). Testing the average end-to-end delay at network

62.01

53.21

46.65

63.6

68.32

55.13

53.14

51.14

45.73

45.73    51.14   53.14   55.13

46.65    51.24   55.01    58.56

53.21    62.01    63.6    68.32

^<— ♦ — SMAODV

— ■ — SAODV

—*—AODV

MAXIMUM MOVING SPEED [M/S]

Fig.7(b). The ratio of average end-to-end delay at network with different speeds

to determine a special mechanism for guiding the packets which guaranties energy saving and controlling the existing traffic at nodes.

As our practical results admit, our proposed algorithms have better productivity than the basic algorithm AODV. The ratio of the sent packets to the received packets in destination is more optimized comparing with AODV method and shows the fact that more packets are routed and smaller percentage of packets had been lost. Testing the amount of remaining energy in nodes shows that the total remaining energy in the nodes is higher in our proposed methods than AODV. Furthermore, with checking the end-to-end delay test, we concluded that our methods have less end-to-end delay than the basic method.

Considering all of the above matters, we can say that our introduced methods for finding several routes for sending data will help us to control the network traffic, energy management of network nodes, increasing the network life time and reducing the end-to-end delivery rate. Regarding the constraints of a network without infrastructure, such results are important achievements in these networks. In the end we conclude that our introduced methods will increase the network lifetime.