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.

MANAP: An Effective and Self-Configuring Protocol for Dynamic Node Addressing In MANETs

Pradyumna Rao D1 and Raghavendra T.S2
  1. 2nd year M.Tech (CNE), Dept of Computer Science & Engg., Cambridge Institute of Technology, Bangalore, India
  2. Asst. Professor, Dept. of Computer Science & Engg., Cambridge Institute of Technology, Bangalore, India
Related article at Pubmed, Scholar Google

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

Abstract

Mobile Ad hoc networks face serious drawbacks regarding the allocation of addresses to the nodes. This challenge is mainly because MANET nodes are primarily distributed and they do not have predefined infrastructure. The existing ad hoc network addressing protocols have not been completely successful in handling address collisions because of leaving and/or joining nodes, and frequently occurring network partitions. To overcome such undesirable scenarios, we propose an efficient protocol based on a distributed database containing addresses stored in filters. This approach will allow the network to be functional despite frequent network partitions and packet losses. We consider the cases such as initializing a network, merging of existing partitions and joining of new nodes in a network for evaluating the performance of our protocol. We can prove through simulation results that our protocol is highly efficient in handling the address collisions and reducing the control traffic load.

Keywords

MANETs, distributed addressing, address collision

INTRODUCTION

Mobile Ad hoc Networks (MANETs) are auto-configuring wireless ad hoc networks of mobile devices requiring no previously established infrastructure. Since MANETs lack a centralized administration[1], each node in the network will actively participate in routing, thus playing the role of an active router. Such a de-centralized and dynamic administration of MANETs have greatly contributed towards distributed applications such as Military/ Tactical MANET, internet based MANET (iMANET), Vehicular Ad hoc networks (VANET), disaster recovery and so on.
Since the nodes in a MANET are free to move in any direction, the network is subject to frequent partitions. The mobility of the nodes can cause them to join or leave a network which often results in the disordering of the MANET control. Due to the absence of a centralized administrative server, MANET initialization is also a challenge.
Since each node in a MANET acts as a router, each node needs a unique network address. But the address allocation to these mobile nodes are not as simple as in centrally administered networks. The distributed and self organizing nature of MANET nodes is always a bottleneck in address assignment.
We propose an effective protocol called MANET Node Addressing Protocol (MANAP). In our proposed protocol, we extend the functionalities of the Filter-based Addressing Protocol (FAP)[2]. This protocol makes use of filters which are used to store a highly distributed database containing already assigned addresses in the network. We propose a new kind of filter called Linear filter along with the Bloom filter. These filters ensure unambiguous address allocation for the nodes which are joining the network. They also detect the address collisions of the nodes whenever two or more partitions merge. Hence our proposed protocol allows the mobile nodes to check the duplication of addresses. In order to diminish the storage overload of filters, we propose the usage of a unique Partition identification Code (PARCODE). The filter is hashed and the resultant hash value is the PARCODE. Hence the nodes can easily identify the network partitions and thus avoid the address collisions. The simulation results prove that the proposed protocol achieves a very low communication overhead, low storage requirement and low latency.
The remainder of this paper contains the following sections: We discuss the related work in section I. Proposed algorithm and pseudo code are detailed in section II and section III respectively. Section IV depicts the simulation results. Finally we conclude the paper and discuss about the future scope of this paper in section V.

RELATED WORK

Since the MANETs are distributed in nature, there is no centralized administrative entity to monitor the configuration of the network nodes. Hence there is always a high probability of address collision by newly joining nodes, as shown in the birthday paradox[3]. This birthday paradox guarantees the detection of address replication with high probability. The paper [4] discusses the Duplicate Address Detection (DAD) which is the basis for address auto configuration in distributed networks. Here the allocated addresses are never stored unlike in the proposed protocol. In this protocol, each newly joining node chooses an IP address and broadcasts this address using an IP address query (IPQRY) message, so that all other nodes in the network are notified about this address. If any other node in the network has the same IP address as the joining node, it alerts the joining node regarding the address collision by replying with an IP address duplication (IPDUP) message. The paper[5] discusses in detail about handling the network partitions in a MANET. In this paper each partition is assigned a unique network identifier (NID). Each newly joining node repeatedly broadcasts a configuration request (CREQ) message until a neighbour responds with a hello message. Then the neighbour sends the necessary configuration parameters to the joining node which is then identified by the {IP address, NID} pair. The paper[6] proposes to enhance the detection performance of a partition merge through MANETconf protocol. According to MANETconf, each node in a MANET maintains two lists : Allocated_List and Allocated _Pending_List. When a new node arrives at a MANET, it repeatedly broadcasts the address request message to its neighbours. One neighbour responds to the address request message by choosing am address which is then broadcasted to the whole MANET by the responder. This chosen address is then added to the Allocated_Pending_List until the responder gets positive replies from all the nodes. Once it is confirmed that the chosen address is not assigned any other node, that address gets allocated to the joining node. Then the address is removed from the Allocated_Pending_List and added to Allocated_List, and then it is again broadcasted to all the nodes so that they too can update the lists.

PROPOSED WORK

