TMCnet News

Self-Adaptive Context Aware Routing Protocol for Unicast Communication in Delay and Tolerant Network [Sensors & Transducers (Canada)]
[June 26, 2014]

Self-Adaptive Context Aware Routing Protocol for Unicast Communication in Delay and Tolerant Network [Sensors & Transducers (Canada)]


(Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: At present, most of research works in mobile network focus on the network overhead of the known path which exists between the sender and the receiver. However, the trend of the current practical application demands is becoming increasingly distributed and decentralized. The Delay and Tolerant Network (DTN) just comes out of such background of the conflicts between them. The DTN could effectively eliminate the gap between the mobile network and the practical application demands. In this paper, a Self-Adaptive Context Aware Routing Protocol (SACARP) for the unicast communication in delay and tolerant networks is presented. Meanwhile, according to the real-time context information of DTN, the Kalman filter theory is introduced to predict the information state of mobility for the optional message ferrying node, and then gives the optimal selection strategy of the message ferrying nodes. The simulation experiments have shown that, compared to the familiar single-copy and multi-copy protocols, the SACARP proposed in this paper has better transmission performance and stability, especially when the network is free, the protocol would keep a good performance with fewer connections and less buffer space.



Copyright © 2014 IFSA Publishing, S. L.

Keywords: Self-adaptive routing, Unicast communication, Kalman filter theory, Delay network, Tolerant network.


(ProQuest: ... denotes formulae omitted.) 1. Introduction Due to the topological dynamic changes of DTN, there is no stable transmission path between nodes, even no a complete transmission path at any time, which makes the traditional ad hoc network routing mechanisms relying on the stability of the transmission path difficult to play its role. Therefore, in delay tolerant networks, the transmission of the packet is often done by means of a store-carry-forward mechanism [1]. Based on the number of the coexisting copies of the message in the network, DTN routing mode can be divided into two types: single-copy routing mode and multi-copy routing mode [2]. In the single-copy mode, no node can carry more than one copy. The advantage of this model is simple and efficient, but lack of ability in processing interruption and node error in the network connection [3]. On the other hand, multi-copy routing mode allows the multiple copies of the same message in the network, which could improves the stability of the whole network by the parallel routing strategy [4], Currently, most of the multi-copy protocols are based on the flooding routing protocol [5], and they distribute unlimited copies throughout the network, while some of them are based on the controlled flooding routing protocol [6], and they just distribute a subset of the copies, or use the method based on utility to determine whether the information should be copied to the connected node or not, which is just simply based on the developed utility function. Although these multi-copy modes improve the performance of the network, they encounter the following problems [7]. Firstly, the multi-copy mode inevitably requires a lot of transmission, thus brings the consumption of the transmission bandwidth, node memory and the node energy [8]. Secondly, in the case of high traffic load, the phenomenon of packet loss will be more evident, and thus causes a significant decrease in transmission efficiency of the network [9].

As the DTN has been widely operated in an environment with a large number of miniature handheld devices such as smart phones, tablet computers, and mobile sensors, the energy consumption of nodes, buffer space, and message transmission strategy have become the dominant factors to restrict the performance of the DTN [10]. According to this problem, a family of multi-copy modes called utility-based controlled flooding has been proposed [11]. The class of modes generates only a small number of copies to ensure that the network is not overloaded with the launched messages.

The modes are proposed under the assumption that each node has sufficient resources. However, in the practical transmission, the states of node resources are constantly changing, which makes the prediction and assessment on the states of node resources become an important factor on affecting the performance of DTN [12].

It should be noted that, there is no related research on improving the transmission performance of mobile network by analyzing the states of node resources.

This paper exactly proceeds from this angle, and proposes the self-adaptive aware routing protocol based on the context of the nodes in the network, and uses the Kalman filter prediction theory [13] to predict the future state of the nodes in the network. The results of the prediction will be used to make routing decisions, which aims at overcoming the disadvantage of the multi-copy mode based on utility and achieves high efficiency of the transmission.

This paper is organized as follows: the design of the SAC ARP is presented in Section 2, and its performance assessment is discussed in Section 3. The comparative experiment is provided in Section 4 to verify the rationality and feasibility of SACARP. Finally, Section 5 concludes the paper.

2. Design of Self-Adaptive Context Aware Routing Protocol In this section, the overview of Self-Adaptive Context Aware Routing Protocol is presented. Firstly, the runtime steps of the protocol are described. Secondly, the prediction theory and its foundation algorithm are analyzed. Thirdly, the implementation of the protocol, especially the management of routing information for synchronous and asynchronous delivery is discussed.

As the first step, we introduce two important assumptions underlying the design of the protocol. One assumption is that the only information a host has is its position information related to its logical connectivity. That's to say, we assume that a host is neither aware of its absolute geographical location nor aware of the location of those to whom it might deliver the message. Though this potential information could be useful, it's difficult to turn on GPS or other positioning devices all the time due to the limited energy of mobile devices. Another important assumption is that the hosts presented in the system cooperate to deliver the message. In other words, all the hosts are bona fide co-hosts, and will not refuse to be message ferrying nodes.

Based on the assumptions above, the key issue in the design of the self-adaptive aware routing protocol is the choice of the message ferrying node. Therefore, taking Kalman filter theory into consideration, on the basis of the perceived system routing information, this paper combines the characteristics of intermittent connection, frequent change and heterogeneous interconnection in Delay and Tolerant Network, and assesses the message routing state of the optional message ferrying nodes, and then gives a real-time selection strategy of message ferrying nodes.

This paper proposes that there are two transmission modes which are supported by the selfadaptive aware routing protocol in the Delay and Tolerant Network, synchronous mode and asynchronous mode. The choice of the transmission mode depends on whether or not the recipient is present in the same connected region of the network as the sender. If both of them are currently in the same region of the network, the message is delivered by using an underlying synchronous routing protocol to determine a forwarding path. If a message cannot be delivered synchronously, it's necessary to select an optimal message ferrying node as the intermediate node, and the message will be transferred to the selected intermediate mode by using an underlying synchronous routing protocol. In this way, the message transmission mode from the sender to the recipient is transformed into an asynchronous mode. Now let's discuss in detail the implementation process of the self-adaptive aware routing protocol in the application scenarios shown in Fig. 1.

In Fig. 1, Nu, N12, No and N14 are connected in Cloud 1, and N21 and N22 are connected in Cloud 2. We assume that the Dynamic Destination-Sequenced Distance Vector (DSDV) is used to support dynamic routing [14]. Node Nu wants to send a message to N22. Because there is no connected path between them, this cannot be done synchronously. The delivery probabilities for message transmission for N22 are showed in Fig. 1. In this case, the node possessing the best delivery probability to N22 is N13. Consequently, the message is sent to N13 which stores it. After a certain period of time, N13 moves to the cloud 2. Using DSDV, N13 will receive the routing information relating to N21 and N22, thenNn is able to send the message to N22 since a connected path between No and N22 now exists. The process of message transmission from the start Node Nn to the destination Node N22 is asynchronous transmission mode.

In the asynchronous transmission mode, we use the delivery probabilities of each node for message transmission to make routing decisions, and the delivery probabilities are predicted by analyzing the context routing information of the communication node. Therefore, the prediction and assessment of the context routing information is the key to achieve asynchronous message transmission. In the following sections, we will discuss the analysis, prediction and assessment of the context routing information in detail.

3. Prediction and Assessment of Context Routing Information The context routing information of the nodes in the network can be defined as a set of attribute values used to drive and affect the process of message delivery. Now we will take the change rate of connectivity as an example to describe the process of message delivery. Since the change rate of connectivity is closely related to the number of connections and disconnections that a node experienced over the past T seconds, this parameter can measure this node's relative mobility, and consequently it predicts the probability that a node will encounter other hosts. If we adopt a proactive routing protocol, every node periodically sends the information related to the underlying synchronous routing to other nodes. When a node receives this information, it updates its routing table. With respect to the mode of asynchronous routing, each node maintains a list of entries, each of which is a tuple that includes the context information. Then the node has to make a routing decision about which node the message should be transferred to. When a node is selected as a carrier and receives the message, it inserts the message into a buffer. If the buffer overflows, messages will be lost, and the probability of message loss is increasing. It is not difficult to see that during the process of message delivery, the change of context routing information and decision making on routing have become dominant factors that affect the efficiency of message delivery.

In this paper, we start from the two dominant factors mentioned above, based on the predicted future values of the context attributes, and develop a set of self-adaptive message routing decision algorithm. It should be noted here that instead of using the current context information, we analyze the recent changing time series of the context information associated to each context dimension and calculate the trend of information change. For example, Dl and D2 are not interconnected with each other, if we evaluate only this instant of time, D2 may be considered as an inefficient carrier. However, D1 may have connected to D2 many times for the recent time, its possibility of being interconnected again with each other is high. Therefore, in this paper, the method of context routing prediction will give full consideration to this aspect.

3.1. Method of Prediction and Assessment on Context Routing Information First, we present a general and extensible method of prediction and assessment on context routing information: 1) Given a set of network nodes, each node calculates its delivery probabilities. This delivery probability is based on the calculation of utilities for routing context attributes. Then the future values of these utilities are predicted and composed by using multi-criteria decision theory in order to estimate the total delivery probability.

