Research and Reviews - International Journals

International Journal of Innovative Research in Computer and Communication Engineering

Menu

ISSN ONLINE(2320-9801) PRINT (2320-9798)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Implementation of E2AODV Protocol for Load Balancing In Cluster Ad-Hoc Network

A.S.Narmadha, C.Vasanthapriya, D.Sangeetha
  1. PG Scholar, Karpagam University, Tamilnadu, India
  2. PG Scholar, JSRGI, Tirupur, Tamilnadu, India
  3. AP Deartment of ECE, Karpagam University, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering

International Journal of Innovative Research in Computer and Communication Engineering

Abstract

In mobile ad hoc networks there are a number of challenges in providing quality of service routing with energy efficiency and load balancing. Most routing protocols do not consider the problem of load balance. In this paper we propose an E 2 AODV algorithm for balancing the load using ACO technique in cluster based mobile ad-hoc networks. Clustering makes possible hierarchical routing in which paths are recorded between cluster-heads Instead of nodes. This reduces routing overheads. Presence of an unstable and non-reliable cluster-head degrades the performance of the network since cluster-heads of the network take active role in routing messages between a source destination pair. The proposed algorithm chooses the most reliable and stable node as cluster-head depending on four criteria i.e. stability, battery power, degree, and trust value of the node. It also uses a multi agent based routing algorithm to generate load balanced routes between source and destination in cluster-based network. This study presents a scheme to balance the load with energy efficiency considering both congestion and the nodes energy usage. A threshold value was used to judge if intermediate node was overloaded, variable and changing along with nodes interface queue length around the backward path. E2 AODV protocol chooses an optimum path with low energy usage. It provides a better scheme to balance the load with energy efficiency and packet delivery ratio. Performance of this algorithm was compared with AODV protocol. It can be further enhanced as a secure routing protocol for mobile ad-hoc networks.

Keywords
MANET, Dominating Node, Cluster-head, Gateway node, Routing protocol, Ant Colony Optimization, Load balancing, queue length, energy consumption

INTRODUCTION
A Mobile ad-hoc network is a collection of wireless mobile nodes, forming a temporary network without the use of fixed network infrastructure and operating on limited amount of battery energy consumed for transmitting a packet. Protocols are classified as table driven and on demand routing. The area in which mobile ad-hoc network has wide applications includes battlefield, emergency, search rescue operation and data acquisition in remote areas. Cluster-heads of the clusters take active role in routing messages between a source destination pair. Gateway nodes are used for intercluster communication. In this algorithm clustering set up phase is accomplished by using dominating set of nodes. Gateway nodes are also selected from the set of dominating nodes. It also uses a multi-agent based routing algorithm using ACO to generate load balanced routes between source-destination pairs in a cluster based network. In this study, we propose load balance in proportion to their residual energy and received signal strength. The objective is to assign more loads to under utilize paths and less load to over committed paths so that uniform resource utilization of all available paths can be ensured. Load balancing is especially useful in energy constrained networks because the relative energy level of the nodes does not affect the network life time more than their absolute energy level. E2AODV provides multiple routes to a destination, to select a single route with low hop count and discards higher hop count

II. RELATED WORK
A categorized review covering the basic routing protocol, cluster based routing protocol is presented in this section.

2.1. Basic Routing Protocol
Destination Sequenced Distance Vector (DSDV) routing protocol is one of the first routing protocols for ad hoc networks. A number of routing protocols have been proposed based on this distance-vector approach, e.g. the Extended Bellman-Ford (EXBF) algorithm. The EXBF protocol is free from routing loops and count-to-infinity problem
Dynamic Source Routing (DSR)[9] protocol is an on-demand protocol that establishes a route by flooding route request packets in the network. The major limitation of this protocol is that the route maintenance mechanism fails to repair a broken link locally. Ad hoc On Demand Vector (AODV) [7, 8] routing protocol offers loop-free routes even while repairing broken links and is also scalable to a large extent. One of the disadvantages is that the intermediate nodes may have stale entries leading to inconsistent routes.