The aim of the proposed MANAP is to efficiently auto-configure the addresses of the MANET nodes by resolving address duplications in case of node joining or partition merging events. To accomplish these goals, address filters are maintained at all the nodes across the network. We propose to use two kinds of filters :
(a) Bloom Filter
(b) Linear Filter
Bloom Filter: The Bloom filter is a probabilistic data structure that is used to test whether an element is present in a set or not[7,8]. We consider the bloom filter to consist of a x-bit vector to represent a set S={s1,s2,s3,...sy} of y elements. All the x-bits are initially set to 0. A set of hash functions f1,f2,...fk are fed with the elements of set S and the output of the hash functions are distributed evenly over the x-bit vector. Then, all the hash functions are used to hash every element si ? S whose output is represented by a bit which is set to 1 in the x-bit vector. We can check if an element si ? S by verifying whether all the bits in the vector corresponding to the locations f1(si), f2(si),...fk(si) are set to 1 as shown in Fig 1. The element si is not considered to be in the filter even if at least one bit is set to 0.
We can obtain the probability of a specific bit in the vector is 0 even after y elements are inserted, explained by Mitzenmacher and Broder. This probability can be given by the following expression:
equation
We can also find the probability of the false positives which is the probability that all the k-bits representing an element which is not inserted, are set to 1. In other words, this probability P(+ve) can be given by the following expression:
equation
Thus the P(+ve) increases with the increase in the number of elements in S, or with the decrease in the vector size x.
Linear Filter: This is the proposed filter which stores the addresses according to the linear order of the addresses. The first address in the address list is concatenated with a vector of size q-bits. We call the concatenated address as the leader element (s0) and the vector size (q-bits) represent the address range. We consider the suffix of each address in the list which is represented by a single bit. Each of the address suffix can be indexed by δ, which gives the distance between leader suffix s0suf and the present element suffix sisuff. If a bit indicates 1, then the address suffix represented by that bit belongs to the filter. In the opposite case, then the address is not said to be in the filter. Since the representation of each available address is deterministic, the concept of false positives and false negatives does not exist.
The representation of the linear filter is as shown in the above figure.

PSEUDO CODE

Step 1: Node no arrives at a network at current time TC
Step 2: no listens to the network for a time period TW
Step 3: If TC > (TC+TW) and Hello_message_received=false
Make no as the initiator ni;
Form the network;
end if
Step 4: else if TC <= (TC+TW) and Hello_message_received from initiator ni=true
Make no as the joining node nj
Step 5: ni randomly chooses an address Ao
ni broadcasts address request message MREQ advertising Ao to all other initiators NM times
Other initiators broadcast MREQs advertising their chosen addresses Ai NM times
Step 6: ni receives MREQs from other initiators
Step 7: ni compares Ai s with Ao
Step 8: if Ai= Ao
goto Step 5
end if
Step 9: else
Assign Ao to nj
end if
end if

SIMULATION RESULTS

The proposed MANAP was implemented in ns 2 simulator. In the simulation results, we try to compare and analyze the efficiency of MANAP, DAD, DAD with partition detection (DAD-PART) and MANETconf. Efficiency is measured by considering the parameters like average delay and control overhead.
Fig 3(a). plots the number of control messages against the number of nodes for various protocols. As per the results, DAD-PART suffers the greatest overhead as compared to other three protocols. The DAD protocol achieves very less control overhead than MANAP when the number of nodes in the MANET is in between 0 and 60. However, as the number of nodes in the network starts exceeding 60, the MANAP marginally takes the lead in reducing the control overhead. It can be noticed very clearly from the above graph that as the number of nodes approaches 100, the control overhead difference between MANAP and DAD protocol is very less. That is, the MANAP slightly overtakes the DAD protocol in reducing the overhead when the node count nears 100.
Fig 3(b). plots the average delay against the number of nodes for various protocols. As per the results, DAD-PART has the highest average delay. Hence it is not the ideal protocol for MANET node address allocation. If the number of nodes are less, MANAP has the second highest delay. As the number of nodes approaches 80, the delay is lowest for MANAP. Thus, the MANAP may not prove to be an optimal choice to reduce the average delay in MANETs when the number of nodes are less than 80. But it is very efficient for the networks with the number of nodes exceeding 80.

CONCLUSION AND FUTURE WORK

We proposed and analyzed the MANAP, which is self-configuring and dynamic in nature. It is very well suited for MANETs which encounter frequent network partitions and have leaving and/or joining nodes. The proposed protocol uses address filters to store the available addresses which highly reduces control load and address duplications. Also our protocol is very much robust, given the continuously changing topologies of MANETs. The filter signature produced by filter hashing provides better unique representation of nodes in a MANET. Even the protocols such as DAD has a low control overhead, but it can not be efficient in case of network partitions. Hence it is reasonable to conclude that the MANAP is best suited for the node addressing in MANETs.
But the MANAP is not suitable for MANETs with a low node count as it is evident from the simulation results plotted in the previous section. Hence, in the future, we would like to optimize the performance of our proposed protocol even when the network has a low number of nodes.
 

Figures at a glance

Figure 1 Figure 2 Figure 3 Figure 4
Figure 1 Figure 2 Figure 3A Figure 3B
 

References