J. Cent. South Univ. (2012) 19: 1577-1582

DOI: 10.1007/s11771-012-1179-y

Adaptive clustering hierarchy routing for delay tolerant network

TAO Yong(陶勇), WANG Xiao-fang(王晓方)

School of Information Science and Engineering, Hunan University, Changsha 410082, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2012

Abstract: Adaptive clustering hierarchy routing (ACHR) establishes a clusters-based hierarchical hybrid routing algorithm with two-hop local visibility for delay tolerant network (DTN). The major contribution of ACHR is the combination of single copy scheme and multi-copy scheme and the combination of hop-by-hop and multi-hop mechanism ACHR, which has the advantages in simplicity, availability and well-expansibility. The result shows that it can take advantage of the random communication opportunities and local network connectivity, and achieves 1.6 times delivery ratio and 60% overhead compared with its counterpart.

Key words: delay tolerant network; routing scheme; congestion control; hierarchy routing
 

1 Introduction

Delay tolerant network (DTN) is fundamentally an opportunistic communication system, where communication links only exist temporarily, rendering it impossible to establish end-to-end connections for data delivery. How to control the network congestion and improve the ability of packet operation is a concerned problem in DTN [1-2]. Routing strategy is mainly to determine the out-going path for the received packets. In DTN, the main principal for routing message is “store and forward” [3]. Each node in DTN stores incoming message in the buffer, and then delivers it to another desirable node towards destination whenever the contact is initiated. Intermediate node copies incoming message and work as relay node in order to increase the delivery probability [4-5].

Based on the strategies, routing in DTN is categorized into two main categories, flooding strategy and forwarding strategy [6]. Flooding strategy is based on the principal of replicating messages to enough nodes so that destination node must receive it [5]. Forwarding strategy uses knowledge about network to select best path to the destination. The controlled flooding scheme [7-9] and its optimization [10], are the basic kinds of dynamic routing methods, which deliver data packets by breadth-first searching. The effective range of routes increases in geometric progression. As a result, the data spread all over the network quickly with small delay. However, due to the broadcast, as the network grows, these approaches will produce a large amount of duplicated packets, which result in the increasing probability of network congestion. It is not suitable for large-scale network. The scheme of forwarding based on effectiveness adopts reasonable algorithm to select the best path and forward messages along the path. The shortest path routing is necessary to know the whole information of network, which is difficult to achieve for intermittently connected link and delayed DTN network. The drawbacks of given message delivery strategy are as follows:

1) Flatting. Most DTN protocols are “flat”, where every node plays a similar role in routing. The role of each node is the same when forwarding. The flat architecture is simple and effective in small networks, but not scalable to large size DTNs. It easily leads to the imbalanced consumption of resources, causing hot spots and congested nodes. Flat structure is not scalable, while clustering is the effective way to reduce network cost and improve scalability.

2) Hop-by-hop. Internet’s end-to-end multi- hop routing algorithm is not applicable for the opportunity communication with frequent disconnection. However, the hop-by-hop DTN routing mechanism does not support local connectivity owing to the lack of local multi-hop.

3) Exclusive. From the perspective of the routing strategy, each routing algorithm belongs to random routing mechanism or deterministic routing mechanism. The message delivery method for single and multiple copies is difficult to reconcile in one strategy.

Obviously, there exists a local network model in the real world, that is, a non-connected network can be divided into a series of locally connected subnets. There are some nodes in the subnets intermittently connecting to other subnets by moving [11] and other ways [12]. Clustering hierarchic scheme is an effective approach to reduce the network overhead and improve scalability. Therefore, in non-uniform DTN network, it is important to consider how to build a local area network, how to select the appropriate node carrying and transmitting the data in local area and how to combine hop-by-hop routing with multiple hop routing. It is conducive to utilize the precious connect opportunities to reduce link conflict and improve data transfer rate. Existing hierarchical methods can be divided into following three categories:

