Up-and-Down Routing in Mobile Opportunistic Social Networks with Bloom-Filter-Based Hints

Abstract—In this paper, an up-and-down routing protocol is proposed for mobile opportunistic social networks, which exhibit a nested core-periphery structure. In such a network, a few active nodes with large weighted degrees form the network core, while the network peripheries are composed of many inactive nodes with small weighted degrees. By nested, it means that the core-periphery structure is preserved, when periphery nodes are removed. Based on this structure, a message can be uploaded from the source to the network core, through iteratively forwarding the message to a relay that has a higher position in the nested network hierarchy. Then, space-efficient Bloom-filter-based hints are introduced to provide guidance for downloading messages from the network core to the destination. Through utilizing the network structure and space-efficient routing hints, subtle balances between the data delivery delay, ratio, and cost are achieved by our proposed approach. Finally, through extensive simulations, we show that the up-and-down routing scheme achieves a competitive performance on the data delivery delay and ratio, with a relatively small cost on the prior information maintenance and a relatively low forwarding cost. Keywords—Bloom filter, mobile opportunistic social networks, nested core-periphery network structure, routing hints. I