A Proposed Architecture for Efficient Data Delivery and Route Maintenance in a Sparsely Deployed Mobile Ad Hoc Network

Abstract

Mobile ad hoc networks have seen tremendous research being carried out looking into various issues in the area of routing, disruption tolerance and mobility control amongst other issues. MANET has a typical environment and in many works MANET is not treated as a case of infrastructureless network. This work aims to treat Ad Hoc networks differently than a Wireless Infrastructure Network. This work also aims at proposing a framework for route maintenance of a network of any size in case of sparsely deployed topologies and maintain the mobility of all the nodes to the advantage of the participating nodes.

1 Introduction

Mobile Ad Hoc Networks (MANET) are a collection of self-configuring mobile nodes which combine arbitrarily in any topology so that basic functions of a network are carried out and network is up for the duration of time for which it was established. MANETs are characterized by random mobility of nodes, frequent disruption in connectivity and limitation of resources such as buffer, battery back-up etc. and most importantly lack of infrastructure or backbone [1]. Each node in a MANET can perform network function of Packet forwarding and thus each node is acting like a Router, hence at each node route maintenance activity has to be carried out. Participating nodes in a MANET communicate with other nodes in the network through 802.11 MAC Layer [2]. They can be found as STA (Stations) which are part of IBSS (Independent Basic Service Set) in IEEE standards. A Collection of interacting IBSSs’ is represented as Mobile ad-hoc network where the Basic Service set functionality is without any backbone as illustrated in Fig. 1 ahead in this article.

Fig. 1

IBSS as ad hoc network (Source 802.11 standards)

Ad-hoc networks have been named like this as they are created on the go mostly without any prior planning and they are deployed for dealing with emergency situations mostly, like battlefields, or natural disaster sites earthquake and other natural calamities etc. These networks are operative for only as long as they are needed. In emergency situations like mentioned the network partitions can last long because thick deployment of nodes shall not be done and hence the main challenges in our view shall be efficient data delivery in sparse deployment, optimal usage of resources of node. However, it has been seen over a period of time that commercially Ad Hoc network have not been in use as much as in above mentioned scenarios.

Many articles [3–5] have been dealing with a high node density scenario there by proposing protocols such as DSR, DSDV and AODV. These protocols aim to solve problems of typically “connected networks”. A connected network would be one in which node density in the network deployment area is relatively high.

Some of articles go on to indicate TCP traffic [6, 7] in a MANET which is in clear opposite to what has been proposed in 802.11 standards where as we can see in Fig. 1. Stations are part of basic service set and interacting BSS’s combine to form an Ad hoc network. Since there is no portal involved here as is seen in [2] in case of wireless infrastructure network hence it can be safely concluded that Ad Hoc networks are a case of a infrastructureless network and TCP traffic can’t be a characteristic of Ad Hoc networks. Hence Ad hoc network looks more suited to conditions mentioned in Delay Tolerant Networks at [8], a separate research group is working on node mobility management, data buffering amongst others.

Rest of the paper is organized as follows. Section 2 briefly discuss about various issues that concern us in design of routing protocol for Mobile Ad Hoc network. Section 3 is about related works in the area of MANET and Delay Tolerant Network environment and their co relation. Section 4 mentions about existing drawbacks in the related works. Section 5 contains description about concept of remoteness and mobility management. Section 6 provides the protocol design and framework and Sect. 7 is the conclusion section.

2 Design Issues

The identified issues in design of a routing protocol are:

• A. Route Entries at a node: MANET nodes are constantly moving in random direction and due to changing topology paths keep on varying and it is needed to maintain the route entries on the move. Lack of infrastructure increases the need of accurate network mapping all the time so that network function is not hampered. But doing so should be with minimum overhead.

• B. Mobility: Nodes are mobile and this mobility can be put to use so as the network becomes self-organizing and stable over a period of time. Mobility control again relies on network mapping at each node but is constrained by limited battery power. Inclusion of extra control information in data packets for the purpose of self-organization shall cause faster depletion of battery and has to be optimized.

• C. Limited resources availability: Mobile Nodes have finite battery power and limited buffer and processing capacity. Any processing overhead would result in faster consumption of battery and any increase in battery or buffer at node would lead to loss of free mobility as payload of nodes will increase.