1) Traditional clustering algorithm. Various clustering algorithms, such as LEACH, have been investigated in the context of mobile ad hoc networks. However, none of them can be applied directly to DTN, because they are designed for well-connected networks and require timely information sharing among nodes.

2) Based on mobility pattern or social model, the method was proposed based on social network characteristics in real life [13]. Nodes in real-life tends to visit some locations more frequently than others. SPYROPOULOS et al [14] introduced the community- based mobility model, where each node has its own home location that it visits most frequently, along with several elsewhere locations. Clearly, if two nodes share the same home location, they have high chances to meet each other. Thus, real-life mobility patterns naturally group mobile devices into clusters. Reality mobile mode can be naturally divided into different clusters, however, in condition that the algorithm must be the serious mobile modern. The mobile related to properties of each node must be informed in advance.

3) Based on bottleneck nodes, under the condition that DTN has already been divided into different regional clusters, DANG and WU [15] developed a comprehensive mix routing protocol, providing fusion algorithm and messages scheduling strategy for ferry data, in order to maximize the effectiveness of ferry node. LEGUAY et al [16] developed an algorithm which maintains three queues: message, neighbor and key vector. When a node has a message to send, it firstly examines whether the destination node is in its neighbor vector. If so, it sends the message directly, or the message will be saved into vector and will be sent to the directly connected critical nodes.

In this work, a cluster-based hierarchical hybrid routing algorithm with two-hop local visibility for delay tolerant network was investigated. The basic effect is combined hop-by-hop mechanism with multi-hop mechanism. Each node can build its cluster by local information. The message in a cluster is delivered by multi hops with single copy, meanwhile the message delivery between clusters is hop-by-hop with multi-copy.

2 Two-hop neighborhood domain

2.1 Network model

