Congestion aware routing algorithm for delay-disruption tolerance networks

1) Address: Routing relies on addressing and addressing is related to the format of address. A DTN node uses a form like (, ) for the addressing format. To maximize the message transmission, when its destination node is in external

Table 1 Attribute hierarchical model

region, a DTN node prefers to send the message to the external region. Otherwise, it will send the message to the inner region first.

2) Bundle factor: It is mainly related to the survival period, size and priority of messages.

 is equal to bundle size/bundle average size; T_TL is equal to survival time/average time and  is equal to message priority/average priority.

3) Node factor: C_h denotes whether it is a cluster head. Nodes can be divided into different types such as normal nodes and cluster head nodes.  denotes the maximum storage space (in bytes) of a node.  denotes the current queue length of a node and  denotes the average occupancy rate of the buffer in recent time T.

2.2.2 C₂ attributes

In forwarding desire information the risks and benefits of data receiving are mainly considered. It includes such parameters as traffic load, transfer mode, buffer occupancy, and average risk rate: D=(<>_I>, <>_T>, <>_O>, <>).

1) T_I denotes traffic intensity, which represents the current and future traffic demand. Traffic intensity is equal to buffer filling rate/buffer empty rate.

2) C_T denotes whether use the custody transfer mode.

3) B_O is a parameter related to buffer occupancy and includes storage cost and transmission cost. Storage cost S_v(s)=(s<>_v), where A_v expresses the free space and s represents the length of the message. If s>A_v, then S_v(s) will be infinite. Transmission cost T_i(s)=lg((L_i+ (s/B_i))/10^-6)/10, where L_i denotes the delay and B_i denotes the band width.

4) R_T represents the average risk during a period of T and it is related to the size of the bundle and remainly time to live; V_T represents the average profit during a period of T and it is related to the priority of the node message; and  represents average risk rate and it is the ratio of R_T to V_T.

2.2.3 C₃ attributes

As the DTN network connection appears occasionally, the contact occurs accidentally, and the link connect intermittently, transmission capacity information C₃ mainly includes such parameters as the available band width estimated through link state, available probability of bandwidth, future contact probability between nodes and the forwarding probability: C={<>_B>, <>_cp>, <>_D>}.

1) A_B stands for available bandwidth. A_B=B/|N_i|, where B denotes the total band width and |N_i| denotes the current number of receiving bundles.

2) F_cp stands for future contact probability.

Its initial value is 1/(|s′|-1), and s′ represents a set of network nodes. Then, we can get the possibility of transmission (P_LH) through P_LH=F_cp/(1+B_f) which represents the frequency of node contact that will reflect the probability of a node contact with its destination node.

3) The forwarding probability of node a and node b can be defined as P(a, b)=P(a, b)_old+(1-P(a, b)_old?P_init), where P_inint[0, 1] is an initialization constant. And the sending probability between nodes will decay over time (0<γ<1, where γ represents the decay constant), which can be denoted as P(a, b)=P(a, b)_old?γ^k.

3 Description of MACAR algorithm

3.1 Priority preference relations

Relations here have three kinds, better than (>), worse than (<) and can not compare (-), namely R={r₁, r₂, r₃}={>, <, -}. Then, the priority preference relation related to C_i (i=1, 2, 3) attribute of the next hop node a_p and a_q can be expressed as follows.

Definition 1: The priority preference relation with confidence level is

R_i(a_p, a_q)={(>, β_1,i (a_p, a_q)), (<, β_2,i(a_p, a_q)), (-, β_3,i(a_p, a_q))} (1)

where β_n,i(a_p, a_q) represents the confidence level of >, <

and - under attribute C_i. So, β_n,i≥0 and  Its

calculation rules are as follows.

Rule 1 (Superior parameter rule): A larger beneficial-type parameter is superior to those smaller ones while a smaller cost-type parameter is superior to those larger ones. The “Right” is superior to the “Error” in the right-preferred parameters, while it is contrary among negative-preferred parameters.

Rule 2 (Inferior parameter rule): Larger ones of P_B are inferior to those smaller ones while smaller ones of P_C are inferior to larger ones. The “Right” is inferior to the “Error” in P_R parameters while it is contrary in P_W parameters.

Rule 3 (Rule of parameter with the uncertain relation): If all the values of parameters are the same or any of them is unknown, the relations among them will be uncertain.