2.2. Cluster based routing Protocol
The basic routing protocols show degraded performance as the number of nodes increases. Individual nodes face power shortage due to extra load. The cluster based approach tries to reduce the load on individual nodes, as well as increases scalability and efficiency of routing protocols in mobile ad-hoc networks. The two main tasks involved in maintaining a cluster based network are finding the cluster-head nodes and partitioning the network into clusters. The following section presents review of cluster based routing protocols.
CBRP is the example of this type of routing protocols. CBRP divides the nodes in ad-hoc network into a number of disjoint or overlapping clusters. Every node upon receiving “HELLO” message from its neighbour compares its own id with other. If a node distinguishes its own id is the lowest id between its neighbours, this node declares itself as the cluster head. A cluster-head is elected for each cluster to maintain cluster membership information. Inter-cluster routes are discovered dynamically using the cluster membership information kept at each cluster-head. A cluster-head elects a gateway node to communicate with other cluster-heads. CBRP is based on source routing similar to DSR. This CBRP protocol efficiently minimizes the flooding traffic during route discovery and speeds up route discovery process. Too much traffic due to interference is the shortcoming of this protocol

2.3. DEFINITIONS
Definition 1: Mobility of a node i having n number of neighbours is defined as the summation of difference of distance computed between the node and all its neighbours during time interval Δt, i.e., mobi=Σs=1..n dist(i,s) where, dist(i,s)=|dtsi - dt+Δtsi| where s is a neighbour of node i , dtsi indicates distance between node s and node i at time t. The distance is calculated from the location co-ordinates of the nodes at that instant of time. Stability of the node is defined as the inverse of its mobility.
Definition 2: Probability of concentration of red and blue pheromone between source node i and destination node j is defined in the following way:
rprobij⓿⓿ red ij / phsumcurrent
bprobij⓿⓿ blueij / phsumcurrent
phsumcurrent⓿⓿ phsum prev⓿⓿ red ij⓿⓿ blueij
where, phsumprev is the total amount of red and blue pheromone deposited between node i and next hop node j at time t.
Initially phsumprev= 0.
phsumcurrent is the total amount of red and blue pheromone deposited between node i and next hop node j at time t+Δt. redi,j: It defines red pheromone value of the link between node i and next hop node j . It is initialized with summation of trust value and battery power of node i.
bluei,j : It defines blue pheromone value of the link between node i and next hop node j. It is initialized with summation of degree and stability of node i .
rprobi,j is the probability of deposition of red pheromone between node i and next hop node j.
bprobi,j is the probability of deposition of blue pheromone between node i and next hop node j.These red and blue pheromone probabilities are used for path selection by red and blue ants respectively
Definition 3: A node i is dominating if its weight crosses threshold limit. Weight of the node i depends on its trust value (tai), battery power (bpi), degree (degi) and stability (1/mobi). Dominating status will be determined using the following relations and the logic:
Weight of node i i.e
Wi⓿⓿ tai⓿⓿ deg i⓿⓿1/ mobi⓿⓿ bpi
select⓿⓿ (1/ p)⓿ j⓿⓿1W j
Where,
p is number of the neighbor nodes of node i.
if Wi >=select, Node i is declared as the dominating node .
Definition 4 : Trust value tai of a node i is defined as follows:
tai⓿⓿ forward _ counti / tot _ forward _ message

III. PROPOSED WORK

