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

Yan hua LI, Yuan an LIU

Research output: Contribution to journalArticlepeer-review


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%.

Original languageEnglish (US)
Pages (from-to)42-46
Number of pages5
JournalJournal of China Universities of Posts and Telecommunications
Issue number4
StatePublished - Aug 2009

Bibliographical note

Funding Information:
This work was supported by the National Natural Science Foundation of China (60573111), the Project for Supporting Excellent Scholars in the New Century, and the Ministry of Education of China (NCET-04-0112).


  • graph partitioning
  • mobile Ad-hoc network
  • opportunistic routing
  • wireless routing

Fingerprint Dive into the research topics of 'Graph partitioning algorithm for opportunistic routing in large-scale wireless network'. Together they form a unique fingerprint.

Cite this