Set g(?) as the utility function for the parameter j of attribute C_i, meeting the rules above. And set the parameters of the subset of attribute C_i as

J_a>b={jC_i: g_j(a)>g_j(b)}, J_{a={jCi: gj(a)<>j(b)} and Ja-b={jCi: gj(a)-gj(b)} represent the subsets of these three situations, respectively: a is superior to b, a is inferior to b, and the relation between a and b is uncertain. We can divide the parameters set of the attribute Ci into three parts as}

They represent the number of parameters when attributes C_i meet Rule 1, Rule 2 and Rule 3, respectively. As a result, we can make use of a fuzzy rule in a format like “IF-THEN” to obtain β_n,i(a_p, a_q): If the number of support parameters is q_n,i in the total number of evaluation of |C_i|, then β_n,i=q_n,i/|C_i|:

                (2)

3.2 Uncertain attribute integration

When measuring, mixing and signifying the uncertain information, the evidence theory has a greater advantage than the Bayesian inference, the fuzzy reasoning, the probabilistic reasoning and the rule-based reasoning. The evidence theory has gone through the probability assignment, the property iterative synthesis, the combination of computing confidence and other processes. The most important is the combination rules proposed by evidence theory.

Step 1: Constructing probability assignment. Suppose that ω_i represents the weights of the attributes C_i (i=1, 2, …, k), and this ω_i satisfies the condition: 0

ω_i≤1,Use ω_i to express the relative importance

of these attributes and ψ_n,i=ω_iβ_n,i(a_p, a_q), n=1, 2, to express the better relations and the inferior relations separately. The ψ_{n, i} is a basic probability density, which describes the extent of property C_i supporting r_n, and the r_n is the relation between a_p and a_q.

The ψ_R,i is surplus probability density, which describes that the extent of property C_i can not support r_n. The ψ_{R, i} can be divided into two parts as

Step 2: Composite these properties iteratively. To get a combination confidence of all sub-attributes, the following algorithm composes the evidence.

Initialize:

Interate:

where  represents a

normalization factor.

Step 3: Calculate the confidence level combination.

3.3 Advantages partial order

The partial order can be expressed as a directed acyclic graph, which has transitive nature. Because of these properties, the partial order can be used to represent the sequence. d(r₁, r₂) is used to express the degree of deviation between r₁ and r₂. The distance between the partial order given the calculated values of d(r₁, r₂) is shown in Table 2.

Table 2 Distance degree between partial orders

Definition 2: The priority preference relations and “<”, “>” distance weighted, respectively, are defined as  d ^>(a_p, a_q) and d ^<(a_p, a_q):

Definition 3: φ^>(a_p) and φ^<(a_p) are the index numbers of the disadvantages and advantages of the node a_p:

Obviously, φ^>(a_p) and φ^<(a_p) have the following properties: With the disadvantage index increasing, the distance between the > and the relations among this program and other programs is further. This means that this program is worse. From the disadvantage index (or preference index), we can know that the degree of this program is worse (or better) than the other programs.

The disadvantage index and the advantage index are utility function, can be used to measure the sorting as a support measure.

3.4 MACAR algorithm design

The routing algorithm proposed in this study uses an uncertain information inference method. It effectively merges all the congestion control-related attributes together in the selection of routing. The multi-attributes congestion aware routing algorithm is as follows.

Input: node n, attribute set C=IDC, neighbor node set A_n

1) Classify the selection parameter c_j of the selected next hop node as IDC measurement parameters and determine its parameter type;

2) Select a neighbor node set A_n of node n, and use Eqs.(2)-(3) to construct a preference matrix [R_i(a_p, a_q)]_r*3, where r is the number of neighbor nodes. Then, calculate the different priority preference relations of the solutions with a confidence level under any attribute;

3) Set the weight ω_i of each IDC attribute, and use Eq.(4) and the preference matrix to obtain R(a_p, a_q) with a confidence structure, formatting the preference vector: R(a_p, a_q)={(>, β₁(a_p, a_q)),(<, β₂(a_p, a_q)),(-, β₃(a_p, a_q))}

4) Construct the partial order with the low-quality index and superior index:

(1) Construct the total order V ^> and V ^< of A_n

V ^>=[]

Loop

w={a_p|minφ^>(a_s), a_s∈A_n}