2) The calculated total delivery probabilities of each network node are included in the real-time routing information, and are sent periodically to the other nodes which exist in the same connected cloud.

3) Based on the received delivery probabilities, the node makes a forwarding table meeting the needs of current message transmission, whose describes the next logical network node and its associated delivery probability for all known destinations.

4) After receiving the information of forwarding table, associated with its own delivery probabilities, the node will predict and assess the delivery probabilities to the subsequent nodes again. The process is carried out until a certain accuracy of the delivery probabilities for all the nodes in the table can be guaranteed.

It's not difficult to see that the calculation of delivery probabilities throughout the process is the key and difficulty point in prediction and assessment of the context routing information. Here we will focus on this point and discuss it in detail. Each node calculates its delivery probability based on the various context attributes, and it is not difficult to monitor the attribute of context information for each node, therefore, the key problem is to combine the multi-dimension attributes. It should be noted that during the process of combination of the attributes, we will meet multiple conflicting objectives. For example, consider a battery power level and the rate of change of connection. The node with higher mobility usually has lower battery power level, while the node with higher battery power level has poor mobility. Therefore, it's not possible to maximize across all objectives, and instead, we must weigh each achievement of one objective against others to get the whole optimization.

The formal description of the context information of nodes and the calculation process of the delivery probabilities is as follows: Definition 1. The context information related to a certain node can be defined as one or multi-dimension set of attributes, Cxt = {XvXv...,Xn}(n> 1).