3 Related Works

Sparse node problem has been treated by deploying ferrying techniques in [9]. Message ferrying approach deploys set of special nodes called message ferries that exploits mobility to decrease delays. OPWP technique also uses this kind of approach in [10] where ferry nodes rather than being mobile all the time show controlled mobility around, optimized waypoints. Another technique which is very similar to [9, 10], uses data mules which are moved into a sensor field to facilitate traffic in a wireless sensor network [11], in which sensor field has a sparse deployment of nodes. Sensor nodes are pinned at one location and data mules act as carriers of information available at sensor nodes which are stationary. Ferry Access Points (FAPS) propose in [12] sticky transfers as a method to improve communication in DTN. In this node to ferry contact as and when it happens will lead to creation of a long duration contact resulting transfer of complete data. But, natural node movement is controlled during this sticky contact. Another approach is in [13] where throwboxes have been suggested in DTNs having mobile nodes so that larger contact opportunities are created and these throwboxes are present at advantage location provide routing and buffering.

In [14] DTN routing schemes are classified as deterministic, enforced and opportunistic. Deterministic routing schemes are used when a priori information about traffic demand and contact is known. Enforced Routing schemes deploy special purpose nodes to provide connectivity as already discussed in [9–13]. Enforced routing techniques also require beforehand information about design of routes or locations for placing throwboxes to facilitate traffic. Opportunistic routing schemes use flooding mechanism where multiple copies of each message is flooded in the network as provided in epidemic routing [15]. As proposed in [16] the approach aims to better [15] by limiting multiple copies being sent to next hops for better resource utilization. Another technique is proposed in spray and wait [17] in which replication of messages is present in network but the concern that how many messages stay replicated is again a concern and it is stated in [17] that source can’t decide how many copies of message can stay in network. ASBIT [18] is a recent technique that identifies the significance of time intervals between two exchanges and it utilizes the same interval to predict the number of inter node contacts within the estimated delivery and delay therein. In [19] the authors provide mechanism to source packets from nodes to a node as compared to node to a base station in DSG routing where traffic is sent from a node to a base station, a sensor node and deploys distributed caching. DSG-N² routing identifies social grouping among nodes based on contact patterns between nodes.

4 Observations to Related Works

These are:

• 1. Special nodes are made to travel in network and in event of failure of ferry node, data mule in [9, 11] the network operation would fail. Moreover in [11] the technique suggested is for specific case for wireless sensor networks. However, the concept that some node has to act as ferry is supported.

• 2. In [10] ferries stop at OPWP and wait for buisiness nodes to come at some point in network run time to offload nodes’ buffer. This waiting for nodes contributes to delay.

• 3. In [12] mobility of nodes is governed by movement of ferries only during contact time between ferry node and network node. This is a scenario to be replicated during entire duration of network but without ferry nodes, and only for duration of node to node to data transfer.

• 4. In [14] throwboxes are stationary ferries that occur to contact within the travel of a node, hence the node that facilitates traffic is stationary and offloads data on nodes by assuming that node is travelling in direction of destination specific traffic acquired by throwbox. Hence, throwbox technique is again waiting for favorable node to arrive.

• 5. Approaches provided in [16, 17] work on concept of multiple sends and in a sparse node deployment this flooding or controlled flooding is highly taxing on resources of mobile nodes and seems improbable too.

• 6. In [18] it overcomes the disadvantages of [17] by utilizing the inter contact delay and it is aimed to use this significant inter-contact time for network restoration.

• 7. In [19] the network is managed by caching at base stations as well node to node transfers on type of request basis which suggest that it is not a case of sparsely deployed network whereas DTN environment is a typical case of sparsely deployed topology.

5 Concept of Remoteness and Mobility Management

A node can be considered a transceiver with a range around it in a circular area with node acting as radial point. The range of transmission for a node is equal to radius of the circle. This imaginary circle moves along with node’s random movement. Since Ad hoc network will have node to node communication it means that receiver node has to be inside the circle of sending node for the duration of transfer. A remote node would be one that is outside the range of the broadcasting node and a node at relatively larger distance would be more remote to another node that is relatively nearer but still outside the range of the node.

