第
31
卷第
10
期
20
口年
lQll
计算机应用
Vo
l.
31
No.
lO
Oc
t.
2011
JoumaLof ComputerApplications
文章编号:
1001 - 9081
(2011)
10 - 2625 - 05
doi:l0.3724/SP.J.I087.2011.02625
传感器网络中基于移动
sink
最优穿越路径的高效数据收集算法
李彬,林亚平,周四望,黄岑桑,罗卿
(湖南大学信息科学与工程学院,长沙
410082)
(bawojinti3n@
126.
com)
摘
要:移动
sink
数据收集研究主要集中在轨迹固定的移动策略。为此,建立了移动
sink
穿越路径可控条件下
的数据收集模型,并提出一种最优路径穿越的移动
sink
数据收集算法(
OTP-TS)
。算法利用局部
Voronoi
网格将连续
路径问题离散化,以收集数据量、系统能耗为衡量指标,结合禁忌搜索算法,实现系统数据量最大化和网络能耗最小
化穿越。理论分析和实验结果表明,该算法很好地解决了移动
sink
在可控移动轨迹情况中数据收集的最优路径穿越
问题。
关键词:无线传感器网络;移动
sink;
最优路径;数据收集;
Voronoi
网格
中图分类号:
T
P3
93.03
文献标志码
:A
Efficient
data
collection algorithm in
sensor networks with optimal-path mobile sink
LI
Bin
,
LIN
Ya-ping
,
ZHOU
Si-wang
,
HUANG
Cen-xi
,
LUO
Qing
(
College
of
Inforrrwtion
Science
αnd
Engineering, Hunan
University
,
Ch
α
ngsh
α
Hunan
410082
,
China)
Abstract:
Mobile sink can efficiently collect data and extend the network lifetime. However, the existing researches
about data collection based on mobile sink mainly focus on path-constrained mobile sink. Hence, a path-controlled traversal
model for mobile sink data collection
was
constructed, and a data collection algorithm for mobile sink based on optimal-path
traveling
was
proposed. The algorithm discretized the continuous path problem by local Voronoi grid, used the amount of data
collected and system energy consumption as performance metric, combined taboo search algorithm
to
achieve the maximum
amount of data collected and the minimum of network energy consumption traversing. Theoretically and experimentally, it is
concluded that the proposed algorithm is able
to
solve the optimal-path traveling of data collection problem using path-
controlled mobile sink
Key
words:
Wireless Sensor Network
(WSN);
mobile sink; optimal-path; data collection; Voronoi grid
0
引言
元钱传感器网络
(Wireless
Sensor N etwork ,
WSN)
是由大
量传感器节点组成的一种特殊的
Ad
Hoc
网络,具有十分广泛
的应用前景,如环境监测、战场监控、医疗护理、智能交通等。
数据收集是
WSN
的首要任务之一,传统的采用静态
sink
的
数据收集方法容易造成
sink
周围的节点需要转发更多数据
而过早死亡,导致网络出现分割。以往解决这一问题主要在
传感节点分簇算法和数据融合算法等方面的研究。近年来,
人们引人移动
sink
方案
[1
-2J
来均衡全网节点能量消耗,缓解
能耗瓶颈,提高整个网络的吞吐量,延长网络生存时间。
目前
WSN
中基于
sink
节点的数据收集策略研究主要有
如下
3
类:
1)
sink
轨迹随机移动
;2)sink
轨迹固定移动;
3)
sink
轨迹可控移动。如图
1
所示,描述了移动
sink
在无线
传感器网络中数据收集应用场景。传感器节点随机均匀部署
在传感区域
F
,
移动
sink
节点
M
以上述
3
种移动策略从传感
区域的一端移动到另一端,当
M
移动到节点附近时,节点向
M
传输数据。
本文研究轨迹可控的移动
sink
在无线传感器网络数据
收集中的应用。其中,传感器节点随机均匀地分布在监测区
域,并采用多跳的方式将数据传输到移动
sink
,移动
sink
节点
以恒速率从监测区域一端穿越到另一端。
sink
节点的移动性
会限制它与周围节点的通信时间,从而约束了系统数据收集
能力。如何规划移动
sink
的穿越路径来最大化数据收集量,
提高系统能耗利用率,已成为移动
sink
在传感器网络数据收
集应用中亟待解决的问题。
•
'
F
•
•
• •
P
曰
:-COLIIJ-
Mjj?ι
二、,工艺
:7177d
•
•
• •
•
•
•
•
图
1
元线传感器网络移动
sink
应用场景
为此,针对轨迹可控移动
sink
在大规模密集型传感器网
络数据收集中的应用,本文综合考虑移动
sink
路径选择的衡
量标准,提出一种基于禁忌搜索算法的最优路径穿越高效数
据收集算法。算法以
sink
节点通过路径的数据收集量最大
收稿日期
:2011-04-01;
修回日期
:2011-06-02
。
基金项目:国家教育部博士点基金资助项目
(20100161110025)
。
作者简介:李彬(1
984
- )
,男,湖南新化人,硕士研究生,主要研究方向:元线传感器网络;
林亚平(1
955
- )
,男,湖南邵阳人,教授,博士生导
师,主要研究方向:计算机网络、机器学习;
周四望(1
971
- )
,男,湖南岳阳人,副教授,主要研究方向:无线传感器网络;
黄岑载(
1983
- )
,女,福
建三明人,硕士研究生,主要研究方向:无线传感器网络、网络安全;
罗卿(1
981
- )
,男,湖南衡阳人,博士研究生,主要研究方向:无线传感器网络。