DTN is an unstable connection network, which may vary with time. It can be defined as G(t)=(V(t), E(t)), which represents nodes and edges as V and E, respectively, where t is a nonnegative time variable. E(t)={(u, v):u, v∈V(t), and (u, v) is able to communicate during time t. ?T=[t₁, t₂] makes G(t₁)=G(t₂). At this point, the network node still exists an end-to-end path in a temporary period. PAN and CROWCRAFT [17] proposed a parameter m, which means the range of node neighbors. When m reaches a certain value, the network performance (such as average delay, transmission efficiency, the average probability of resulting data and network load) is similar with the global shortest path strategy. Taking the local visibility routing strategies only needs to know the local shortest path information of the target node, which is similar with the global shortest path routing.

2.2 Two-hop neighbor discovery

Two-hop neighborhood method can construct a visibility three-local-connected subnet, which is called an area. Each node periodically broadcasts NeighborDiscoverReq message to its two-hop neighbor nodes using fixed period schema neighbor discovery (FPSND). In this way, each node may periodically receive neighbor messages from its two-hop neighbor nodes, and then acquire the local connective area within distance of three. As shown in Fig. 1, the node a sends the NeighborDiscoverReq, whose TTL (the maximum hops of message) is set as two. This means that the neighbor information of a is sent to its two-hop neighbors so that a can obtain the topology information in a range of three-hop.

Fig. 1 Two-hop neighborhood diagram

The value of the period will influence the accuracy and real-time of neighbor’s discovery. When to send the NeighborDiscoverReq message can be determined on the transmission radium and the deployment of neighbors. Assume that the moving speed of each node is randomly distributed in [0, v], then the relative speed w of any pair of nodes is [0, 2v]. If the max distance to the farthest node is d in t₁, it is the time to send neighbor request to examine the fracture of the link at t₁+(r-d)/2vt. NeighborDiscoverReq message contains NID (the node identifier), NumNeighbor (the number of nodes’ adjacent neighbors), isPartitionNode (whether it is the two-hop key node), and TTL (the message’s maximum hops).

Although each node is of the same property, some of them have special significance to the whole network. On one hand, those nodes as the unique access path among two or more independent subnets, have an important effect on the topological structure; On the other hand, the ability of bottleneck nodes affects the whole performances of the network, such as the success rate of data transmission, congestion and delays. These special nodes are called articulation nodes. The basic question is which node is the topological articulation node.

Definition 1: The nodes, whose neighbors are divided into disjoint node sets and whose neighbors are not disjoints, are defined as two-hop articulation nodes.

3 Adaptive clustering hierarchy routing algorithm

Adaptive clustering hierarchy routing algorithm splits the routing of node into two parts: intra-domain and inter-domain. If the destination node is in the same area, intra-cluster forwarding routing strategy is executed, otherwise inter-cluster forward routing strategy is chosen to use. Any two intra-domain nodes have direct or indirect links to connect with each other. The intra-domain routing strategy uses the synchronous optimize-shortest-path method, and non-articulation nodes are prior to be chosen as the translation nodes to make the best of all nodes ability and improve the load balancing. In comparison, the exchange of information of the inter-domain nodes can only be achieved by a number of mobile nodes which carry messages. Besides the inter-domain routing strategy uses the asynchronous restricted flooding routing, it considers the relay nodes as translation points firstly. It passes the messages to node which has the maximum probability to encounter with destination, so as to enhance deliver probability.

3.1 Intra-cluster forwarding routing strategy

When a message is generated, it needs to be delivered to the destination node. If the message cannot deliver directly, then some relay nodes should be used. And the selection of the relay nodes is based on the shortest path algorithm. Local routing discusses the problem of how to build a communication path and then transfer information correctly from source to destination with the premise knowledge of intra-cluster topological information.

3.1.1 Improved shortest path algorithm

Fairness and network load balance are important issues in routing algorithm. The routing algorithm which ignores load balancing will bring about congestion, resulting in sharp decline of the network performance. Node betweenness and node degrees are positively correlated. The load of these nodes is large in the shortest path routing strategy, and it is needed to redefine the path cost function to improve it.

Definition 2: Supposing (i, x₁, x₂, …, x_n, j) is the node sequence from node i to node j, then the path length    L(i, j) is defined as

               (1)

where C(x_k) represents the link cost to node x_k; N(x_k) represents the number of x_k’s  neighbors; m is a parameter about articulation nodes. If x_k is the articulation node, set m>0, otherwise m=0. The α is an adjustable parameter. For a given α, the minimal path length is defined as a selected path. Clearly, the traditional shortest path routing strategy is a special case when α=0. The main purpose of parameter α is to make network traffic prefer to lighter load nodes, thus the route selection between the heavy load and light load node is weighed. When α>0, we can improve the transmission efficiency of the network and avoid congestion.

3.1.2 Algorithm combining shortest path with load balancing

A good routing algorithm can not only search a path from the source node to the destination node, but also try to make the network load balance. The shortest path algorithm mentioned above considers only the structural features, while ignoring the actual dynamics of the network load. We integrate shortest path and load dynamic routing strategy, using the parameter b for balance:

                 (2)

where L(i,k)_min represents the shortest path length between nodes x_k and x_i, and B(x_k) represents the queue length of node x_k. Select the neighbor of current node which has the minimum δ_k, considering the static path and dynamic data transmission simultaneously. So, it can be found that there is an effective path to improve data transmission performance. When b=1, the algorithm is same to the shortest path algorithm. Compared with the case of b≠1, the threshold of congestion can be greatly improved, which can reduce network congestion.

3.2 Inter-cluster forwarding routing strategy

Inter-cluster forwarding routing strategy is based on delivery probability to choose the next node. The delivery probability is related to link connectivity. To select the relay nodes, source nodes need to evaluate the delivery probability with the neighbor nodes, as well as delivery probability between the neighbor nodes cluster and the destination nodes cluster. That is, delivery probability is established on the entire region containing the source node members and the destination nodes. A member source node region may be connected with several members of destination node region. Thus, it’s necessary to evaluate the delivery probability of inter-region.

As shown in Fig. 2, the source node S belongs to region C₁, and its four adjacent regions are C₂, C₃, C₄ and C₅. The data generated by node S will be transmitted to those regions. It is needed to determine the selection problem of next hop node.

Fig. 2 Flooding among adjacent regions

Take region C₂ as an example. The two-hop neighbor of S which has communication opportunity with region C₂ is {S_i| 1≤i≤m}, the node set of region C₂ is {D_j | 1≤j≤n}, and the relationship value of node S to its member S_i is p_i. Set p^T=(p₁, p₂, …, p_m) as the delivery probability vector of node S_i and q^T=(q₁, q₂, …, q_n) as the delivery probability vector from nodes of region C₂ to node D; ω_i represents the delivery probability of node S_i and all neighbor nodes in region C₂, denoted by ω_i=(ω_i1, ω_i2, …, ω_in), and ω_ij represents the delivery probability from node S_i to node D_j. At this point, get the relationship assessment matrix of the adjacent neighbors of node S to all the members in region C₂:

             (3)

For the convenience of calculation, the vector p is extended to a diagonal matrix P:

                 (4)

Calculate the transmitted intensity of the steering vector T about node S, T^T=[T₁, T₂, …, T_m], in which

                                           (5)

Compare the component of the vector T, and select those whose component value is not less than T₁. That is, all the member nodes whose transmitted intensity is prior to all the member nodes of source node are regarded as transmitting nodes. S_T is transmitting node binding: S_T={S_i | T_i≥T₁, 1≤i≤m}. The articulation nodes in S_T are preferred as relay.

4 Results and discussion

4.1 Simulation results of intra-cluster forwarding routing algorithm control parameters

Suppose that a node can handle C messages at a time, and define R as data generation rate. As shown in Fig. 3, as a increases gradually, the threshold of data generation rate also increases. When a=0.8 or near, the threshold of data generation rate reaches its maximum. It’s clear that a=0.8 is an optimized parameter which can improve the transmission performance of network. On the other hand, the bigger the parameter a, the longer the path. In other words, the actual packet routing path deviates from the shortest path when a=0. As a result, although the routing strategy can increase the congestion threshold, it increases the expanse of the shortest path.

Fig. 3 Effect of parameter a

4.2 ACHR simulation results and analysis

If the cache of node is unlimited, Epidemic routing algorithm submits the highest delivery rate. This is because the flood transmitting method is used by Epidemic routing algorithm. Flooding algorithm copies the message and transmits it to all the encountered nodes. Meanwhile, the relay nodes transmit the message to the next relay node promptly, delivering the message at the maximum degree, thus the message submit rate reaches the highest and delay is minimized. But Epidemic routing will generate a lot of redundant copies, and will sacrifice a lot of storage, bandwidth, energy and other network resources, as shown in Figs. 4 and 5.

Fig. 4 Message redundancy

Fig. 5 Successful message ratio

PROPHET routing algorithm is based on delivery probability to choose the next relay node. Thus, the total number of message copies is limited, with the decrease in the number of nodes which are responsible for delivery. At the same time, transmission delay will increase. However, as shown in Fig. 5, Epidmic routing algorithm is less than PROPHET routing algorithm in performance because of the buffer overhead. In another case, message queuing contributes to the message delay increasing, as shown in Fig. 6. In DTN, this kind of resource-constrained network environment, consuming too much resources, will largely affect the delivery of message. ACHR routing proposes a stable and high performance delivery rate, because of the combination of optimal routing and flooding. In sparse condition, the effect is not very significant. However, in the condition of higher node density and stronger community, it can maintain a steady transmission rate and delay.

Fig. 6 Average delay

5 Conclusions

1) ACHR divides the node routing into intra-domain and inter-domain. If the destination node is in the region, the intra-domain routing strategy will be executed. Otherwise, choose the inter-domain routing strategy.