Also, there can be scenario where node would be moving into the circle in the direction of center of the circle. In this scenario the node has to stop after coming inside the circle. This effort of controlling the receiver position inside the broadcasting node’s transmission range would be called as mobility management.

Here BSS1 has one node in it and the node in BSS3 is remote node for BSS1. For BSS2 the node on outside boundary is to be stopped and node has to be brought in after it reaches the boundary perimeter.

The following illustration will explain this concept of node mobility management (refer (Fig. 2)).

Let R be the radius of circle of Transmission range and there be defined a threshold distance D_th1 which is equal to R, i.e. D_th1 = R.

Now $\exists {\text{Y}}\,\varepsilon {\text{Y}}_{\text{k}} \,{\text{s}}.{\text{t}}\,\left| {{\text{Y}}_{\text{k}} \, - {\text{Y}}_{0} } \right|\, = \,{\text{Y}}_{\text{dis}} \,{\text{and}}\,\exists {\text{X}}\,\varepsilon {\text{X}}_{\text{k}} \,{\text{s}}.{\text{t}}.\,\left| {{\text{X}}_{\text{k}} \, - {\text{X}}_{0} } \right|\, = \,{\text{X}}_{\text{dis}}.$

Therefore,

$$ \surd \left( {{\text{Y}}_{\text{dis}} } \right)^{ 2} { + }\left( {{\text{X}}_{\text{dis}} } \right)^{ 2} {\text{ = R = D}}_{\text{th1}} $$

(1)

Let us maximum displacement threshold for any node at any location within the range is 90 % of R and minimum displacement threshold for node be 20 % of R. This can be put in inequalities 2 and 3 as below.

$$ \surd \left( {{\text{Y}}_{\text{dis}} } \right)^{ 2} { + }\left( {{\text{X}}_{\text{dis}} } \right)^{ 2}\,{<=}\,0.9 {\text{R}} $$

(2)

$$ \surd \left( {{\text{Y}}_{\text{dis}} } \right)^{ 2} { + }\left( {{\text{X}}_{\text{dis}} } \right)^{ 2} \,{>=}\,0.2 {\text{R}} $$

(3)

We shall term this as snoop location test that each node will do for its master node to get its coordinates as given by inequality 4 as under.

$$ 0.2{\text{R}}\,{<=}\, \surd \left( {{\text{Y}}_{\text{dis}} } \right)^{ 2} { + }\left( {{\text{X}}_{\text{dis}} } \right)^{ 2}\, {<=}\,0.9 {\text{R}} $$

(4)

If the condition is violated, the node shall reset its path to align with the master node and shall keep on doing so, till the next agreed time interval when One Hop Packets are broadcast and network topology is available afresh.

6 Protocol Design and Framework

In this section, the workflow of the algorithm is described on the basis of the following assumptions derived out of favorable scenarios in previous section.

• a. Network is sparsely deployed and here we model network for 4 nodes only.

• b. We assume that all nodes are aware of maximum network size which is 4 in this case.

• c. Nodes broadcast to other nodes there one hop neighbor information after fixed interval of time and network activity is suspended during this time interval.

• d. All nodes enter the network simultaneously and if any node is entering after some time the network has started functioning it will not straight way look to connect to some neighbor, though it will be listening to its neighbors if any. It will have to wait for time interval when one hop neighbor is being broadcast by its neighbor.

Algorithm: Since the network size is 4 and node are enumerated in given set N_i = (n1, n2, n3, n4,}. Each node shall maintain a 3 × 4 Stack of Booleans 1-D matrix for route maintenance, which is to be maintained at each node. Each row of stack matrix shall signify as nth hop entries where each column represents node $\varepsilon$N_i.

Tables 1 and 2 are route maintenance matrices for nodes, n1 and n2, where column are indicative of n1, n2, n3, n4 and rows are indicative of 1 hop neighbor, 2 hop neighbor and 3 hop neighbor. If any entry in table is 1 it means that corresponding node is a neighbor and row no will tell if it is 1-hop, 2-hop or 3-hop neighbor.

