计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (20): 80-86.DOI: 10.3778/j.issn.1002-8331.1707-0103

• 网络、通信与安全 • 上一篇    下一篇

网络节点布置问题的算法设计

王勇杰   

  1. 山西大学商务学院 电子商务系,太原 030031
  • 出版日期:2018-10-15 发布日期:2018-10-19

Algorithm designs for node placement in networks

WANG Yongjie   

  1. Department of Electronic Commerce, Business College of Shanxi University, Taiyuan 030031, China
  • Online:2018-10-15 Published:2018-10-19

摘要: 节点布置问题随着数据量的增多变得越来越重要,它决定着整个网络模型的覆盖情况,并且对于整个网络的能耗、效率等一些因素也有影响,因此研究节点布置问题对于提升网络性能至关重要。而节点布置问题又分为两个子问题,区域覆盖问题和中心点选择问题,对于区域覆盖问题,利用虚拟力场的方法,使每个节点自身根据受力情况进行相应的移动,扩大区域的覆盖范围;对于中心点选择问题,提出了两种基于不同策略的[k]-中心算法来对节点进行聚类处理,降低节点之间的通讯开销。最后,通过大量的仿真实验来验证提出的算法能够很好地解决节点布置问题,提升整个网络的性能。

关键词: 节点布置, 区域覆盖, 节点聚类, 虚拟力, [k]-中心

Abstract: Node placement becomes more important with the increasing of data. It not only determines the coverage of the networks, but also influences the energy consumption, efficiency and other factors. Therefore, it is necessary to do researches about node placement to improve the networks performance. The node placement problem contains two subproblems, area coverage problem and center selection problem. For area coverage problem, it uses the virtual force method that makes each node moves according to its forces, extending the coverage. For center selection problem, it proposes two different[k]-center algorithms to cluster these nodes, decreasing the communication cost between nodes. In the end, it implements many simulations to detect the algorithms. They can deal with the node placement problem perfectly and improve the networks performance.

Key words: node placement, area coverage, node clustering, virtual force, [k]-center