2) ACHR algorithm is a kind of hybrid routing protocols, which has the advantages of both active routing and reactive routing protocol. The major contributions of ACHR are the combination of single copy scheme and multi-copy scheme, the combination of hop-by-hop and multi-hop mechanisms.

3) ACHR is a distribution algorithm without global information, which is simple and scalable.

References

[1] FALL K. A delay-tolerant network architecture for challenged internets [C]// Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2003: 27-34

[2] SHEN Jian, MOH S, CHUNG I. Routing protocols in delay tolerant networks: A comparative survey [C]// Proceeding of 23rd International Technical Conference on Circuits/Systems, Computer and Communications. Shimonoseki: ITC-CSCC, 2008: 1577-1580.

[3] D′SOUZA A J, JOSE J. Routing approaches in Delay Tolerant Networks: A survey [C]// Proceeding of International Journal of Computer Applications. New York: FCS 2010, 2010, 17: 9-15.

[4] JAIN S, FALL K, PATRA R. Routing in a delay tolerant network [C]// Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2004: 1023-1030.

[5] VAHADT A, BECKER D. Epidemic routing for partially connected ad-hoc networks [R]. Tech Report CS-200006, Duke University, 2000

[6] BALASUBRAMANIAN A, BRIAN N L, VENKATRAMANI A. DTN routing as a resource allocation problem [C]// Proceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2007: 373-384.

