法律状态公告日
法律状态信息
法律状态
2018-07-03
授权
授权
2014-09-10
实质审查的生效 IPC(主分类):H04W16/18 申请日:20140527
实质审查的生效
2014-08-13
公开
公开
技术领域
本发明属于无线网络传感器技术领域,尤其涉及一种无线网络传感器覆盖的分布式方法。
背景技术
无线传感器网络是由大量能量有限的微型传感器节点组成,这些节点被随机部署在指定的监测区 域,以探测覆盖监测区域中的重要目标。因此,选择合适的节点进行工作,让有限的能量得到合理且有 效的利用是无线传感器网络设计的核心,在有限的网络寿命中让节点对关键位置的感知覆盖最大化是无 线传感器网络研究的热点之一。
现有的大多数覆盖算法都是在满足特定区域覆盖的情况下,研究如何延长网络寿命。然而,少有工 作主要研究如何让节点对关键位置的覆盖最大化。文献《Spatial-temporalcoverageoptimizationinwireless sensornetworks》和《DistributedCriticalLocationCoverageinWirelessSensorNetworkswithLifetime Constraint》将网络寿命设为定值,选择工作节点最优的工作时间方案,使得节点对关键位置的覆盖最大。 不同的是,文献《Spatial-temporalcoverageoptimizationinwirelesssensornetworks》主要研究对区域的面 覆盖,《DistributedCriticalLocationCoverageinWirelessSensorNetworkswithLifetimeConstraint》主要研 究对关键的点位置的覆盖,此外,在文献《Spatial-temporalcoverageoptimizationinwirelesssensornetworks》 中提出的分布式算法实质上是性能没有保障的启发式算法,而文献《DistributedCriticalLocationCoverage inWirelessSensorNetworkswithLifetimeConstraint》证明了它的算法的近似度为一个常数。然而将网络寿 命设为定值的弊端是使得网络不能满足富于变化的任务需求,同时忽视了网络寿命可提高的空间,最终 使得节点对点位置的覆盖没有达到最大。因此,对文献《DistributedCriticalLocationCoverageinWireless SensorNetworkswithLifetimeConstraint》进行了改进,目的是在满足任务指定时间的前提下,使得节点 对点位置的覆盖最大,同时让实际网络寿命大于任务指定的时间。
发明内容
本发明实施例的目的在于提供一种无线网络传感器网络覆盖的分布式方法,旨在解决现有的算法将 实际网络寿命设为常量,不能很好的满足动态的任务要求,因此忽略了实际的网络寿命可以提升的空间, 从而使得总的有效覆盖时间没有到达最大的问题。
本发明实施例是这样实现的,一种无线网络传感器网络覆盖的分布式方法,该无线网络传感器网络 覆盖的分布式方法包括:
将任务指定完成时间设为预设网络寿命,并将设为常值的预设网络寿命L按轮来划分为轮,每一 轮时间为l,在每一轮中通过筛选最大额外有效覆盖时间大于零的节点进行工作,其他冗余节点关闭探测 功能进入睡眠;
在每一轮挑出合适的工作节点后,通过比较工作节点与邻居工作节点之间的最大额外有效覆盖时间 和剩余能量来选择最优的工作时间方案,从而使得每一轮中总的有效覆盖时间最大,工作节点si额外有 效覆盖时间为:其中R(i)表示节点si覆盖的点位置集合,w(i)表示点位置pj的 重要性系数,即pj的权值,表示点位置pj被节点si覆盖的额外时间,此外在每一轮中都设置了工作 节点的剩余能量安全阈值,若工作节点的剩余能量低于该安全阈值时,则该节点将被强制关闭它的探测 功能,只维持部分的通讯功能。
进一步,该无线网络传感器网络覆盖的分布式方法为了分析不同方案对网络寿命的影响,定义了网 络节点剩余能量均匀度这一新指标,即为工作节点剩余能量的均值与它的方差之间的比例,通过该指标 来度量每一轮中所有工作节点剩余能量的平均值和工作节点消耗的是否均匀,此外还通过选择让每一轮 网络节点剩余能量均匀度达到最大的合适参数将工作节点的最大额外有效覆盖时间和节点的剩余能量进 行有效的结合。
进一步,该无线网络传感器网络覆盖的分布式方法在满足预设网络寿命为常值的条件下,使得节点 对关键点位置的总的有效覆盖时间最大的方法,其中任务指定的完成时间被定义为无线传感器网络的预 设网络寿命,以有效覆盖时间量化节点对目标覆盖的质量,总的有效覆盖时间通过计算每个点位置的有 效覆盖时间的总和得出,即其中P表示点位置的指标集,wi表示点位置pi的重要性系数, 即为点位置的权值,Ti表示点位置的有效时间。
进一步,该无线网络传感器网络覆盖的分布式方法通过比较每个节点的最大有效覆盖时间来挑选出 最合适的节点参加工作。
进一步,该无线网络传感器网络覆盖的分布式方法在指定的时间内,通过比较工作节点的最大有效 覆盖时间和剩余能量来安排工作节点的最优探测活动时间,从而使得总的有效覆盖时间最大;
数学模型如下:
ST:0≤si.start≤l,i∈N (2)
si.end-si.start=bi,i∈N (3)
其中C为总的有效覆盖时 间,l是每一轮的时间,bi是节点si在每一轮中的工作时间。
进一步,该无线网络传感器网络覆盖的分布式方法具体包括以下步骤:
步骤一,节点si的邻居,覆盖的点位置,预设网络寿命L,电池寿命Bi,si的标记类型UPD,ii=1;
步骤二,判断是否ii<L/l,若是,则直接进行下一步,否,则标记类型,标记为LAB的节点的 最优工作时间安排,然后结束;
步骤三,计算最大额外有效覆盖时间和工作优先度,并向邻居广播mes(i,Null,UPD,ΔPi);
步骤四,判断若,是,si的ΔPP·在邻居中是否最大,若si的ΔPi·在邻居中是 最大,si标记自己为LAB并向邻居广播mes(i,LAB,sch,ΔPi)di=di-bi,siexits.;若si的ΔPi·在邻居 中不是最大,判断si是否接收到邻居sk的mes(k,LAB,sch,ΔPk);若si是接收到邻居sk的 mes(k,LAB,sch,ΔPk),则si更新邻居sk的信息,重新计算并且向邻居广播 mes(i,UPD,Null,ΔPi);若si没有接收到邻居sk的mes(k,LAB,sch,ΔPk),则,判断si是否接收到邻 居sk的mes(k,UPD,Null,ΔPk),若si是接收到邻居sk的mes(k,UPD,Null,ΔPk),si更新邻居sk的工作优先度; 若si没有接收到邻居sk的mes(k,UPD,Null,ΔPk),则返回判断
本发明提供的无线网络传感器网络覆盖的分布式方法,任务指定完成时间被设为定值,针对如何使 得节点对点位置的覆盖最大化建立了数学模型;为求解此模型,任务指定完成时间被按轮进行划分,研 究每一轮中如何挑选最合适的工作节点,同时关闭其他冗余节点,使得实际网络寿命大于任务指定时间; 此外每一轮中如何选择工作节点的最优工作时间方案,使得节点对点位置的覆盖最大;因此,提出了改 进的分布式算法。本发明通过仿真实验,在总有效覆盖时间、网络寿命、平均加权事件探测率和网络节 点剩余能量均匀度方面,改进的算法的性能都超过了原来的算法和随机算法的性能。
附图说明
图1是本发明实施例提供的无线网络传感器网络覆盖的分布式方法流程图。
图2是本发明实施例提供的演示在每一轮中如何计算ΔPi和如何选择合适工作节点的例子示 意图;
图3是本发明实施例提供的总的有效覆盖时间与节点数目之间的关系示意图;(p=20u=1/5)
图4是本发明实施例提供的网络寿命与节点数目之间的关系示意图;(p=20,u=1/5)
图5是本发明实施例提供的事件探测率与节点数目之间的关系示意图;(p=20u=1/5)
图6是本发明实施例提供的节点剩余能量均匀度的比较示意图;(p=20,u=1/5)
图7是本发明实施例提供的事件探测率与节点数目之间的关系示意图;(p=20u=1/10)
图8是本发明实施例提供的总的有效覆盖时间与位置点的数目之间的关系示意图;(n=200,u=1/5)
图9是本发明实施例提供的事件探测率和电池与预设网络寿命比率之间的关系示意图。(n=200,p=20)
具体实施方式
为了使本发明的目的、技术方案及优点更加清楚明白,以下结合实施例,对本发明进行进一步详细 说明。应当理解,此处所描述的具体实施例仅仅用以解释本发明,并不用于限定本发明。
下面结合附图及具体实施例对本发明的应用原理作进一步描述。
如图1所示,本发明实施例的无线网络传感器网络覆盖的分布式方法包括以下步骤:
S101:节点si的邻居,覆盖的点位置,预设网络寿命L,电池寿命Bi,si的标记类型UPD,ii=1;
S102:判断是否ii<L/l,若是,则直接进行下一步,否,则标记类型,标记为LAB的节点的最 优工作时间安排,然后结束;
S103:计算最大额外有效覆盖时间和工作优先度,并向邻居广播mes(i,Null,UPD,ΔPi);
S104:判断若,是,si的ΔPi·在邻居中是否最大,若si的ΔPi·在邻居中是最 大,si标记自己为LAB并向邻居广播mes(i,LAB,sch,ΔPi)di=di-bi,siexits.;若si的ΔPi·在邻居中 不是最大,判断si是否接收到邻居sk的mes(k,LAB,sch,ΔPk);若si是接收到邻居sk的 mes(k,LAB,sch,ΔPk),则si更新邻居sk的信息,重新计算并且向邻居广播 mes(i,UPD,Null,ΔPi);若si没有接收到邻居sk的mes(k,LAB,sch,ΔPk),则,判断si是否接收到邻 居sk的mes(k,UPD,Null,ΔPk),若si是接收到邻居sk的mes(k,UPD,Null,ΔPk),si更新邻居sk的工作优先度; 若si没有接收到邻居sk的mes(k,UPD,Null,ΔPk),则返回判断
本发明将任务指定完成时间设为预设网络寿命,并将设为常值的预设网络寿命L按轮来划分为轮, 每一轮时间为l,在每一轮中通过筛选最大额外有效覆盖时间大于零的节点进行工作,其他冗余节点关闭 探测功能进入睡眠,从而使得实际网络寿命大于任务指定时间,将任务指定完成时间设为常值解决了将 网络寿命设为常值使得网络不能满足富于变化的任务需求,同时忽视了网络寿命可提高的空间,最终使 得节点对点位置的覆盖没有达到最大;
在每一轮挑出合适的工作节点后,通过比较工作节点与邻居工作节点之间的最大额外有效覆盖时间 和剩余能量来选择最优的工作时间方案,从而使得每一轮中总的有效覆盖时间最大,这里工作节点si额 外有效覆盖时间为:其中R(i)表示节点si覆盖的点位置集合,w(i)表示点位置 pj的重要性系数,即pj的权值,表示点位置pj被节点si覆盖的额外时间,此外在每一轮中都设置了 工作节点的剩余能量安全阈值,若工作节点的剩余能量低于该安全阈值时,则该节点将被强制关闭它的 探测功能,只维持部分的通讯功能。
通过比较节点最大额外有效覆盖时间和剩余能量来选择工作节点的工作时间方案解决了仅仅通过比 较节点的最大额外覆盖时间来选择节点的工作时间方案,使得最大额外有效覆盖时间最大的节点在每一 轮中都长时间进行工作从而迅速死亡的问题。
为了分析不同方案对网络寿命的影响,本发明定义了网络节点剩余能量均匀度这一新指标,即为工 作节点剩余能量的均值与它的方差之间的比例,通过该指标来度量每一轮中所有工作节点剩余能量的平 均值和工作节点消耗的是否均匀,此外还可以通过选择让每一轮网络节点剩余能量均匀度达到最大的合 适参数将工作节点的最大额外有效覆盖时间和节点的剩余能量进行有效的结合,
本发明在满足预设网络寿命为常值的条件下,使得节点对关键点位置的总的有效覆盖时间最大的方 法,其中任务指定的完成时间被定义为无线传感器网络的预设网络寿命,此外,引用了文献《Distributed CriticalLocationCoverageinWirelessSensorNetworkswithLifetimeConstraint》里的一个定义,叫做有效覆 盖时间(简称覆盖值),以此量化节点对目标覆盖的质量,总的有效覆盖时间可以通过计算每个点位置的有 效覆盖时间的总和得出,即其中P表示点位置的指标集,wi表示点位置pi的重要性系数, 即为点位置的权值,Ti表示点位置的有效时间。
本发明通过比较每个节点的最大有效覆盖时间来挑选出最合适的节点参加工作,减少冗余的节点浪 费能量,使得实际的网络寿命大于预设的网络寿命。
本发明在指定的时间内,通过比较工作节点的最大有效覆盖时间和剩余能量来安排工作节点的最优 探测活动时间,从而使得总的有效覆盖时间最大,
数学模型如下:
ST:0≤si.start≤l,i∈N (2)
si.end-si.start=bi,i∈N (3)
其中C为总的有效覆盖时 间,l是每一轮的时间,bi是节点si在每一轮中的工作时间。
本发明具体包括以下步骤:
1:forii:1→L/l;
2:分别计算si最大额外有效覆盖时间和工作优先度,也即为:
3:向si的邻居广播mes(i,Null,UPD,ΔPi);
4:
5:ifsi在它的邻居中有最大的工作优先度ΔPithen;
6:si标记自己为LAB,并向邻居广播mes(i,LAB,sch,ΔPi),di=di-bi
,exits;
7:endif;
8:ifsi接收到邻居sk的信息包mes(k,LAB,sch,ΔPk)then;
9:则si更新邻居sk的信息,重新计算ΔPi并且向邻居广播mes(i,UPD,Null,ΔPi),Goto 4;
10:endif;
11:ifsi收到邻居sk的信息包mes(k,UPD,Null,ΔPk)then;
12:更新邻居sk的工作优先度,Goto4;
13:endif;
14:ifdi≤λi;
siexits.
15:endif;
16:endwhile;
17;endfor;
其中di为节点si的剩余能量,在每一轮的开始,节点的工作时间都是未安排的,也就是sch都为空, 在每一轮中都要重新选择新的合适的工作节点,确定工作节点最优的工作时间安排方案,而在每一个 While循环中(第4到16行),节点都要在自己的邻居内比较ΔP的大小,并更新自己和邻居的sch,当 所有的节点的ΔCmax都等于0时,则这一轮中的所有合适的工作节点都已经被选完,
本发明的输入:节点si的邻居N(si),自己和邻居的sch,自己覆盖的重要位置点Pi,位置的权值 wi,i∈Pi,预设网络寿命L,电池寿命Bi,si的标记类型为UPD;输出:si标记类型(LAB或UPD), 被标记为LAB的节点的最优工作时间安排;
本发明在算法的每一轮中,都会有一些局部最优的工作节点被选择,同时它们的工作时间安排方案 也被确定,其中,局部最优的工作节点即为在它们的邻居中拥有最高的工作优先度的节点,为了便于邻 居节点间相互通讯,它们之间相互传递的信息包应该包括本身的ID,自己的工作时间安排方案(sch),工 作优先度ΔP和它们的标记类型,标记类型为LAB或者是UPD,其中,LAB表示已被标记为最合适的工 作节点,UPD表示已更新自己的信息包,把这种信息包定义为mes(ID,sch,type,ΔP),此外,每个节点 都建立一个数据库存放自己和邻居的信息包。
和ΔCi的计算细节:
当节点si的工作时间安排方案被确定时,定义si额外有效覆盖时间为:其中 R(i)表示节点si覆盖的点位置集合,w(i)表示点位置pj的重要性系数,即pj的权值,表示点位置pj被节点si覆盖的额外时间。通过图2(b),和ΔC1和的演算过程为:其中时间 长度0.2为点位置p2被节点s1覆盖和已被节点s2覆盖的重叠时间,所以点位置p2被节点s1覆盖的额外时 间为0.4。此外,最大额外有效覆盖时间为:
ΔPi的计算细节:
结合每个节点的剩余能量重新定义每个节点si的工作优先度,
节点si的最大额外有效覆盖时间可通过上述方法来计算,因此在图2(a)中,可得此外,第n轮之后,三个节点的剩余能量分别为5,4和1,这里不妨设α=0.6, β=0.4,则ΔP1=3.44,ΔP2=4.12,ΔP3=2.56,显然,不管是通过最大额外有效覆盖时间还 是工作优先度ΔPi来比较,节点s2都是最大的,则这一轮中,节点s2被选择为工作节点,但是,如图2(b) 中显示,在第n+1轮中,虽然但是节点s3的剩余能量过低,导致ΔP3<ΔP1,所以这一轮 中,节点s1被选择为合适的工作节点,此外,为了保护长期进行工作的节点,设置了节点的电池剩余能 量安全阈值λi来检查工作节点在每一轮中的剩余能量是否过低,若工作节点si的剩余能量低于λi,则该 节点将被强制关闭它的探测功能,只是维持部分的通讯功能,假设λi都为1.5,则在第n+2轮中,s3将 不再被选为工作节点;
确定α和β:
在本发明中,节点剩余能量均匀度被用来度量每一轮中节点剩余能量的平均值和消耗的是否均匀, 通过该指标,可以选择合适的α和β将节点的最大额外有效覆盖时间和节点的剩余能量有效的结 合,这个问题用数学语言描述如下:
maxH
其中式子(5)中,Si.d表示第i轮中,所有节点的剩余能量,mean(Si.d)和var(Si.d)分别表示它 们的均值和方差,通过算法2来求解α和β,
将α的区间[0,1]平均分为四个子区间,统计1000次模拟中,min(mean(Si.d)/var(Si.d))最大的值 所对应α的区间的次数,显然,α处于[0.5,0.75]时被选为合适参数的次数最多,因此在模拟仿真中,以 α=0,64,β=0.36进行仿真。
通过以下的仿真实验对本发明的应用效果做补充说明:
算法性能评估,通过仿真实验,将改进后的算法和文献中的原来算法还有随机算法进行各种性能的 比较,下面先简要介绍一下原来的算法ECT和随机算法:
算法ECT:在文献《DistributedCriticalLocationCoverageinWirelessSensorNetworkswithLifetime Constraint》中ECT是针对节点对点位置的覆盖提出的一种分布式算法,它的目的是在满足网络寿命为常 值的基础上,研究如何使得总的有效覆盖时间最大,在每一轮里,ECT通过比较每个节点的最大额外有 效覆盖时间ΔCmax与他们邻居的大小,从中选出ΔCmax最大的节点进行监测工作;
随机算法:在这一算法中,网络寿命也按轮进行划分,并且在每一轮中节点被随机选择为合适的工 作节点,此外,工作节点的工作时间安排方案也被随机确定,然后在这一轮中非工作节点则进入休眠。
1仿真实验:
在本发明的仿真试验中,将重要位置点p随机分布在10×10的区域内,而传感器节点n被随机部署 在点位置的附近,在大多数的传感器平台中,传感器节点的通信半径至少是它的探测半径的两倍,因此, 将通信半径设置为2,探测半径设置为1,假设初始的电池能量是相同的,电池寿命与预设网络寿命之比 记为u,本论文进行的模拟仿真所需的参数具体见表1;
表1:仿真实验所需参数
本次试验的目的主要是分别计算改进ECT、ECT和随机算法的总有效覆盖时间、网络寿命、平均加 权事件探测率和网络节点剩余能量均匀度,通过Matlab软件将算法仿真1000次;
2仿真结果:
图3显示了在这三种算法中,总有效覆盖时间都随着传感器节点数目的增加而增大,在这三种算法 中,改进的算法ECT的性能大大的超过另两种算法所具有的性能,显而易见的是,改进ECT与ECT在 总有效覆盖时间上的差距随着节点的增加不断增大,在n=500时,达到了最大值,改进的ECT比原来算 法ECT超出了50%,可见,改进的算法比原先算法具有很大的优越性;
图4显示了在不同算法中节点数目对网络寿命的影响,在网络寿命这一性能当中,改进的ECT同样 表现出远超其他算法的优越性能,其中随机算法与原来算法ECT非常接近,但是这次随机算法表现的比 ECT好些;
如图5所示,当ECT的事件探测率随着节点的增加逐渐接近1的时,改进的ECT已大大的超出了 1,这表明了在改进的ECT中,传感器节点不仅完成了在预设网络寿命中的探测任务,而且还探测到了任 务规定时间以外更多的信息;
节点剩余能量均匀度体现了在每一轮当中,传感器节点耗能的均匀性,该值越高,则网络性能越好, 在图6中,显然改进的ECT比原先ECT具有更好的性能;
与图5比较可得,图7显示了事件探测率不仅与节点的数目有关,还与电池能量与预设网络寿命比 率有关,此外,图7还显示了在n=300前,改进的ECT与ECT非常接近,而当n超出300之后,改进的ECT 明显的大于ECT;
在图3-7中都显示了各种网络性能与节点数目的关系,而在图8中,可以看出三种算法的总有效覆盖 时间也都随着位置点数目的增大而增大,在这一性能中,改进的ECT再一次体现出了他的优越性;
图9显示了事件探测率和电池寿命与预设网络寿命的比率u之间的关系,在u=0.6时,改进的ECT 与原先ECT几乎相等,但随着u的增大,改进的ECT又渐渐的大于ECT。
本发明主要在预设网络寿命为常值的情况下,研究了无线传感器网络中节点对关键点位置的覆盖问 题和实际网络寿命,通过将节点的活动时间分成轮进行分析,将如何选择工作节点的工作时间安排方案 使得总的有效覆盖时间最大的问题公式化,并研究了如何使得实际的网络寿命大于预设网络寿命,从文 献《DistributedCriticalLocationCoverageinWirelessSensorNetworkswithLifetimeConstraint》分析中,得 知MAXECT问题是NP难问题,并就此提出了一个改进的分布式算法,通过大量的仿真实验,看到的改 进后的算法的性能比原来的算法和随机算法都大大提高了,且随着节点数目的增多,改进的ECT所得的 覆盖值越来越大,在稀疏网络中,改进的ECT比另两算法的网络寿命超出了20%,在稠密的网络中,改 进的ECT更是超出了70%,此外,改进的算法在节点能量下降均匀度这一性能中更是比原先的算法超 出了80%。
以上所述仅为本发明的较佳实施例而已,并不用以限制本发明,凡在本发明的精神和原则之内所作 的任何修改、等同替换和改进等,均应包含在本发明的保护范围之内。
机译: 一种将电子消息中继到无线网络覆盖范围之外的手持电子设备的方法
机译: 一种将电子消息中继到无线网络覆盖范围之外的手持电子设备的方法
机译: 一种检测分布式方法以处理来自传感器分布式光纤传感器的数据,该装置分布式光纤,装置,处理器以及计算机程序的方法。