Among them, the attribute denoted with a capital letter, such as ..., refers to the description of the context routing information from one dimension, which is composed of one or more sets of values used to descript the value of the specific dimensional information, For example... should be noted that the properties (e.g. X.... are independent of each other because they are used to describe different dimensions of information. For example, X/can be the mobility of the nodes (e.g. X} = (x',^2,...}), among them, x\ means the remaining battery level, and x\ means the CPU utilization ratio, both of whose values are used to measure the mobility of nodes.

In order to describe the context information of the nodes in the network quantitatively, we introduce a utility function to combine the properties together and to predict the value of the properties.

Definition 2. The context information of the nodes can be defined as follows: ...

where E is the utility function among dimensions, and Ei is the utility function of the attributes among dimension i.

The aim of the quantitative assessment for context information is to maximize each attribute according to the requirements, in other words, we expect to choose the node that can best trade-off between the attributes representing the relevant aspects of the system for the message delivery. Instead of simple arithmetic sum, the value of the comprehensive assessment should be a weighted sum representing the importance of each dimension. To solve this problem, we apply the weight mechanism.

Definition 3. The context information of the weighted nodes can be defined as follows: ...

where ... is the weight which could be predefined by users to present the relative importance of the context attributes in each dimensions. Through values of the attributes of the context information, we can use the combination utility function to calculate the optimum value of the context information. However, the future prediction values of the context information are more important to the message routing decision. Therefore, it's necessary to introduce the techniques based on Kalman Filter to calculate the prediction values of context information of the nodes. The significant characteristic of Kalman Filter techniques is that it doesn't require the storage of the entire past history of the system. And the algorithm itself is lightweight, which makes it more suitable for a mobile setting in which resources may be very limited in DTN.

We take the change degree of connectivity and the future node collocations as examples, and give the method of prediction and assessment of context information based on the Kalman Filter Techniques.

1) Formal description of interconnection between network nodes The interconnection between d\ and di at time t can be described as follows: ... if d1 and d2 are connected with each other, the value is 1, and otherwise is 0.

2) Calculating the changing connectivity degree of network node Definition 4. The changing connectivity degree of network node d at time t can be described by the formula ... which yields the number of nodes that become neighbors or disappeared in the time interval [i-T, t\, where T is a standardized specific length of time, and n(t)is d7s neighbor set at time t. It's obvious that a high value of ConCDd{t) means that the numbers of its neighbors have changed a lot recently.

3) Calculating utility functions of network nodes based on Kalman Filter Theory Kalman Filter Theory is used to generate the prediction value of ConCE>(t) and CondxJ2(t) * And then we compose these values into a single utility value using multi-criteria decision theory.