[7] SPYROPOULOS T, PSOUNIS K, RAGHVENDRA C S. Spray and focus efficient mobility-assisted tolerant networks [C]// Proceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications. New York: ACM, 2007: 79-85.

[8] WU J, WANG N. A-SMART: An advanced controlled-flooding routing with group structures for delay tolerant networks [C]// Proceeding of 2010 Second International Conference on Networks Security. Wireless Communications and Trusted Computing. Wuhan: IEEE, 2010: 192-196.

[9] BURGESS J. MaxProp: Routing for vehicle-based disruption- tolerant networks [C]// Proceeding of 25th IEEE International Conference on Computer Communications. Barcelona: IEEE, 2006: 1-11.

[10] LIU C, WU J. Scalable routing in delay tolerant networks [C]// Proceedings of the 8th ACM International Symposium on Mobile ad hoc Networking and Computing. Montreal: ACM, 2007: 51-60.

[11] [11]LINDGREN A, DORIA A, SCHELN O. Probabilistic routing in intermittently connected networks [C]// Proceeding of first International Workshop on Service Assurance with Partial and Intermittent Resources. 2004: 239-254.

[12] CHAINTREAU A, HUI P, CROWCROFT J, DIOT C, GASS R, SCOTT J. Impact of human mobility on the design of opportunistic forwarding algorithms [J]. IEEE Transactions on Mobile Computing, 2007, 6(6): 606-620.

[13] KIM M, KOTZ D, KIM S. Extracting a mobility model from real user traces [C]// Proceeding of 25th IEEE International Conference on Computer Communications. Barcelona: IEEE, 2006: 17-21.

[14] SPYROPOULOS T, PSOUNIS K, RAGHAVENDRA C. Performance analysis of mobility-assisted routing [C]// Proc MobiHoc, 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing. Florence: ACM, 2006: 49-60.

[15] DANG H, WU H. Clustering and cluster-based routing protocol for delay-tolerant mobile networks [J]. IEEE Transactions on Wireless Communications, 2010, 9(6): 1874-1881.

[16] LEGUAY J, FRIEDMAN T, CONAN V. DTN routing in a mobility pattern space [C]// Proc WDTN 2005 ACM SIGCOMM Workshop on Delay-tolerant Networking. Philadelphia: ACM, 2005: 276-283.

[17] PAN H, CROWCRAFT J. Bubble rap: Social-based forwarding in delay tolerant networks [C]// Proceedings of the 9th ACM International Symposium on Mobile ad hoc Networking and Computing. Hong Kong: ACM, 2008: 241-251.

(Edited by DENG Lü-xiang)

Foundation item: Project(531107040202) supported by the Fundamental Research Funds for the Central Universities of China

Received date: 2011-12-02; Accepted date: 2012-03-20

Corresponding author: TAO Yong, PhD; Tel: +86-731-88825889; E-mail: ytao@hnu.edu.cn