Multi-Axis Projection Based Giant Component Formation in Random Unit-Disk Graphs  

作　　者：Pengfei Hu Kai Xing Liusheng Huang Yang Wang Dapeng Wang Pei Li 

机构地区：[1]School of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China [2]Suzhou Institute for Advanced Study, University of Sciences and Technology of China, Suzhou 215123, China [3]AIcatel-Lucent Shanghai Bell, Shanghai 201206, China [4]College of Information Systems and Management, National University of Defense Technology, Changsha 410073, China

出　　处：《Tsinghua Science and Technology》2011年第5期553-558,共6页清华大学学报（自然科学版（英文版）

基　　金：Supported by the National Natural Science Foundation of China(No. 60903055);the China Postdoctoral Science Foundation Funded Project (No. 20080430776);the National Basic Research and Development (973) Program of China (No. 2011CB302905)

摘　　要：This paper proposes a multi-axis projection （MAP） based giant component formation strategy via the Maximal Independent Set （MIS） in a random unit-disk graph. We focus on the problem of virtual backbone construction in wireless ad hoc and sensor networks, where the coverage areas of the nodes are disks with identical radii. In the simulation, we show that the MAP-based giant component has the ability to connect most nodes and serves as a backbone in the network. The algorithm is localized and may play an important role in efficiently constructing a virtual backbone for ad hoc and sensor networks.This paper proposes a multi-axis projection （MAP） based giant component formation strategy via the Maximal Independent Set （MIS） in a random unit-disk graph. We focus on the problem of virtual backbone construction in wireless ad hoc and sensor networks, where the coverage areas of the nodes are disks with identical radii. In the simulation, we show that the MAP-based giant component has the ability to connect most nodes and serves as a backbone in the network. The algorithm is localized and may play an important role in efficiently constructing a virtual backbone for ad hoc and sensor networks.

关 键 词：ad hoc and sensor networks maximal independent set giant component 

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论] O157.5[自动化与计算机技术—计算机科学与技术]