异构无线网络中 Relay 节点部署算法

摘要：

目前越来越多的无线网络技术涌现出来，如 ZigBee 技术、多频段的 Mesh 网技术、IEEE 802．16j 技术等，上述无线网络有效的前提是要依靠于网络的连通．而事实上由于多种因素，如随机部署、意外损坏、能量耗尽等，导致无线网络的不连通是非常常见的，通常可以通过新加入一定数量的 relay 节点从而实现网络的连通．现有的 relay节点部署研究都是基于被加入 relay 节点的网络本身是同构这一假设，事实上异构网络情况是非常常见的，所以该文致力于研究在异构传感器网络中部署 relay 节点问题，该问题可以被证明为 NP-Hard．该文首先推导了以前工作中所提出用于同构网络的 relay 节点部署算法应用在异构网络中所能达到的近似比，提出了两种分别基于权重图增量和基于迭代权重图增量的 relay 节点部署算法，并推导出这两种算法的近似比为10，最后通过实验给出以上3种部署算法在网络中不同低能力节点数量、不同高能力节点通讯半径和不同高能力节点数量情况下的使用效果，验证了该文算法效果．

关键词：无线网络、网络连通、relay节点部署、部署算法、物联网

所属期刊栏目：39

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金61370214，61300210资助．

在线出版日期：2016-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：905-918