Message ferries as generalized dominating sets in intermittently connected mobile networks

• Published in: Pervasive and mobile computing 2011-04, Vol.7 (2), p.189-205
• Main Authors: Polat, Bahadir K., Sachdeva, Pushkar, Ammar, Mostafa H., Zegura, Ellen W.
• Format: Article
• Language: English
• Subjects: Delay tolerant networks; Dominating sets; Mobility; Routing
• ISSN: 1574-1192; 1873-1589
• DOI: 10.1016/j.pmcj.2011.01.002

Message ferrying is a technique for routing data in wireless and mobile networks where one or more mobile nodes are tasked with storing and carrying data between sources and destinations. To achieve connectivity between all nodes, message ferries may need to relay data to each other. While useful as a routing technique for wireless mobile networks in general, message ferrying is particularly useful in intermittently connected networks where traditional MANET routing protocols are not usable. A wireless and mobile network is said to possess an intrinsic message ferrying capability if a subset of the nodes can act as message ferries by virtue of their own mobility pattern, without introducing additional nodes or modifying existing node mobility. Our goal in this work is to provide a formalism where one can characterize intrinsic message ferrying capability. We first observe that the use of message ferries is the mobile generalization of the well-known use of connected dominating set-based routing in wireless networks. We next consider the problem of identifying the set of nodes in a mobile network which can act as message ferries by virtue of their mobility pattern. To this end, we define the concept of a Connected Message Ferry Dominating Set (CMFDS) in a manner that achieves data delivery within certain performance bounds. We then develop algorithms that can be used to find such a set within a mobile, wireless network or identify that no such set exists. We provide some illustrative examples to show the application of our algorithms to several mobility patterns.