无线传感器网络基于连通性的平面化算法

J4 ›› 2012, Vol. 34 ›› Issue (3): 13-18.

无线传感器网络基于连通性的平面化算法

董德尊1，廖湘科1，沈昌祥2

(1.国防科学技术大学计算机学院，湖南长沙 410073;2.海军计算技术研究所，北京 100841）

收稿日期:2010-03-16 修回日期:2010-11-22 出版日期:2012-03-26 发布日期:2012-03-25

A ConnectivityBased Planarization Algorithm for Wireless Sensor Networks

DONG Dezun1，LIAO Xiangke1，SHEN Changxiang2

(1.School of Computer Science，National University of Defense Technology，Changsha 410073;
2.Naval Institute of Computing Technology，Beijing 100841,China)

Received:2010-03-16 Revised:2010-11-22 Online:2012-03-26 Published:2012-03-25

摘要/Abstract

摘要：

构建平面拓扑结构是无线传感器网络中一个重要的问题，它是设计许多高效网络协议的基础。传感器网络中许多重要的协议和应用都依赖于平面拓扑结构，比如著名的地理路由协议GPSR、GOAFR等。目前的平面化技术往往都需要网络中节点具有精确的位置测量信息。精确的位置或测距信息在资源受限的传感器网络中往往很难得到，因此基于位置的平面化技术的可应用性受到了很大的限制。设计有效的位置无关的平面化算法成为目前平面化技术研究面临的重要问题。本文提出了一种新的位置无关的分布式平面化算法。该方法仅基于网络的通讯连接关系信息，且运行复杂度低，便于分布式执行。本文通过证明确保所构建拓扑的平面性，并通过仿真实验验证了算法在随机生成网络中的有效性。

关键词: 无线传感器网络, 平面化, 拓扑, 连通性

Abstract:

Extracting planar graph from network topologies is of great importance for efficient protocol design in wireless sensor networks. It has become the foundation of many important protocols and applications, such as geographic routing including GPSR, GOAFR, etc. Previous techniques of planar topology extraction are often based on the assumption of accurate node location measurements. It is highly desirable to relax assumptions and extract a planar topology in a locationfree and distributed manner. We present a novel method to construct a planar structure for wireless sensor networks in a distributed manner, merely using connectivity information. Our method can extract a provably planar graph from communication graphs. The extensive simulations also show the effectiveness of this design in randomly generated networks.

Key words: wireless sensor networks;planarization;topology;connectivity

董德尊1，廖湘科1，沈昌祥2. 无线传感器网络基于连通性的平面化算法[J]. J4, 2012, 34(3): 13-18.

DONG Dezun1，LIAO Xiangke1，SHEN Changxiang2. A ConnectivityBased Planarization Algorithm for Wireless Sensor Networks[J]. J4, 2012, 34(3): 13-18.

[1]	施得君, 李宏亮, 胡舒凯. 基于Clos网络的高阶路由器结构[J]. 计算机工程与科学, 2023, 45(12): 2099-2112.
[2]	罗仕杭, 何庆. 多策略融合改进的均衡优化算法及其应用[J]. 计算机工程与科学, 2023, 45(08): 1508-1520.
[3]	葛一漩, 李晨, 陈小文, 鲁建壮, 郭阳. 一种定制片上网络设计探索算法的设计与实现[J]. 计算机工程与科学, 2023, 45(06): 970-978.
[4]	赵玉华, 贾向东, 胡海霞, 敬乐天. 无人机辅助的无线传感网络AoI最小化方案研究[J]. 计算机工程与科学, 2022, 44(07): 1216-1222.
[5]	张孟健, 汪敏, 王霄, 覃涛, 杨靖, . 混合粒子群-蝴蝶算法的WSN节点部署研究[J]. 计算机工程与科学, 2022, 44(06): 1013-1022.
[6]	高航, 吴嘉鑫, 陈龙, 武继刚. QoS保障下的无人机传感网安全通信路径规划[J]. 计算机工程与科学, 2022, 44(06): 1037-1045.
[7]	林楷智, 宗艳艳, 孙珑玲, . AI服务器PCIe拓扑应用研究[J]. 计算机工程与科学, 2022, 44(03): 390-395.
[8]	苟平章, 原晨, 张芬. 基于软件定义的WSNs非均匀分簇QoS路由算法[J]. 计算机工程与科学, 2022, 44(02): 227-236.
[9]	周杨, 董玉辉, 姚旭, 刘强, 孙延涛, 张靓. 空间激光通信网络拓扑算法设计与仿真研究[J]. 计算机工程与科学, 2022, 44(01): 68-74.
[10]	张晶, 魏淼, . 基于Delaunay三角划分策略的WSN区域覆盖优化研究[J]. 计算机工程与科学, 2021, 43(11): 1944-1951.
[11]	魏连锁, 陈齐齐, 韩建, 苏扬. 一种基于区域分裂与合并的势博弈网络拓扑控制算法[J]. 计算机工程与科学, 2021, 43(11): 2063-2068.
[12]	苟平章, 刘学治, 孙梦源, 何博. 基于跳距修正与狮群优化的WSNs三维定位算法[J]. 计算机工程与科学, 2021, 43(08): 1405-1412.
[13]	周静, 关玉蓉. 基于SDN的DWSN技术分析及性能优化研究[J]. 计算机工程与科学, 2021, 43(08): 1413-1421.
[14]	宋玲, 黄达胜. 一种基于狼群优化的改进DV_Hop定位算法[J]. 计算机工程与科学, 2021, 43(07): 1210-1218.
[15]	王俊喜, 陈桂芬. 能耗均衡的多跳多路径认知分层路由算法[J]. 计算机工程与科学, 2021, 43(03): 442-448.