没有合适的资源?快使用搜索试试~ 我知道了~
异构有向传感器网络连通覆盖调度算法.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 87 浏览量
2022-12-15
14:20:49
上传
评论
收藏 242KB DOCX 举报
温馨提示
试读
16页
异构有向传感器网络连通覆盖调度算法.docx
资源推荐
资源详情
资源评论
近年来,无线视频传感器(其感知具有方向性,隶属于有向传感器)逐渐取代有线视频
监控传感器,其安装简便,价格便宜,应用场景不断拓展。传感器网络节点覆盖调度对于
网络同步与分布式优化起着重要作用
[1-4]
。在满足监测目标监测覆盖的要求下,如何借助节
点调度算法延长有向传感器网络的工作时间是有向传感器网络的重要研究内容。文献[5]提
出一种基于概率覆盖圆的连通有向传感器网络的目标覆盖增强算法。文献[6]提出了一种面
向有向传感器网络的基于遗传算法的 k 覆盖算法,通过求解多个满足目标 k 覆盖要求且节
点数量最少的集合延长网络的寿命。文献[7]通过建立一种混合二进制整数线性规划模型,
求解得到多个互不相交的覆盖集合来延长有向传感器网络的寿命。这些研究都是假设参与
节点调度的传感器节点参数相同,未考虑异构节点对调度算法的影响。同时,均假定监测
目标在区域内均匀分布,未考虑监测目标的重要性、出现频率对网络服务质量的影响。对
于异构有向传感器网络,文献[8]提出两种启发式算法解决有向传感器网络的寿命最大化问
题,两种算法的区别在于每次选取节点感知方向的标准不同。一种为每次选取对目标覆盖
贡献最大(也就是覆盖最多目标)的感知方向,另一种为每次选择能覆盖监测目标且能量最
少的感知方向,两种算法结束的条件均为直到所有的目标满足覆盖要求。文献[9]提出一种
基于学习自动机的算法解决感知半径可调的有向传感器网络的 k-覆盖问题。文献[10]提出
一种基于遗传算法的寿命最大化策略来延长半径可调的有向传感器网络的寿命。针对异构
有向传感器网络的寿命优化问题,利用集合覆盖的思想,文献[11]通过改进的和声搜索算
法求解满足目标覆盖要求的集合,解决差异化覆盖条件下异构有向传感网络寿命的问题。
文献[12]将学习自动机引入差分进化算法,实现算法参数的自适应并增强算法的优化能
力,使寿命达到最大化。但这些文献没有考虑网络的连通性,使得算法在工程实践中受到
影响。尽管文献[13-14]对差异化覆盖连通问题进行了研究,但其研究对象为全向感知和节
点同构的传感器网络,研究成果不适用于感知模型为有向的异构有向传感器网络。
针对上述研究中存在的问题,在满足应用场景监测目标覆盖要求差异化和网络连通的
条件下,本文提出一种面向异构有向传感器网络的节点调度算法,达到降低网络能耗和延
长网络工作时长的目标。
1. 问题描述及数学建模
在二维监测区域中随机部署 N 个不同的感知半径 r
i
、通信半径 c
i
、携带能量 E
i
、感知
角度 θiθi 的传感器节点 s
i
(i =1, 2, ···, N),用于监测 W 个目标。由节点的感知角度得出可用
的感知方向为 2πθi2πθi,本文假定节点的感知方向不重叠,在工作状态时传感器节点消耗
的能量 e
i
不同,非工作状态时节点不消耗能量,则可得出节点的寿命为 Li=Ei/eiLi=Ei/ei。
根据监测目标出现的频率将其分为重点目标(出现频率高)和非重点目标。为保证网络服务
质量和网络可靠性,要求至少两个传感器节点对对重点目标进行监测,其他目标只要能监
测到就符合应用需求。
定义 传感网络的寿命
[12]
网络中的传感器节点能提供符合监测目标的监测要求且能保
持网络连通的时间。
在满足监测目标的监测覆盖需求和保持网络连通的前提下,如何延长传感网络的寿命
是本文要解决的问题。其形式化的描述为:
Maxt1+t2+⋯+tkMaxt1+t2+⋯+tk
(1)
s.t.∑k=1K∑j=1|Di|bi,j,kei⩽Eii∈[1,K]s.t.∑k=1K∑j=1|Di|bi,j,kei⩽Eii∈[1,K]
(2)
∑j=1|Di|bi,j,k⩽1i,k∈[1,N]∑j=1|Di|bi,j,k⩽1i,k∈[1,N]
(3)
∑Di,j∈C_Tk,mbi,j,k⩾Req(Tm)k∈[1,K],m∈[1,W],bi,j,k={10Di,j∈Ck其他∑Di,j∈C_Tk,mbi,j,k⩾Req(Tm)k∈[1,K],m∈[1,W],bi,j,k={1Di,j∈Ck0 其他
(4)
∑j=1Nconi,j⩾1j≠i且 1⩽i,j⩽N∑j=1Nconi,j⩾1j≠i 且 1⩽i,j⩽N
(5)
coni,j={10节点 si与节点 sj连通其他 coni,j={1 节点 si 与节点 sj 连通 0 其他
除了增加式(5)的连通要求,该数学模型与文献[11]相同。式中,KK 表示满足覆盖连
通要求的集合数;tktk 为第 kk 个覆盖连通集的工作时长,其大小由集合中能量最小的节点
决定;Di,jDi,j 为节点 sisi 的第 jj 个感知方向;CkCk 为第 kk 个符合连通覆盖要求的节点集
合;C_Tk,mC_Tk,m 表示在 CkCk 中能覆盖监测目标 TmTm 的感知方向的集合;
Req(Tm)Req(Tm)表示监测目标 TmTm 要求同时被多少个传感器节点监测,取值为正整
数,由目标本身的特性或出现的区域决定。采用文献[15]中的有边界的帕累托分布模拟目
标在某一时间段内的出现情况,其参数取值与文献[15]相同,仿真结果如图 1 所示。其
中,“□”目标出现频繁的区域为重点区域,对于这些区域的监测目标要求
Req(Tm)⩾2Req(Tm)⩾2,其他区域 Req(Tm)=1Req(Tm)=1 即可。式(2)对节点的能量进行
约束,使得其工作时消耗的总能量不超过其携带的总能量。式(3)表示传感器节点在工作状
态时只能有一个感知方向。式(4)表示由传感器节点构成的集合能满足所有监测目标要求。
式(5)保证传感器节点之间是相互连通的,本文假定传感器节点在其通信半径内有其他节点
存在时则该节点连通的。
图 1 监测目标出现区域示意图
下载: 全尺寸图片 幻灯片
考虑到集合覆盖问题为 NP-hard 问题
[11]
,本文利用珊瑚礁算法进行求解。
2. 连通覆盖调度算法
2.1 原始珊瑚礁优化算法
珊瑚礁算法
[16]
是一种模拟珊瑚虫行为的智能进化算法,已用于求解农场风力资源优
化、有向传感器网络资源优化
[17]
等组合优化问题。该算法的步骤为:初始化、繁殖过程、
竞争过程和淘汰过程。其中,种群初始化实现算法参数的初始化,包括:珊瑚礁的面积(通
常为 W×L 矩形)、珊瑚礁中存在珊瑚虫的比例 pro、迭代数 I_MAX、非性繁殖(即雌雄同体)
的比重 F
a
、迭代过程中子代寻找珊瑚礁附着时允许尝试的最大次数 T_MAX、珊瑚虫被淘
汰的概率 pro_coral 和被淘汰珊瑚虫与珊瑚虫总数的比重 pro_no。珊瑚虫的繁殖行为包括:
剩余15页未读,继续阅读
资源评论
罗伯特之技术屋
- 粉丝: 3655
- 资源: 1万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功