Routing in Socially Selfish Delay Tolerant Network

Routing in Socially Selfish Delay Tolerant Network

Harshitha B K

M.tech, Computer networks

Shree Devi Institute of Technology, Mangalore

Abstract–Mobile wireless devices play important roles in our daily life, e.g., users often use such devices to take pictures and share with friends via opportunistic peer-to-peer links, which however are intermittent in nature, and hence require the store and- forward feature proposed in Delay Tolerant Networks to provide useful data sharing opportunities. Moreover, mobile devices may not be willing to forward data items to other devices due to the limited resources. Hence, effective data dissemination schemes need to be designed to encourage nodes to collaboratively share data. We propose a Multi-Receiver Incentive-Based Dissemination scheme that allows nodes to cooperatively deliver information of interest to one another via chosen paths utilizing few transmissions. This scheme exploits local historical paths and users interests information maintained by each node. In addition, the charge and rewarding functions incorporated within the scheme stimulate cooperation among nodes such that the nodes have no incentive to launch edge insertion attacks. Furthermore, charge and rewarding functions are designed such that the chosen delivery paths mimic efficient multicast tree that results in fewer delivery hops.

KeywordsPublisher / subscriber, data sharing, delay tolerant networks, mobile network, Incentive mechanisms.

1. INTRODUCTION

   With the rapid advancement of wireless technologies, mobile wireless devices, e.g., smart phones, PDAs, and laptops have emerged and are gradually woven into our social life. Such devices allow people to access information anywhere at any time since these devices have increasingly larger storage and support multiple network interfaces including cellular, WLAN, and Bluetooth. Users can utilize these devices to access and store interesting data items. While cellular data services are available almost everywhere, constantly using such services to access information is costly because the energy consumed with such constant access is high. On the other hand, it is attractive to exploit peer to peer ad hoc networks [1], [2], [3], [4] formed by these wireless devices utilizing lower- power radios (e.g., Bluetooth or Wi-Fi) to share useful information among users. Users can acquire data items from their peers by expressing their interests based on either data categories which are used to describe these data items [5],[6]. Although

   content dissemination schemes have been proposed for ad hoc networks in the past, e.g.,[5], such approaches usually assume that the networks are well connected. However, interfaces such as Wi-Fi and Bluetooth have shorter radio range and hence connectivity between mobile devices using such interfaces is dynamic and intermittent.

   Delay tolerant networking technology has been proposed to allow nodes in such environments to still communicate by storing data packets when connectivity disappear and exchanging stored packets once connectivity reappears.

   In order to enable smooth information sharing in delay tolerant mobile networks, the participants need to be cooperative. However, since such networks are typically human contact based networks, users are selfish and wish to preserve their devices resources such as communication bandwidth and battery power. Thus, in practice, any useful content dissemination scheme needs to incorporate an incentive or reputation mechanism to encourage users to cooperate for effective information sharing.

   Most existing incentive mechanisms have been designed for unicast scenarios. While these schemes can effectively encourage selfish nodes to help relay others packets,

   their achieved transmission efficiency may be low in multicasting scenarios, which are representative in publish/subscribe systems for delay tolerant mobile networks as the same data items may be interested by multiple users.

   Recently proposed incentive-aware data dissemination seemed promising for multi-receiver scenarios. However, the incentive mechanism in this work focused on rewarding the last-hop relay node which communicates with the destinations, which is not fair for all other relay nodes.

   Here the aim is to design a Multi- Receiver Incentive-Based Dissemination (MuRIS) scheme that not only encourages nodes to cooperate via our proposed incentive mechanism, but also wisely selects paths that can reach multiple subscribers efficiently. Specifically, multi- receiver based charge and rewarding functions are proposed that would favor the paths which can reach more subscribers at intermediate hops.

   Further charge and rewarding functions can prevent edge insertion attacks. This type of attacks is the easiest approach for relay nodes to obtain extra incentives without obvious misbehaviors. Such attacks can significantly impact the fairness of the network since subscribers need to pay more total rewards. Charge and rewarding functions provide no rewarding gain for adversarial nodes, which insert fake intermediate nodes during their edge insertion attacks. Moreover, information sharing scheme allows nodes to utilize locally maintained information about past node encounters and partial delivery paths to determine if they should forward received data

   items to other nodes they encounter such that the chosen delivery paths are those that efficiently reach many subscribers.

2. EXISTING SYSTEM

   1. Content dissemination schemes

      Content dissemination schemes proposed for ad hoc networks in the past, such approaches usually assume that the networks are well connected.

      Drawbacks: Interfaces such as Wi-Fi and Bluetooth have shorter radio range and hence connectivity between mobile devices using such interfaces is dynamic and intermittent. Traditional content dissemination schemes do not consider users changing interests from time to time.

   2. Incentive mechanisms

   Incentive mechanisms designed for unicast scenarios. While these schemes can effectively encourage selfish nodes to help relay others packets, their achieved transmission efficiency may be low in multicasting scenarios, which are representative in publish/ subscribe systems for delay tolerant mobile networks as the same data items may be interested by multiple users.

   Recently proposed incentive-aware data dissemination seemed promising for multi-receiver scenarios.

3. PROPOSED SYSTEM

   Multi- Receiver Incentive- Based Dissemination (MuRIS) scheme encourages nodes to cooperate via proposed incentive mechanism. Multi-receiver based charge and rewarding functions favors the paths which can reach more subscribers at intermediate hops. Proposed information sharing scheme allows nodes to utilize locally maintained information about past node encounters and partial delivery paths to determine if they should forward received data items to other nodes they encounter such that the chosen delivery paths are those that efficiently reach many subscribers.

   A high level overview of MuRIS scheme is shown in the figure. Each node that supports MuRIS scheme collects historical path information used in our scheme, namely, feasible path set and closeness vector. The incentive mechanism in this proposed work focused on

   rewarding the last-hop relay node which communicates with the destinations, which is not fair for all other relay nodes. Also wisely selects paths that can reach multiple subscribers efficiently. Charge and rewarding functions can prevent edge insertion attacks.

   Proposed Charge and rewarding functons provide no rewarding gain for adversarial nodes, which insert fake intermediate nodes during their edge insertion attacks.

   1. Incentive Driven Information Sharing

      MuRIS scheme aims to provide efficient information sharing in DTNs when non-cooperative users are present Multi-Receiver Incentive Based Dissemination (MuRIS) scheme is proposed for efficient information sharing, especially for one-to-many dissemination scenarios. MuRIS scheme dynamically constructs efficient multicast delivery tree for multiple receivers interested in the same message. The incentive mechanism incorporated in MuRIS encourages intermediate nodes to cooperate rather than being selfish so as to gain some rewards associated with their forwarding efforts.

   2. Background on designing an incentive mechanism In a fair incentive mechanism, rewards are distributed to all cooperative intermediate nodes along the delivery path of a message, and the reward should be proportional to the consumed resources for the delivery. Moreover, if we assume the identical resource consumption for every intermediate node, the charge and reward regarding a n hop delivery path must satisfy the Equation

      1. to ensure that the charge can cover all the rewards.

         C(n) _ n × R(n), (1)

         where the C(n) and R(n) indicate the charge to a subscriber receiving a message, and the reward per intermediate node on an n hop delivery path, respectively. To note that publishers are considered as intermediate nodes when the total reward is computed in Equation (1).

         However, an incentive mechanism simply following the Equation (1) is vulnerable to the cheating performed by some greedy intermediate nodes e.g., edge insertion attacks, to gain additional rewards. Such attacks can be prevented by designing an incentive mechanism [16] which adheres to the following rules:

         Rule 1. To prevent an intermediate node from gaining in an edge insertion attack, the reward R(n) for relaying the message via an n hop path must be no less than the total rewards gained through an insertion attack, i.e., 2×R(n+1)

         R(n).

         Rule 2. To prevent a subscriber from benefiting in an edge insertion attack, the charge C(n) for receiving a message via an n hop path must be no larger than the new resulting charge after the insertion attack,i.e., C(n + 1) R(n + 1) C(n).

   3. Multi-Receiver based Incentive Mechanism

      Here the aim is to design an incentive mechanism that encourages nodes to cooperate such that the selected forwarding paths use few transmissions and hence achieves

      high network efficiency. Furthermore, to encourage nodes to make such forwarding decisions in one-to-many dissemination scenarios, the delivery status of messages must be considered. Therefore, assume that every message has a header which contains a pair of values (RSS, RNS) defined as follows:

      Definition 1. The Reachable Subscriber Size (RSS) of a message m is the number of subscribers that have already received m on the path that this message has gone through before being received by the current node.

      Definition 2. The Relay Node Size (RNS) of a message m is the number of intermediate nodes that have successfully delivered at least one copy of m to a subscriber on the path that this message has gone through before being received by the current node.

      With RSS and RNS, we propose the following charge and rewarding functions:

      C(n, ) = 2N 2Nn(1 + (n, )) (2)

      R(n, , ) = 2Nn(1 (, )), (3)

      where N is a predefined maximum allowed hop counts in the network for scalability control, , are values of RSS and RNS respectively, and (.), (.) are two synthetic functions that are introduced to utilize the information from RSS and RNS.

   4. Closeness Vector and Feasible Path

   • Closeness Vector: The encounter time and the associated contact duration recorded by a node when it meets another node can be used to predict future encounters. The concept of closeness using the cumulative window (Cwindow) approach is defined, which calculates the average node encounter duration during previous time windows.

   • Feasible Path Set: Because nodes move around in DTN, the available paths between a pair of nodes change dynamically. A common way to describe the available paths between two nodes in DTNs is to use a sequence of nodes and their corresponding probabilities of reaching a certain destination. Here each node maintain a set of paths that have been used in the past to reach certain subscribers. Set of paths is referred to as the Feasible Path Set.

   Incentive Driven Information Sharing

   A node may be aware of multiple paths that can reach different number of subscribers. Thus, when a node encounters another node, it needs to decide if it should forward a message to that node based on the expected rewards it can gain. The expected rewards are calculated utilizing the closeness vector, feasible path set, and the rewarding function.

   Algorithm Incentive Driven Forwarding

   Require: Message m, forwardNode null

   for neighbornode interested in m do

   SendMessage(m, node)

   end for

   if nexthopList(m).size _= 0 then

   expReward calExpReward(m, thisNode)

   for all nexthop in the list nexthopList do

   if expReward < calExpReward(m, nexthop) then expReward calExpReward(m, nexthop) forwardNode nexthop

   end if end for

   if forwardNode _= null then

   if forwardNode is in communication range then

   sendMessage(m, forwardNode)

   return end if

   end if

   else if thisNode = sourceof(m) then

   for all node in the communication range do

   sendDataMessage(m, node);

   end for end if return

4. CONCLUSION

An incentive driven dissemination scheme is proposed called MuRIS that not only encourages nodes to cooperate but chooses delivery paths that can reach as many subscribers as possible with fewest transmissions. The wise choice of delivery paths is achieved via proposed multi- receiver based incentive mechanism. Furthermore, the charge and rewarding functions not only thwart edge insert attacks but also allow us to achieve high network efficiency. MuRIS exploits locally maintained node encounter history and historical path information to construct Closeness Vector and Feasible Path Set. MuRIS outperforms other existing schemes in achieving high delivery ratio with low overhead ratio. MuRIS performs especially well when the publisher and subscribers come from different communities. Additionally, it will be interesting to explore the impact of feasible path set or the closeness vector on the delivery performance of individual nodes.

REFERENCES

1. V. Lenders, G. Karlsson, and M. May, Wireless ad hoc podcasting, in Proc. 2008 ACM SigMobile Mobile Computing and Communications Review.

2. D. B. Johnson and D. A. Maltz, Dynamic source routing in ad hoc wireless networks, in Mobile Computing, Kluwer Academic Publishers,1996, pp. 153181.

3. G. Ding and B. Bhargava, Peer-to-peer file-sharing over mobile ad hoc networks, in Proc. 2004 IEEE International Conference on Pervasive Computing and Communications Workshops, vol. 0, p. 104.

4. S. Goel, M. Singh, D. Xu, and B. Li, Efficient peer-to-peer data dissemination in mobile ad-hoc networks, in Proc. 2002 International Conference on Parallel Processing Workshops, pp. 152158.

5. B. Xu, A. Ouksel, and O. Wolfson, Opportunistic resource exchange in inter-vehicle ad-hoc networks, in Proc. 2004 IEEE International Conference on Mobile Data Management, pp. 412.

6. Burcea, H.-A. Jacobsen, E. de Lara, V. Muthusamy, and M. Petrovic,