Definition 5. The utility function of message transmission from d\ to di can be expressed as ...

where wwa and wCOn are the weights reflecting the relative importance of each attribute. The values depend on application scenarios. And the values of these weights are the same for every nodes, in other words, the combination of utility is the same for all the nodes in the network.

3.2. Self-adaptation of Utility Function The weighting mechanism proposed in last section is a static mechanism fixed by users in advance, which is practical when the changes of context information presents linearly. However, such a mechanism fails to apply when the changes of the context information is more complex. Thus, for example, when the battery voltage is low, a small drop in battery voltage may be indicative of the imminent exhaustion of the battery, and this case reflect the nonlinear characteristic of voltage. Consequently, the automatic adaptation of weighting mechanism becomes especially important.

In general, we wish to adapt the weights of each parameter dynamically and in ways that are dependent on the values of those parameters. In other words, we need a runtime self-adaptation of the weightings used for this assessment process. A solution to this problem is the introduction of adaptive weights ai into the definition 3 to construct a predicting mechanism of the context information on adaptive weights.

Definition 6. The combined utility function of context information on adaptive weights can be defined as: ...

where a.(x.) is the parameter that may itself be composite, which is composed of three values: Criticality of certain ranges of values ara(x.) ; Predictability of the context information a (x ) ; Availability of the context information aav(x.) * a.(x.) can be described as factors in the following formula: ...

Each of these above aspects is described in detail: 1) Self-adaptive weights related to the ranges of context routing attributes We can model the adaptive weights a (x.) in the domain [0, 1], For example, with respect to the battery energy used by nodes in the network (modeled using the percentage of residual battery energy), we would use a monotonically decreasing function to assign a decreasing adaptive weight, which is, in turn, used to ensure that the corresponding utility function decreases as the residual energy tends toward 0.

2) Self-adaptive weights related to the predictability of context routing information It may happen that the forecasting model is not able to provide accurate predictions for a certain time series related to a given attribute. We define it as ..., if the context information is currently predictable, we define it as 1, and otherwise is 0. We prefer to adopt an approach based on two discrete values (0 and 1) rather than one based on continuous values (i.e., an interval between 0 and 1), since the latter would be only based on a pure heuristic choice and not on any sound mathematical basis.

3) Self-adaptive weights related to the availability of context routing information It is obvious that all context attributes have the different degrees of availability. Thus, we expect to have a time-varying set of attributes available whose values are known: ... information is currently available, we define it as 1, and otherwise is 0. Formally, we just have assumed a static set of attributes. However, if some attribute values couldn't be obtained, we can simply assume that they were always there but had zero weight for aav. For example, if an operating system is not able to provide information about the current battery level of a device, the value of availability is set to 0.

4. Experiment and Analysis First of all, we introduce four typical DTN routing protocols. Epidemic Routing represents an example of an asynchronous protocol, and in particular, it provides the theoretical upper bound in terms of delivery ratio with infinite buffers [15]. Random Choice implement that the selection of carriers is done randomly instead of choosing the host with the highest delivery probability in the connected portion of the network [16]. PRoPHET is a semi-epidemic approach based on the calculation of the probability of replicating a copy of a message based on the frequency of encounters between pairs of hosts [17]. Spray and Wait is based on the initial replication of a certain number of copies of the message (5 and 10 in our experiments) [18]. Then, these copies are not replicated further and are only forwarded to the recipient of the message.

We implemented our simulation scenario using OMNet++ [19], and we conducted the performance contrast experiments between ACRP introduced in this paper and the four selected typical routing protocols related to the two aspects of transmission delay and buffer size respectively.

