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

作     者：LI Yan-hua LIU Yuan-an 

作者机构：Wireless Communication Center Beijing University of Posts and Telecommunications Beijing 100876 China 

出 版 物：《The Journal of China Universities of Posts and Telecommunications》 (中国邮电高校学报（英文版）)

年 卷 期：2009年第16卷第4期

页      面：42-46页

核心收录：

学科分类：0810[工学-信息与通信工程] 08[工学] 080203[工学-机械设计及理论] 081001[工学-通信与信息系统] 0802[工学-机械工程] 

基　　金：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) 

主　　题：opportunistic routing graph partitioning wireless routing mobile Ad-hoc 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%.