V^>.addElement(w)

A_n=A_n-{w}

until A_n is empty

And we can get the total order V^< of A_n in the same principle.

(2) Determine the partial order R={>, <, ?} of the next hop node, using the rules as follows:

if (a_p<>_q for all members in V ^<, V ^> or one meets a_p>a_q and another meets a_p-a_q)

a_p>a_q;

if (a_p>a_q for all members in V ^<, V ^> or one meets a_p>a_q and another meets a_p-a_q)

a_p<>_q;

else

a_p-a_q;

5) Decision-making output DMⁿ={k|k>a, any a∈A_n}, and the algorithm is over.

Compared with the single-attribute decision-making, MACAR increases the cost of computation and the number of the exchanged network information. In n alternative options, the number of multiplication and division in combining k evidence with a method of combination is the complexity of the combination method, which can be expressed by O(f(n, k)). By using the defined formula in Ref.[16] to compute the complexity, the complexity of MACAR algorithm is O(f(n, k))= O(2^nk+1+k). The attribute sub-set model IDC constructed in this work, organizes a great number of metrics parameters into three top-level attributes in the way of pretreatment method. So, the expression becomes simple, and the number of dimensions is constant 3. It uses the preference matrix that is limited by the constant as the input to the integration algorithms. Thus, it effectively decreases the computational complexity and the space complexity of the integrated decision-making algorithm. In addition, if the model increases new measure parameters, it will not increase the number of top-level attributes and the computational complexity will not increase with the increase of parameters.

4 Experimental simulation

4.1 Experimental environment

In order to analyze and evaluate the projects proposed earlier, we use the ONE simulator [17] to simulate. This open source simulator is an opportunity to network simulation environment, and it integrates mobile modeling, routing simulation, visualization and result reporting into an integrity. We rewrote the CARRouter class to support strict custody transfer algorithm. Moreover, we designed and constructed the MACARRoutes class. The network topology is shown in Fig.2. Without loss of generality, the scenarios are divided into regions 1-4, and region 3 as the backbone network includes B1-B3 transit nodes, the rest regions includes E1-E9 terminal nodes and cluster head nodes. And E1, E2, E4, E5, E6 and E9 are the source nodes, E3, E7 and E9 are the destination nodes. The link bandwidth of region 1-3 is 2 Mbit/s, region 4 is 1 Mbit/s, and the ability of link between Region 1 and Region 3, Region 2 and Region 3, Region 4 and Region 3, is 1.0, 2.0 and  0.5 Mbit/s, respectively. Table 3 gives the various values of parameters needed in the experiment.

Fig.2 Simulation topology

Table 3 Experimental parameters

4.2 Experimental results

The performances of CAR and MACAR in two mobile modes of random way point (RWP) and map- based (MB) movement are simulated. The parameters of performance include four aspects: successful delivery rate, bundle dropped rate, average bundle buffer occupied ratio and average delay. The result is the statistics based on 25 independent experiments, as shown in Figs.3-6.

From Fig.3, it can be seen that with the message size increasing from 100 to 500 kbit, the changes of the successful delivery rate of the bundle are observed. As seen from Fig.2, with the MACAR algorithm we proposed, the rate of successful data transmission is better than CAR. Especially, in the case of poor network condition, the performance is improved by nearly 2.3

Fig.3 Successful delivery rate performance

Fig.4 Bundle dropped rate performance

Fig.5 Average bundle buffer occupied ratio performance

times. Figs.4 and 5 show the package loss rate of the algorithm and the performance of average queue length, respectively. When the load is small, the average queue length is small and the packet loss rate is small too. However, with the increase of the load, each CAR node queue is extremely unbalanced since there is no ability to control the congestion. And it easily leads to certain key nodes to be the bottleneck; at the same time, the buffer occupancy rate increases rapidly. All these factors lead to high speed increase of packet loss rate. Fig.6 shows the

Fig.6 Average delay performance

average delay performance of message, from which we can get knowledge that the average delay of CAR is better than that of MACAR in a better network condition. However, with deteriorating the network condition, the advantage of MACAR is more obvious. What’s more, the node movement is random in the random movement pattern and does not have the regularity, so the availability of historical information is somewhat weaker. While in the MB mode, node movement follows a pattern of knowledge, so the context information guidance and the predict effect are strong.

