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

发布时间：2018-03-31 06:18

本文选题：无线网络　切入点：网络连通　出处：《计算机学报》2016年05期

【摘要】：目前越来越多的无线网络技术涌现出来,如ZigBee技术、多频段的Mesh网技术、IEEE 802.16j技术等,上述无线网络有效的前提是要依靠于网络的连通.而事实上由于多种因素,如随机部署、意外损坏、能量耗尽等,导致无线网络的不连通是非常常见的,通常可以通过新加入一定数量的relay节点从而实现网络的连通.现有的relay节点部署研究都是基于被加入relay节点的网络本身是同构这一假设,事实上异构网络情况是非常常见的,所以该文致力于研究在异构传感器网络中部署relay节点问题,该问题可以被证明为NP-Hard.该文首先推导了以前工作中所提出用于同构网络的relay节点部署算法应用在异构网络中所能达到的近似比,提出了两种分别基于权重图增量和基于迭代权重图增量的relay节点部署算法,并推导出这两种算法的近似比为10,最后通过实验给出以上3种部署算法在网络中不同低能力节点数量、不同高能力节点通讯半径和不同高能力节点数量情况下的使用效果,验证了该文算法效果.
[Abstract]:At present, more and more wireless network technologies are emerging, such as ZigBee technology, Mesh network technology in multi-frequency band, IEEE802.16j technology and so on. The premise of the above wireless network efficiency is to rely on network connectivity, but in fact, due to many factors, such as random deployment, Accidental damage, energy depletion, etc., leading to disconnection of wireless networks is very common. Network connectivity can usually be achieved by adding a certain number of new relay nodes. The existing research on the deployment of relay nodes is based on the assumption that the network itself is isomorphic. In fact, heterogeneous networks are very common. Therefore, this paper focuses on the problem of deploying relay nodes in heterogeneous sensor networks. This problem can be proved to be NP-Hard.Firstly, the approximate ratio of relay node deployment algorithm for isomorphic networks applied to heterogeneous networks is derived in this paper. Two relay node deployment algorithms based on weight graph increment and iterative weight graph increment are proposed. The approximate ratio of these two algorithms is 10. Finally, the results of the above three deployment algorithms in different low capacity nodes, different communication radii and different high capacity nodes in the network are given through experiments. The effectiveness of the algorithm is verified.
【作者单位】：哈尔滨理工大学软件学院;哈尔滨工业大学计算机科学与技术学院;
【基金】：国家自然科学基金(61370214,61300210)资助~~
【分类号】：TN92

【参考文献】