1) Distribution of Delivery Delay.

The distribution of delivery delay is a characterizing aspect of a protocol for delay-tolerant networks [20]. It should be noted that, in these simulations, the buffer size of hosts is infinite. Fig. 2 and Fig. 3 show the delay distribution measured in the 50 and 100-host scenarios, respectively.

We note that the number of messages delivered by the Epidemic Routing, PRoPHET, and Spray and Wait in asynchronous way is lower than that by ACRP. In fact, the message is replicated to the neighboring nodes at each replication step in the first three routing protocols, while the synchronous delivery mechanism in ACRP allows for a more efficient routing performance, since a message is delivered immediately to the destination if a known connected route to it exists without replicating messages to neighboring nodes.

2) Influence of Buffer Size.

Another critical aspect is the influence of the buffer size of the hosts on the delivery ratio of messages for delay-tolerant networks [21]. Fig. 4, Fig. 5 and Fig. 7 show the impact of buffer size on the delivery ratio in rather dense scenarios composed of 50 nodes in a 1 km*l km area, 50 nodes in a 2 kmx2 km area and 100 nodes in a 2 kmx2 km area.

Let us consider the scenarios composed of 50 hosts in Fig. 4 and Fig. 5, where ACRP outperforms Random Choice. When the buffer size is not more than 110, ACRP shows a higher delivery ratio than that of the Epidemic Routing protocol. In fact, with small buffers, the Epidemic Routing protocol shows its evident limitations due to the replication mechanism. ACRP also outperforms Spray and Wait with a buffer size lower than 50. This is due to the fact that the latter is a multiplecopy routing scheme. At the same time, the cost of Spray and Wait is really high in terms of messages sent.

Let us observe the results related to the 100-host scenario reported in Fig. 6. The gap between the curves describing the performance of CAR and the Random Choice model is larger than in the previous scenarios. This is due to the fact that in a denser scenario like the one composed of 50 hosts, the probability of getting in reach of the recipient by chance is higher. With respect to the performance of ProPHET and Spray and Wait, we observe a similar trend, ACRP outperforms these two protocols in case of small buffers. The predictability level of this scenario is about 85 percent, a value close to the one measured for the 50-host scenario.

In conclusion, the simulation experiments have shown that, due to the effectiveness of the prediction algorithm based on utility, ACRP is able to keep good performance with a smaller buffer size in comparison to the other four typical routing protocols.

5. Conclusions Self-Adaptive Context Aware Routing Protocol for unicast communication in Delay and Tolerant Network is proposed in this paper, and then a generic method for the prediction and assessment of context routing information is designed. Finally, the results of comparison measurement and test with some typical routing protocols prove that the self-adaptive aware routing protocol proposed in the paper can ensure good transmission performance with limited cost of sending messages, especially suitable for the application scenarios of sparse connections and small buffer.

Acknowledgements Our research was supported by the 2012 Ladder Plan Project of Beijing Key Laboratory of Knowledge Engineering for Materials Science (No. Z121101002812005), National High Technology Research and Development Program of China (863 Program, No. 2009AA01Z119), and National Natural Science Foundation of China (No. 60973065).

References [1] . S. Yamamura, A. Nagata, M. Tsuru, et al, Virtual segment: Store-carry-forward relay-based support for wide-area non-real-time data exchange, Simulation Modelling Practice and Theory, Vol. 19, Issue 1,2011, pp. 30-46.

[2] . Ozan K. Tonguz, Nawapom Wisitpongphan, and Fan Bai, DV-CAST: A distributed vehicular broadcast protocol for vehicular ad hoc networks, Wireless Communications, Vol. 17, Issue 2,2010, pp. 47-57.

[3] . Mathias Boc, et al, Price: Hybrid geographic and cobased forwarding in delay-tolerant networks, Computer Networks, Vol. 55, Issue 9, 2011, pp. 2352-2360.

[4] . Delia Ciullo, et al, Impact of correlated mobility on delay-throughput performance in mobile ad hoc networks, IEEE/ACM Transactions on Networking, Vol. 19, Issue 6,2011, pp. 1745-1758.