3.1. DESCRIPTION OF PROPOSED PROTOCOL
Proposed protocol is divided into following three sub-sections i.e.: Initialization of cluster formation, Entry of a new node and Routing protocol
I. Initialization of cluster formation
Initialization of cluster formation is divided into three components. Assign-weight( ) and Initialize-set-of-clusters ()
i. Assignment of weight to each node in the network (Assign-weight( ))
Step 1: Any node i advertises its presence by broadcasting a NEIGHBOURREQUEST message whose format is {sequencenumber, node-id-i}.
Step 2: The nodes within one hop distance send an ACK message of format {sequence- number, node-id-i, first-hop-id} to the initiator node with in a predefined time period.
Step 3: All such nodes are added to the neighbour list of the node i.
Step 4: Monitor observes mobility of the initiator node for some time interval tmon and then calculates its mobility by using Definition 1 [Section 4.3].
Step 5: During this period tmon Monitor sends some messages to another node present in the neighbour list using node i as the intermediate node.
Step 6: Depending on the number of successful transmission of a number of messages, Monitor assigns a trust value to the initiator node using Equation 4.6 in Definition 6.Monitor calculates weight of the node i using Equation 4.4 in Definition 5[Section 4.3]. If weight of the node is greater than select [Definition 5, Section 4.3], the status of the node is a dominating one by Definition 5 [Section 4.3].
Step 7: Monitor sends weight and status of the node i to the node i. Thus, the node i is aware of its weight and status.
Step 8: The process from step 1 to step 8 will be repeated for every node present there.
Step 9: Stop.
ii. Set of cluster formation (Initialize-set-of-clusters( ))
Step 1: Some nodes which are separated among themselves by more than 2r hop distance are selected randomly. Procedure Initialize-cluster ( ) in subsection 4.4.1.B is executed for each of the selected nodes which leads to form a set of clusters with their members, stable cluster-heads and gateway nodes in the network for a specified time duration
Step 2: After a specified time duration, the whole process of Assign-weight( ), and step1 of Initialize-set-of-clusters() is executed to form the new set of clusters in MANETs and this process will go on continuously
iii. New node entry within a cluster (New-entry( ))
Step 1: Step 1-Step 7 of Assign-weight ( ) will be followed considering new node as node I in Assign-weight ( ).
Step 2: Monitor of the new node transfers weight and status of the new node to the cluster- head and also to the new node.
Step 3: If weight of the new node is greater than that of the present cluster-head, the new node advertises itself as new cluster-head and requests the present one to send all neighbor list and gateway members’ list to it. Old Cluster-head sends them to the new Cluster-head.
Step 4: Stop