Table 1 Route Maintenance Entries in routing table for node n1

Table 2 Route maintenance entries in routing table for node n2

The entries in shaded part of Table 1 represent the presence of neighbor at a particular hop distance. From here onwards, only shaded portion of Table 1 is reproduced under different scenarios and significance of row and columns remains same.

Then, image of network for node n1 is in Fig. 2, and we assume nodes moves in direction of arrow. Let below be called Scenario A.

Fig. 2

Scenario depicting remote nodes and nodes within the transmission range

Zeros in last row of matrix for n2 signify that there is no three hop neighbor for node 2. Also it can be seen that same network image is available at node n1 and n2.

Let the below be called scenario B shown in Fig. 3 when nodes have moved to enter a new topology (Fig. 4).

Fig. 3

Node at center with threshold radials

Fig. 4

Scenario A

Now the matrix for node n1 and n2 for Scenario B is in Tables 3 and 4 respectively (Fig. 5).

Table 3 Route maintenance entries in routing table for node n1

Table 4 Route maintenance entries in routing table for node n2

Fig. 5

Scenario B

Here it can be seen that n2, n3 and n4 are connected in a looping topology and hence which route to be followed is not clear if say data is to be sent from 1 to 4 (Table 5).

Table 5 Notations used in algorithm

So, the following algorithm is proposed.

• Step 1. Node n $\varepsilon$ N_i transmits one hop packet containing 4-bit RH(n) frame along with Control information to each one hop neighbor during the interval already known to all nodes. All nodes n broadcast one hop information received from all sources to all their one hop neighbors except the node from which it came. The source and destination information is available in one hop packet in form of control bits.

• Step 2. Each neighbor node n accepts one hop information, removes control information and pushes RH(n) on NS(n) in modulo 4 order, s.t., rows RH(n) of NS (n) are in order (n + k) % 4 for k = 0, 1, 2, 3 where n is the node number.

Order is representative of the node number.

• 2 (a). If (n + k) % 4 equals ZERO, then set order n of RH(n) being pushed onto stack NS(n) as n = 4.

• Step 3. In NS(n) for node (n) set the nth column bit to ZERO to avoid loopback condition.

• Step 4. Start reading 4 × 4 NS(n) in row major order and preserve 1’s as they are encountered. For every node n $\varepsilon$ N_i don’t read the bit in nth column, and entry is NR whenever 1 is encountered.

• 4 (a). Preserve 1’s only if 1 is not encountered in previous row traversals, i.e., RST if already done a NR for 1 in same column.

• 5. Drop last row of matrix i.e. the 4th row in this case, NS(n) for network of size 4 is ready.

7 Results and Conclusions

We played this algorithm on a self-prepared computer program and found the algorithm working for a network of size 4 where duplicity of links was handled by passing only one hop information between nodes. In this way same network image is available to all nodes as we created AN(n) and BN (n) for all 4 nodes (Tables 6 and 7).

Table 6 Route maintenance entries in routing table for node n1

Table 7 Route maintenance entries in routing table for node n2

After, step 2 the following Tables 6 and 7 are created on nodes n1 and n2. As it can be seen these tables have four rows whereas the actual table that has route entries has three rows. One extra row has been created due to iterations in step 2 of algorithm.

The Tables 8 and 9 are received after the Step 4 and 5 of Algorithm is played. Tables 8 and 9 are representative of same network image for both node n1 and n2. The same network image results in zero duplication of messages in the network when network will be put in operation.

Table 8 Route maintenance entries in routing table for node n1

Table 9 Route maintenance entries in routing table for node n2

The network image emerging out of Tables 8 and 9 is given in Fig. 6.

Fig. 6

Scenario emerging for both n1 and n2

In this Paper we have tried to establish the Parameter of mobility by modeling node as a transmitter which transmits in one circular fashion and then we have tried to propose a routing protocol for the same. It is seen that duplicity of links is handled very well by the routing protocol and any node at any given point in life of network has same image of topology of the network. The controlled mobility feature allows the node to remain in close proximity to each other while data transmission is taking place. In our future work we shall propose packet format for the same and shall model it for varying network sizes.