基于无线传感器网络覆盖的部署及调度算法的研究.pdf

南京航空航天大学
硕士学位论文
基于无线传感器网络覆盖的部署及调度算法的研究
姓名:陈杰
申请学位级别:硕士
专业:计算机科学与技术
指导教师:杜庆伟
2010-12
南京航空航天大学硕士学位论文
摘要
传感器网络的覆盖问题是传感器网络的重要研究内容,较强的监视能力和较高容错率对传
感器节点的覆盖质量提出了较高的要求。论文从提高区域覆盖质量和延长网络使用寿命两个角
度出发,对节点部署问题和节点调度问题进行了研究。
在传感器网络节点初始随机部署之后,节点可能分布很不均匀,无法很好地完成目标感知
和数据搜集任务。需要优化传感器节点的部署,使之能满足那些对网络监视能力、定位能力和
数据搜集可靠性要求较高的应用,并同时能兼顾网络的使用寿命。论文首先设计了一个能量有
效的异构传感器网络节点部署算法 EX-VFA(Extended-Virtual Force Algorithm),算法基于概
率感知模型,采用静态部署与动态部署相结合的策略,其中高能量节点静态部署以更好地覆盖
重点保障区域,低能量节点动态部署以满足其它区域的覆盖要求。算法在动态部署阶段提出了
“接替移动法”,有效地减少了节点的平均移动距离,均衡节点移动时的能量消耗。仿真结果
表明,EX-VFA 算法不仅能够满足应用需要的部署要求,同时还能够充分地均衡网络中各节点
的能量消耗,延长网络寿命。
其次,论文提出了能量有效的区域 K 重覆盖节点调度算法 SA(Efficient K- Coverage
Node Schedule Algorithm),在满足较高覆盖质量的要求下调度节点睡眠,最小化活跃节点个数,
节约并均衡网络能量消耗。算法由三个子算法组成: K 重覆盖判定算法,优化了区域 K
重覆盖的计算方法;,以区域 K 重覆盖算法为基础,分别设计了分布式
和集中式的合格性判定方法;,以节点合格性判定算法的判定结果为依据分别
设计了分布式和集中式的节点调度算法。分布式算法能够实现全区域 K 重覆盖,集中式算法能
够满足多个子区域不同覆盖质量的要求。论文的调度算法基于节点的优先级解决了多个节点同
时睡眠产生的盲区问题,充分考虑了节点本身的能量因素,弥补了现有算法的“时间规避机制”
的不足。仿真结果表明, SA 算法不仅能够满足应用需要的覆盖质量要求,同时能够使
得网络在节点能量消耗比较均衡的情况下获得较长的寿命。

关键词:异构传感器网络,概率感知模型,虚拟力,节点部署,K 重覆盖,节点调度

- I -
基于无线传感器网络覆盖的部署及调度算法的研究
ABSTRACT
The coverage is a very important problem of the wireless work. The situations which
require stronger environmental monitoring capability and scenarios which impose more stringent
fault-tolerant capability require high coverage quality of the wireless paper
focused on the problem of improving the coverage quality and prolonging the lifetime work.
The sensors deployment and the nodes schedule problem are both studied deeply in this paper.
After initial random deployment, the nodes in works are not uniform distributed enough to
complete the task of sensor and data collecting perfectly. Thus, the deployment of nodes needs to be
optimized to meet the requirement of high monitoring capability, fault-tolerant capability, locating
capability and data reliability and the lifetime paper first design an ener