II. ROUTING PROTOCOL
Routing protocol will be governed by the algorithm Route-Cluster( ). Route-Cluster( ) during its execution may call another module gateway-route( ) and ACO-Route( ) which are described later
i. Module Route-Cluster ( )
Step 1: Each node in network maintains two pheromone tables-Red and Blue. Each entry of red pheromone table is initialized with summation of trust value and battery power of the node. On the other hand each entry of blue pheromone table is initialized with summation of stability and degree of the node
Step 2: For a particular source-destination (S-D) pair, source informs the destination address D to its respective cluster-head (say ch-idi)
Step 3: If the destination does not belong to this cluster-head ch-idi , ch-idi calls gateway- route( ) which finds the path from source-cluster-head ch-id i to the destination cluster- head ch-idm via intermediate gateway nodes and cluster-heads, CH = ch-idm ; Else CH = ch- idi
Step 4: Cluster-head CH calls ACO-Route ( )
Step 5: Stop
ii. Module Gateway-route ( )
Step 1: Cluster-head Ch-idi of cluster i communicates the destination address to the respective gateway node(s).
Step 2: Gateway node Gi of ith cluster sends ROUTEREQUEST packet to the gateway node G k of adjacent (say, kth) cluster. G k communicates the destination address to its cluster- head ch-idk.
Step 3: If destination is not present in its cluster, step 1- step 2 will be executed again using the cluster-head Ch-idk as the communicating cluster-head and this process will go on till destination-cluster-head is reached
Step 4: Destination–cluster-head returns ACK message to ch-id i backtracking in the same route traversed before.
Step 5: Stop
iii. Module ACO-Route ( )
Step 1: q is initialized with 0. /* q stands for number of messages to be sent */
Step 2: CH initializes variable v with 0 and 1 (in toggling mode) for alternate messages respectively.
Step 3: If (v=0)/ (v=1) CH generates red/(blue) ant and calculates probability of concentration of red/(blue) pheromone rprobCH,,j/(bprobCH,,j) on each available link between CH and next hop node j using Definition 4 [Section 4.3]. Red/(blue) ant selects link where rprob CH,,j/ (bprob CH,,j ) is maximum amongst all available links and sends qth/ (q+1)th
message with this link. On any link emanating from CH to next-hop node j if (red CH,j +blue CH,j >= (rmax + bmax), that link is considered as blocked temporarily.
Step 4: When red/(blue) ant selects k as the next hop node it deposits red(blue) pheromone between link CH and k. Rate of deposition of pheromone amount is inversely proportional to the cost of the link cost CH,,k which helps ants choose lowest cost path. It is calculated as follows:
Step 5: q is incremented. If q<x step 4 & 5 are repeated until all messages are sent to next- hop node k from CH.
Step 6: Battery power consumed by CH is computed using Definition 3 [Section 4.3]which will be used later for selecting cluster-head in next session.
Step7: During execution of step 4-6, step 7 is executed in parallel. After each specific interval, red/(blue) pheromone is evaporated from all available links(j) emanating from CH
Step 8: CH is assigned the value of k. Step 3 to step 7 will be executed by next hop node k for each message and battery power consumed by next hop node k is computed by using. After each Δt time interval red/(blue) pheromone is evaporated from all available links(j) whose amount is proportional to the cost k,j using similar equations mentioned in step 7.
Step 9: Step 2 to step 8 are repeated until all messages reach the destination node D.
Step 10: Stop

3.2. LOAD BALANCING PROTOCOL
The proposed protocol E2AODV will make the following changes to the existing AODV protocol:
⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿Paths are selected based on the hop count and queue length
⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿Load is balanced via alternate paths if queue length processes a certain threshold
value
⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿RREQ packets are forwarded or discarded depending on the queue length
⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿⓿Based on the threshold value the route request packets will be forwarded
⓿⓿ Based on the threshold value the route request packets are forwarded. Further the node’s energy is compared with threshold energy. If the node’s energy is less than the threshold energy than the packets are transmitted or less the packets are dropped.

IV. SIMULATION RESULTS
This protocol is simulated in NS2.29. Simulation environment of this protocol is Fedora 9. We use IEEE 802.11 for wireless LAN as MAC layer. The channel capacity of mobile node is 2 Mbps. In our simulation mobile nodes move in a 600*600 m2 region for 125 second simulation time. Mobility model is considered here as random waypoint. It is assumed that each node moves independently with the same average speed 10 m/s and pause time is 0-25 second. No path loss is considered. The network size is varied as 10, 20, 30, 40 and 50 nodes. The simulated traffic is constant bit rate (CBR). Table 1 shows the simulation setting of the network environment.
a. Mobility Versus Throughput
This section compares proposed protocol E2AODV with AODV. AODV are known for their routing efficiency in terms of delivery rate. Figure 1 shows this comparison of the proposed protocol with AODV and E2AODV. AODV is not cluster based routing protocol. In case of cluster-based routing protocols CBRP and CLAR, some time is required for cluster formation and cluster-head selection. Performance of AODV is best in comparison to CBRP and CLAR when number of nodes is small like 20. But when number of nodes in the network is more than 20, delivery rate of CLAR is always better than AODV, since clustering increases efficiency and scalability of routing protocol in mobile ad-hoc networks.

V. CONCLUSION
Proposed protocol combines clustering approach with load balancing in the network. This protocol selects stable and reliable cluster-heads and gateway nodes. Cluster formation, stable and reliable cluster-head selection, gateway node selection are main objectives of this clustering approach. On the other hand routing in this protocol is implemented applying agent based ACO technique. Here two different colored ants are used for balancing load and reducing congestion in the network. Thus this protocol takes the advantages of both cluster based approach and agent based ant colony optimization technique and applies it successfully in MANET. It has been observed that number of dominating nodes in CLAR does not increase rapidly with increase in number of nodes in MANET. This result ensures that number of clusters also does not increase rapidly with increase in number of nodes and in turn overhead remains low in the network. In terms of control packet overhead, E2AODV has shown better result than AODV.

Tables at a glance
Table icon
Table 1
 

Figures at a glance
Figure 1 Figure 2 Figure 3
Figure 1 Figure 2 Figure 3
 

References