5 Conclusions

1) A kind of congestion aware routing algorithm, MACAR, is introduced based on the multiple attribute decision making of uncertain information, in which a variety of context information from the congestion control and routing schema is considered.

2) Experimental results demonstrate that the MACAR can not only improve the successful rate of data forwarding, but also decrease the network resource consumption.

References

[1] FALL K. A delay-tolerant network architecture for challenged internets [C]// Proceedings of ACM SIGCOMM. Karlsruhe, 2003: 27-34.

[2] FALL K. HONG W, MADDEN S. Custody transfer for reliable delivery in delay tolerant networks. [EB/OL]. [2010-03-28]. http://www.dtnrg.org/papers/custody-xfer-tr.pdf.

[3] JAIN S, FALL K, PATRA R. Routing in a delay tolerant network [C]// ACM SIGCOM. Portland, 2004: 145-158.

[4] VAHDAT A, BECKER D. Epidemic routing for partially connected ad hoc networks [R]. Duke Technical Report CS-2000-06, 2000: 229-236.

[5] THRASYVOULOS S, KONSTANTINOS P, CAULIGI R. Spray and wait: An efficient routing scheme for intermittently connected mobile networks [C]// Proceedings of ACM SIGCOMM. Philadelphia, 2005: 22-26.

[6] ANDERS L, AVRI D, OLOV S. Probabilistic routing in intermittently connected networks [J]. SIGMOBILE Mobile Computing and Communication Review, 2003, 7(3): 19-20.

[7] MUSOLESI M, HAILES S, MASCOLO C. Adaptive routing for intermittently connected mobile ad hoc networks [C]// Proceedings of the 6th IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM2005). Taormina- Giardini Naxos, 2005: 183-189.

[8] BOLDRINI C, CONTI M, JACOPINI J. HiBOp: A history based routing protocol for opportunistic networks [C]// IEEE International Symposium on a World of Wireless, Mobile and Multimedia Networks. Helsinki, 2007: 1-12.

[9] DE RANGO F, TROPEA M, LARATTA G B, MARANO S. Hop-by-hop local flow control over interplanetary networks based on DTN architecture [C]// IEEE ICC 2008. Beijing, 2008: 1920-1924.

[10] SCHEUERMANN B, LOCHERT C, MAUVE M. Implicit hop-by-hop congestion control in wireless multihop networks [J]. Elsevier Ad Hoc Network, 2008, 6(2): 260-286.

[11] BISIO I, DECOLA, T, MARCHESE M. Congestion aware routing strategies for DTN-based interplanetary networks [C]// IEEE GLOBECOM. New Orleans, 2008: 1-5.

[12] ZHANG Guo-hua, WANG Jing, LIU Yong-he. Congestion management in delay tolerant networks [EB/OL]. [2010-03-28] http: //portal.acm.org/citation.cfm?id=1554126.1554206

[13] BURLEIGH S, JENNINGS E, SCHOOLCRAFT J. Autonomous congestion control for an interplanetary internet [C]// AIAA SpaceOps 2006 Conference. Rome, 2006: 123-127.

[14] SELIGMAN M, FALL K, MUNDUR P. Alternative custodians for congestion control in delay tolerant networks [C]// Proceedings of SIGCOMM. Pisa, 2006: 229-236.

[15] YANG J B. XU D L. On the evidential reasoning algorithm for multiple attribute decision analysis under uncertainty [J]. IEEE Transaction Systems, Man and Cybernetics, 2002, 32(3): 289-304.

[16] HOU Jun. The evidence reasoning’s combination method, evaluation and application [D]. Xi’an: Northwestern Polytechnical University, 2006: 44-47. (in Chinese)

[17] ARI Ker?nen, J?RG Ott, TEEMU K?rkk?inen. The ONE simulator for DTN protocol evaluation [C]// SIMUTools’09: 2nd International Conference on Simulation Tools and Techniques. Rome: 2009: 243-248.

(Edited by LIU Hua-sen)

Foundation item: Project(60973127) supported by the National Natural Science Foundation of China; Project(09JJ3123) supported by the Natural Science Foundation of Hunan Province, China

Received date: 2010-09-10; Accepted date: 2010-11-29

Corresponding author: TAO Yong, PhD; Tel: +86-731-88825889; E-mail: 4889970@qq.com