Effective and efficient collection of control messages for opportunistic routing algorithms

Opportunistic routing algorithms (ORAs) provide a feasible solution to transmit packets in intermittently connected scenarios, where links may be broken due to node mobility or power on/off. To make a smart forwarding decision, most of ORAs have to collect a large amount of control messages, however, few work has focused on how to collect such messages effectively and efficiently. In this paper, we first propose a new hierarchical message collection scheme, called ELECTION to improve the data forwarding performance. ELECTION employs part of the nodes to collect and diffuse the control message. We then design a greedy algorithm to select qualified nodes and theoretically prove that it can achieve the optimum with a probability at least 1−1/e. Finally, by applying ELECTION on real data-sets, the simulation results show that ELECTION reduces cost remarkably compared to the state-of-the-art works, and improves the packet delivery ratio and delay sufficiently under different TTL requirements.