[5] . Muhammad Saleem, Gianni A. Di Caro, and Muddassar Farooq, Swarm intelligence based routing protocol for wireless sensor networks: Survey and lliture directions, Information Sciences, Vol. 181, Issue 20,2011, pp. 4597-4624.

[6] . D. Shin, D. Hwang, D. Kim, DFR: an efficient directional flooding-based routing protocol in underwater sensor networks, Wireless Communications and Mobile Computing, Vol. 17, Issue 12,2012, pp. 1517-1527.

[7] . E. Bulut, B. K. Szymanski, Secure multi-copy routing in compromised delay tolerant networks, Wireless Personal Communications, Vol. 73, Issue 1, 2013, pp. 149-168.

[8] . M. Y. S. Uddin, H. Ahmadi, T. Abdelzaher, et al., Intercontact routing for energy constrained disaster response networks, Mobile Computing, Vol. 12, Issue 10,2013, pp. 1986-1998.

[9] . H. Z. Yu, J. F. Ma, H. Bian, Message redundancy removal of multi-copy routing in delay tolerant MANET, Journal of China Universities of Posts and Telecommunications, Vol. 18, Issue 1, 2011, pp. 42-48.

[10] . A. Balasubramanian, B. Levine, A. Venkataramani, DTN routing as a resource allocation problem, ACM SIGCOMM Computer Communication Review, Vol. 37, Issue 4,2007, pp. 373-384.

[11] . T. Spyropoulos, K. Psounis, C. S. Raghavendra, Efficient routing in intermittently connected mobile networks: the multiple-copy case, IEEE/ACM Transactions on Networking, Vol. 16, Issue 1, 2008, pp. 77-90.

[12] . R. J. D'souza, J. Jose, Routing approaches in delay tolerant networks: A survey, International Journal of Computer Applications, Vol. 17, Issue 1, 2010, pp. 8-14.

[13] . D. H. Dini, D. P. Mandic, S. J. Julier, A widely linear complex unscented Kalman filter, Signal Processing Letters, Vol. 18, Issue 11,2011, pp. 623-626.

[14] . S. A. Ade, P. A. Tijare, Performance comparison of AODV, DSDV, OLSR and DSR routing protocols in mobile ad hoc networks, International Journal of Information Technology and Knowledge Management, Vol. 2, Issue 2, 2010, pp. 545-548.

[15] . Y. Li, P. Hui, D. Jin, et al., Evaluating the impact of social selfishness on the epidemic routing in delay tolerant networks, IEEE Communications Letters, Vol. 14, Issue 11,2010, pp. 1026-1028.

[16] . R. Palucci Pantoni, D. Brandäo, A gradient based routing scheme for street lighting wireless sensor networks, Journal of Network and Computer Applications, Vol. 36, Issue 1,2013, pp. 77-90.

[17] . S. Grasic, E. Davies, A. Lindgren, et al, The evolution of a DTN routing protocol-PRoPHETv2, in Proceedings of the 6th ACM Workshop on Challenged Networks, 2011, pp. 27-30.

[18] . V. G. Patel, T. K. Oza, D M. Gohil, Vibrant energy aware spray and wait routing in delay tolerant network, Journal of Telematics and Informatics, Vol. 1, Issue 1,2013, pp. 43-47.

[19] . A. Varga, OMNeT-HModeling and tools for network simulation, Springer, Berlin Heidelberg, 2010, pp. 35-59.

[20] . G. Resta, P. Santi, A framework for routing performance analysis in delay tolerant networks with application to noncooperative networks, Parallel and Distributed Systems, Vol. 23, Issue 1, 2012, pp. 2-10.

[21] . V. Mahendran, C. S. R. Murthy, Buffer dimensioning of DTN replication-based routing nodes, IEEE Communications Letters, Vol. 17, Issue 1, 2013, pp. 123-126.

1,2 Yunbo Chen 1 School of Computer and Communication Engineering, University of Science and Technology Beijing, 100083, China 2 Beijing Key Laboratory of Knowledge Engineering for Materials Science, 100083, China Tel: +86-010-62334708, fax: +86-010-62334708 E-mail: [email protected] Received: 11 March 2014 /Accepted: 30 April 2014 /Published: 31 May 2014 (c) 2014 IFSA Publishing, S.L.

[ Back To TMCnet.com's Homepage ]