作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (10): 95-98. doi: 10.3969/j.issn.1000-3428.2012.10.028

• 网络与通信 • 上一篇    下一篇

传感器网络节点选择的分布式在线算法

陈光平   

  1. (中国计量学院信息工程学院,杭州 310018)
  • 收稿日期:2012-02-22 出版日期:2012-05-20 发布日期:2012-05-20
  • 作者简介:陈光平(1976-),男,工程师、硕士研究生,主研方向:传感器网络
  • 基金资助:
    浙江省教育厅科技计划基金资助项目(20060520)

Distributed Online Algorithm of Node Selection in Sensor Network

CHEN Guang-ping   

  1. (College of Information Engineering, China Jiliang University, Hangzhou 310018, China)
  • Received:2012-02-22 Online:2012-05-20 Published:2012-05-20

摘要: 大型传感器网络部署的关键是在能量消耗最小的前提下激活传感器节点以获取有价值信息,这要求在效用函数事先不可知的情况下通过分布式方式选择正确的传感器节点。为此,提出一种分布式在线贪心算法。以效用函数满足子模性的自然报酬递减特性为前提,在模型未知的情况下,通过在线学习方式优化目标函数。实验结果表明,该算法的收敛性近似于传统的集中式方法,且在运行中所需的通信消息量较少,适用于大型网络传感器节点的部署。

关键词: 传感器网络, 节点选择, 贪心算法, 子模性优化

Abstract: A key problem in deploying large sensor networks is to obtain the most useful information from the network when subject to constraints on power, which requires the solution should be a online distributed optimization to select and activate right sensors on condition that the utility function is not known a priori. In order to address above challenges, this paper develops an efficient distributed online greedy algorithm, which can be applied to any setting where the utility function satisfies an intuitive diminishing return property of submodularity. The algorithm does not require the model to be specified in advance, and learns to optimize the objective function in an online distributed manner, requires only a small number of messages to be exchanged with high probability, which can scales well to large sensor deployments. Experimental results show the algorithm’s performance converges towards the performance of the common offline greedy algorithm and is effective on real-world sensing tasks.

Key words: sensor network, node selection, greedy algorithm, submodularity optimization

中图分类号: