Graph partitioning algorithm for opportunistic routing in large-scale wireless network

Opportunistic routing takes advantage of the broadcast nature of wireless communications by forwarding data through a set of opportunistic paths instead of one 'best' path in traditional routing. However, using the global scheduling opportunistic scheme like the existing opportunistic routing protocol (ExOR) would consume considerable transmission latency and energy in large-scale wireless topologies. In this article, a graph partitioning algorithm is proposed, namely, minimum cut with laplacians (MCL), to divide the Ad-hoc network topology into subgraphs with minimized edge cuts across them. Then the existing opportunistic routing can be applied locally in each subgraph. In this way, forwarders in different subgraphs can transmit simultaneously, and each node only needs to maintain a local forwarder list instead of a global one. The simulations show that using MCL scheme in the opportunistic routing can reduce the end-to-end delay by about 49%, and increase the life time of the wireless node by about 39%.