2016, Vol. 27
2. 洛阳理工学院计算机与信息工程系, 河南洛阳 471023;
3. 广州大学计算机科学与教育软件学院, 广东广州 510006
2. Department of Computer and Information Engineering, Luoyang Institute of Technology, Luoyang 471023, China;
3. School of Computer Science and Software Engineering, Guangzhou University, Guangzhou 510006, China
随着新一代无线网络技术的迅猛发展,无线传感器网络(wireless sensor network)被广泛应用在各种工程领域,如军事国防、交通运输、医疗卫生、作业开采、抢险救灾、环境监测和智能楼宇以及工业控制领域等[1].其传感器节点特性主要体现在:具有一定的物理感知能力、通信能力、计算能力和存储能力,其动力来源主要依靠电池供电[2].对监测区域内部署大量的传感器节点,通过自组织方式完成对监测区域内数据信息的采集,对所采集的数据信息进行一定的处理之后,通过节点之间的多跳通信方式最终传给基站.
覆盖作为无线传感器网络重要环节,其覆盖的成功与否直接影响到覆盖率的优劣,并关系到无线传感器网络其他特性,如目标的定位、跟踪、数据的采集与处理等.对于工程领域中的一些实际问题,在满足一定的覆盖率的前提下,并不需要对整个监测区域进行完全覆盖,而只对所关注的目标节点进行有效覆盖,即可达到一定的预期效果.传感器节点能量是无线传感器网络工作动力的主要来源.在无线传感器网络中,传感器节点能量非常有限[3].当传感器节点工作在复杂环境中时,传感器节点电池无法进行更换,一旦大量的传感器节点能量耗尽,就意味着整个无线传感器网络处于瘫痪状态.因此,为使无线传感器网络生存周期最大化,抑制传感器节点能量快速消耗,已成为无线传感器网络研究领域的另一个重要课题.上述研究的两个重点问题主要体现在:
第一,能量消耗方面.为了减少传感器节点能量的消耗,提高网络生存周期.在监测区域内,按照目标节点所行进的轨迹,通过节点调度策略开启相邻传感器节点加以对目标节点的覆盖.当目标节点移出传感器节点感知半径之外时,将其传感器节点处于关闭或休眠状态,抑制传感器节点能量快速消耗,提高网络生存周期[4, 5].
第二,有效覆盖方面.减少冗余数据的产生,提高对监测区域的有效覆盖.如果监测区域内的传感器节点全部为开启状态,虽然能够达到完全覆盖的目的,但也会产生大量的冗余数据,加大了传感器节点能量的开销.这些冗余数据对通信信道而言必会产生拥塞现象,传感器节点计算能力大幅下降的同时也会产生大量的误码,对最终所采集的数据造成较大的误差;有效覆盖不仅可以提高对目标节点覆盖质量,而且还可以最大限度延长网络生存周期.
第三,资源优化配置.减少参数的选择,提高优化配置.一个良好的无线传感器网络运行状态主要表示在资源合理配置和节点高效部署以及路由协议的选择.资源优化配置不仅体现在网络资源的合理性优化,更重要的是,用户可以根据不同需求选择不同的覆盖质量.在实际应用过程中,传感器节点的感知范围往往与自身物理特性和环境物理参数相关.因此,合理地优化网络资源可以达到抑制节点能量快速消耗、延长网络生存网络的 目的.
第四,拓扑结构方面.为了提高无线传感器网络的扩展性,应通过某种关联关系让其他网络体系结构嵌入到原网络体系结构之中,如分簇结构.通过嵌入网络体系结构形成的分簇簇首节点与原网络体系结构某簇首节点相连,并保证在通信半径大于等于两倍的感知半径下连通.这主要体现在网络拓扑结构.
综合上述4种情况,评价一个网络体系的优劣主要取决于对监测区域的节点能量消耗方面、对目标节点有效覆盖以及对网络资源的优化配置和无线传感器网络进一步扩充的拓扑结构方面.
在满足一定覆盖率的前提下,如何使用最少的节点完成对监测区域的有效覆盖,如何通过某种策略让节点之间进行合理配置以及通过何种算法减少节点之间的不必要的连通延长网络生存周期,是目前无线传感器网络研究的重点所在.因此,覆盖率在一定意义上来说是衡量网络服务的一个重要标准.为此,本文从以下4个方面对覆盖率进行分析与研究:
(1) 对国内外文献做了重点分析,指出了文献中对监测区域进行各种覆盖的优缺点,提出了本文算法的中心思想.
(2) 构建无线传感器网络覆盖网络模型.针对网络模型,利用概率相关知识证明了覆盖率与覆盖期望之间的比例关系,进而计算出对所需监测区域覆盖最少传感器节点数量;在计算过程中,本文也给出对于两级监测区域的覆盖期望值与方差的证明过程;当多个目标节点成为关注目标节点时,本文也给出了覆盖多目标时,产生的偏离误差的计算方法.
(3) 在抑制节点能量消耗方面,本文引入节点控制调度策略对通信路径进行优化,减少了一些不必要节点之间的连通过程,以达到延长网络生存周期的目的;对监测区域而言,证明了节点能量衰减、极限存在的意义.
(4) 本文最后通过仿真实验,给出了不同参数下的覆盖率和网络生存周期变化曲线,并与其他文献算法相对比,验证了本文算法的有效性.
本文主要通过概率相关知识研究了随机部署在监测区域内传感器节点覆盖问题.通过对网络体系性能指标的计算与证明,给出覆盖期望值和方差求解过程以及对首次完成覆盖时的数学期望的证明过程.在仿真实验环节中,采用本文算法OCPM与其他两种算法进行比对实验.就相同覆盖率而言,通过对参数的动态调节,最终达到了本文算法所需节点数量小于其他两种算法的节点数量,验证了本文算法可用较少的传感器节点数量完成对监测区域的有效覆盖.从而实现了抑制节点能量的快速消耗,达到延长网络生存周期的目的.
1 预备知识近些年,国内外许多专家对无线传感器网络各种特性做了大量细致而深入的研究.文献[6]提出了一种保持连通覆盖算法.该算法利用相对邻接图和节点自身部署特性给出传感器节点移动部署过程中保持网络连通与覆盖.该算法实现了选择任意移动方向上的传感器节点所形成的拓扑结构均保持了网络连通,对移动目标节点的覆盖特性主要取决于网络连通的约束条件.该算法虽然在一定程度上可以保持网络的连通覆盖性,但覆盖有效区域主要体现在局部性.对于全局而言,当目标节点积累到一定数量时,其覆盖率会显现明显的逐渐下降趋势,该算法具有的一定的局限性.文献[7]提出了集中式群集 K覆盖配置协议,该文献利用构建的网络模型对覆盖协议进行分析,并给出了4种 K覆盖配置协议,分别是Centralized Randomized Connected K-Coverage(CERAC C k), T-Clustered Randomized Connected K-Coverage(T-CRACC k),D-Clustered Randomized Connected K-Coverage (D-CRACC k)和Distributed randomized Connected K-Coverage(DIRACC k).该文献证明:当 K≥3时,覆盖后的网络模型所形成的鲁洛三角边长为感知半径 r时,至少需要 K个传感器节点;并给定了完成 K覆盖时通信半径与感知半径的比较关系,同时也给出了完成所覆盖区域的最少传感器节点数量的计算过程及监测区域内所需传感器节点密度的计算公式.该研究成果虽然达到了使用最少传感器节点对监测区域内目标节点的有效覆盖,但算法复杂度较高,计算量大,对传感器节点的部署条件比较苛刻.文献[8]提出了网络生存周期最大化的 K度离散障碍覆盖算法,该算法从理论层面上分析了具体障碍的网络模型覆盖率上限与下限存在的条件,对所关注的移动目标节点完成了有效的覆盖;在网络能耗方面,给出了一种传感器节点调度算法,该算法引入贪婪算法对传感器节点重新部署,利用传感器节点之间的调度机制完成了传感器节点之间的状态转换,最终达到对网络生命周期最大化的目的.该算法在对所关注的移动目标节点覆盖时,需保证分布在监测区域的传感器节点始终保持相连或相交,一旦移动目标节点出现在覆盖“盲区”时,就无法完成对移动目标节点的有效覆盖,网络模型过于理想化.文献[9]通过混合整数规划方式给出了一种启发式覆盖算法,该算法研究了传感器节点集合相交与传感器节点感知半径可调的启发式覆盖.该算法计算量较大,可调性较差.为了进一步改进文献[9]的算法,Yang[10]将文献[9]中的目标节点覆盖区域近似看作监测区域,利用高密度部署传感器节点构建覆盖集合,完成对目标覆盖区的连通覆盖.在上述两个文献研究的基础上,Liu等人[11]对目标覆盖问题做了大量的研究工作,在限定了一个传感器节点只能覆盖一个目标节点的条件下,给出了在任意时刻目标节点覆盖率的求解过程.由于有了限定条件,使得对监测区域的覆盖应用范围较为狭隘,并不适用于实际覆盖场景.文献[12]通过人工蜂群算法和粒子群算法对传感器节点调度问题进行了优化,通过启发式调度配置找出了最佳部署路径,给出了最佳部署后传感器节点位置理论上的计算过程及网络生存周期上限的计算方法.文献[13]提出一种能量高效保持连通覆盖路由算法——An Energy-Efficient Coverage and Connectivity Preserving Routing Algorithm(ECCRA),该算法利用网络模型构建出二重覆盖区域,通过概率相关知识计算覆盖概率值与覆盖期望值,最终确定所覆盖期望值的上限及对完成监测区域有效覆盖的最少传感器节点数量.文献[12]和文献[13]能够在一定程度上都完成对监测区域的有效覆盖,抑制了传感器节点能量的快速消耗,但两种算法的计算较大,算法复杂度较高,节点对监测区域完成覆盖的时间较长.在国内,清华信息科学与技术国家实验室物联网技术中心的“GreenOrbs”研究工作团队对无线传感器网络在工程方面的应用也做了大量的研究性实验,并取得一定的成绩, 其主要体现在林业生态监测和城市环境监测等方面.“GreenOrbs”研究工作团队经过两年多的研究,组建了“CitySee”项目,是将传感器网络应用于城市与社区中碳吸收与排放的监测,为政府决策和城市的发展奠定有力的技术支持与社会保障.同时,项目研究团队也发表了多篇具有代表性的高质量论文.文献[14]以大规模传感器节点部署在森林区域作为研究对象,给出了网络体系中不同层次之间的从属关系.对于网络底层而言,给出了广播信号强度对物理层的影响;在链路层,主要研究了丢包率与链接质量以及传输速率对整个网络体系结构的影响;对于网络上层而言,主要研究了路由动态规划、流量控制以及节点之间的分组、数据交换和拓扑特性等.文献[15]以大规模传感器节点部署在城市中心,以监测二氧化碳的各种性能指标.该文从网络体系着手,介绍了各层之间的作用;而后,对网络体系的软件和硬件配置进行分析与说明;最后,对网络连通性和数据采集做了大量的实验与验证,其中包括了对所采集数据可视化处理和无线传感器网络设计与管理以及移动网络与定位等多个层次结构.上述大规模传感器网络在实际工程中具有较高的应用价值.
本文以概率模型作为研究背景,给出了传感器节点覆盖期望值的计算方法,并对传感器节点之间的概率关系给出了相应的证明过程,同时还给出了对传感器节点能耗衰减后节点覆盖期望理论的证明.在节点能耗方面,本文引入了节点能量调度策略,对节点之间的通信路径进行优化,其目的在于减少节点之间一些不必要的网络连通,以提高整个网络的工作时间,进而达到延长网络生命周期的目的.最后通过仿真实验,验证了本文所给出的OCPM算法的有效性和稳定性.
2 定义与网络模型为了更好地研究无线传感器网络覆盖问题,本文OCPM算法基于以下4种假设:
(1) 传感器节点感知半径与通信半径均显现圆盘形;
(2) 传感器节点通信半径是感知半径的两倍,并保证监测区域内所有节点保持连通;
(3) 传感器节点的感知范围要远小于覆盖区域,每个传感器节点的初始能量均相等,且时钟同步;
(4) 传感器节点的位置信息可以通过某种定位算法获取,如RSSI(received signal strength indication)定位算法.
2.1 基本定义定义 1(覆盖率). 随机部署在监测区域内的全部传感器节点的覆盖面积与监测区域的总面积之比,称为覆盖率.
| \[P(S,\Omega )={\sum\limits_{i=1}^{n}{{{s}_{i}}}}/{A(\Omega )}\;\] | (1) |
其中, n表示传感器节点数量, si表示每个传感器节点的覆盖面积, A( Ω)表示监测区域面积.
定义 2( K度覆盖). 在二维监测区域内,任意目标节点被 K个传感器节点所覆盖(或感知),称为 K度覆盖.
定义 3(有效覆盖面积). 当完成 K度覆盖后,其传感器节点面积与 K度覆盖面积之差,称为有效覆盖面积.
| \[{S_{ec}} = \sum\limits_{i = 1}^n {({s_i} - {s_{kc}})} \] | (2) |
其中, si表示每个传感器节点的覆盖面积, skc表示 K度覆盖面积.
定义 4(有效覆盖率). 有效覆盖面积与监测区域的比值,称为有效覆盖率.
| \[{{P}_{ec}}={\sum\limits_{i=1}^{n}{({{s}_{i}}-{{s}_{kc}})}}/{A(\Omega )}\;={{{S}_{ec}}}/{A(\Omega )}\;\] | (3) |
定理 1. 四圆无缝对接时,有效覆盖面积最大值为 Se=8r2.
证明:如图1所示,该图是四圆进行无缝对接的中间过程.由于四圆与时钟同步,且向空洞中心移动的速度相等,当4个传感器节点进行同步移动时,空洞的面积会随之减小.
|
图1 四圆无缝对接 Fig.1 Among four round seamless docking |
设 FE= m,则 AB=2 r- m, r是传感器节点感知半径,由四圆圆心所构成的正方形面积 S1=(2 r- m)2,以扇形 SADEA为研究对象,其中, SCDEC面积等于扇形 SADEA与三角形 SADC面积之差.令$\angle $FAD= θ,经计算可得, SCDEC= ( r2 θ- rsin θ( r- m/2))/2,即 SFDEF= r2 θ- rsin θ( r- m/2),空洞面积 S2等于正方形面积减去单位圆盘面积与重叠4倍 SFDEF之和,即 S2=(2 r- m)2-p r2+4( r2 θ- rsin θ( r- m/2)).经化简后,得到关于 m的一元二次方程:
| \[{S_2} = {m^2} - (4r - 2rsinq)m + 4{r^2} - p{r^2} + 4{r^2}q - 4{r^2}sinq\] | (4) |
求解上述方程可得:当 θ=π/4,$m = 2r - \sqrt 2 r$时, S2其值为0.有效覆盖面积 Se=4(πr2-4 SFDEF),即
| \[{S_e} = 4\left( {\pi {r^2} - 4\left( {{r^2}\theta - r\sin \theta \left( {r - \frac{m}{2}} \right)} \right)} \right)\] | (5) |
将 θ=π/4,$m = 2r - \sqrt 2 r$代入公式(5)可得: Se=8 r2.
2.2 网络模型本文从研究问题特性的角度出发,以多重正方形监测区域为研究对象.设有两个传感器节点并满足定理1相邻节点之间的关系属性,同时将正方形区域划分为3个部分,分别为重点关注监测区域Ⅰ、关注监测区域Ⅱ和非关注监测区域Ⅲ,如图2所示.在图2中,区域Ⅰ是重点关注区域;区域Ⅱ是关注区域,是夹在区域Ⅰ和区域Ⅲ之间的部分;区域Ⅲ是非关注区域,是外包在区域Ⅱ部分.其三者之间的关注程度依次递减.区域Ⅰ的边长为 l,区域Ⅱ的边长 l+ r,区域Ⅲ边长为 l+2 r,相交的两个传感器节点与区域Ⅱ相交点分别为 A, B, C, D,两圆盘相交的交点为 E.
|
图2 网络覆盖模型 Fig.2 Network coverage model |
定义 5(冗余覆盖率). 任意给定传感器节点 si,该节点工作时所感知的范围与监测区域重叠部分的面积占其整个监测面积的比值,称为该节点 si冗余覆盖率; si称为冗余覆盖节点.
定理 2. 不失一般性,传感器节点 si的冗余覆盖节点为 n,其冗余覆盖率至少要满足:
| \[P(n) = 1 - {\left\{ {1 - \frac{1}{\pi }\left[ {\frac{\pi }{4} - \frac{{k\sqrt {4 - {k^2}} }}{8} + \frac{{{k^2}}}{2}\arccos \left( {\frac{k}{2}} \right) - \frac{{{k^3}\sqrt {4 - {k^2}} }}{{16}}} \right]} \right\}^n}.\] |
证明:以图2为例加以证明.根据均匀分布性质可知,传感器节点 Si的 n个冗余邻居节点所显示的分布状态也服从均匀分布.由定理1可知:当有效面积达到最大值时,其冗余覆盖率才会到达最大值.由假设条件可知:传感器节点均为同质节点,通信半径 R与感知半径 r的比例关系为 R= kr, k是比例系数.设$\angle $BCE= α,点 B与点 C之间的距离 L为随机变量,由概率密度函数可知:
| \[{f_L}(x) = \frac{{2x}}{{{k^2}{r^2}}},0 \leqslant x \leqslant kr\] | (6) |
两圆盘相交区域的面积 S1表示为
| \[{S_1} = (2a - sin2a){r^2}\] | (7) |
令 BC之间的距离 l=2 rcos α,d l=2 rsin αd α,其中,$\alpha \in \left[ {\arccos \frac{k}{2},\frac{\pi }{2}} \right]$,代入概率公式,化简可得:
| \[{P_a} = \int_{{\text{ }}\frac{k}{2}}^{{\text{ }}\arccos \frac{k}{2}} {(2\alpha - \sin 2\alpha )} \frac{{4{r^2}\cos \alpha }}{{{k^2}}}\sin \alpha {\text{d}}\alpha = \frac{1}{\pi }\left[ {\frac{\pi }{4} - \frac{{k\sqrt {4 - {k^2}} }}{8} + \frac{{{k^2}}}{2}\arccos \left( {\frac{k}{2}} \right) - \frac{{{k^3}\sqrt {4 - {k^2}} }}{{16}}} \right]{r^2}\] | (8) |
由公式(8)可知,对于任意一个传感器节点覆盖冗余邻居节点而言,其冗余覆盖率可表示为
\[{P_b} = \frac{{{P_a}}}{{\pi {r^2}}} = \frac{1}{{{\pi ^2}}}\left[ {\frac{\pi }{4} - \frac{{k\sqrt {4 - {k^2}} }}{8} + \frac{{{k^2}}}{2}\arccos \left( {\frac{k}{2}} \right) - \frac{{{k^3}\sqrt {4 - {k^2}} }}{{16}}} \right]\]
(9)
\[P(n) = 1 - {\left\{ {1 - \frac{1}{\pi }\left[ {\frac{\pi }{4} - \frac{{k\sqrt {4 - {k^2}} }}{8} + \frac{{{k^2}}}{2}\arccos \left( {\frac{k}{2}} \right) - \frac{{{k^3}\sqrt {4 - {k^2}} }}{{16}}} \right]} \right\}^n}\]
(10)
证毕.
推论 1. 以三重正方形区域为研究对象,其重点关注区域的数学期望为 E( X)= np1,方差 D( X)= np1(1- p1);关注目标区域的 E( Y)= np2,方差 D( Y)= np2(1- p2). p1和 p2分别是监测区域Ⅰ和监测区域Ⅱ的覆盖率.
证明:以图2为研究对象加以证明.对整个目标覆盖区域而言,设有 n个传感器节点对其进行有效覆盖,其中,监测区域Ⅰ被 k个传感器节点所覆盖,监测区域Ⅱ被 s个传感器节点所覆盖,监测区域Ⅲ的传感器节点数量为 n- k- s.由题意可知,由于3个监测区域彼此之间相互独立,即,非关注监测区域Ⅲ的覆盖率为 p3=1- p1- p2.由 p1和 p2所覆盖监测区域的数量组成了离散型随机变量系为( X, Y),其覆盖率表示为
| \[P\{ X = k,Y = s\} = \frac{{n!}}{{k!s!(n - k - s)!}}p_1^kp_2^sp_3^{n - k - s}\] | (11) |
对于 p1而言,其覆盖率的期望值为
| \[\begin{gathered} E(X) = \sum\limits_{k = 0}^n {\sum\limits_{s = 0}^n {k\frac{{n!}}{{k!s!(n - k - s)!}}p_1^kp_2^sp_3^{n - k - s}} } \hfill \\ {\text{ }} = {p_1}\frac{\partial }{{\partial {p_1}}}{\left. {\left\{ {k\frac{{n!}}{{k!s!(n - k - s)!}}p_1^kp_2^sp_3^{n - k - s}} \right\}} \right|_{{p_1} + {p_2} + {p_3} = 1}} \hfill \\ {\text{ }} = n{p_1}{({p_1} + {p_2} + {p_3})^{n - 1}}{|_{{p_1} + {p_2} + {p_3} = 1}} \hfill \\ {\text{ }} = n{p_1} \hfill \\ \end{gathered} \] | (12) |
其公差为 D( X)为
| \[\begin{gathered} D(X) = \sum\limits_{k = 0}^n {\sum\limits_{s = 0}^n {{k^2}\frac{{n!}}{{k!s!(n - k - s)!}}p_1^kp_2^sp_3^{n - k - s} - E} } {(X)^2} \hfill \\ {\text{ }} = {p_1}\frac{\partial }{{\partial {p_1}}}\{ n{p_1}{({p_1} + {p_2} + {p_3})^{n - 1}}\} {|_{{p_1} + {p_2} + {p_3} = 1}} - {(n{p_1})^2} \hfill \\ {\text{ }} = n{p_1}{({p_1} + {p_2} + {p_3})^{^{n - 1}}}{|_{{p_1} + {p_2} + {p_3} = 1}} + n(n - 1)p_1^2{({p_1} + {p_2} + {p_3})^{n - 2}}{|_{{p_1} + {p_2} + {p_3} = 1}} - {(n{p_1})^2} \hfill \\ {\text{ }} = n{p_1}(1 - {p_1}) \hfill \\ \end{gathered} \] | (13) |
同理可求得 E( Y)= np2,方差 D( Y)= np2(1- p2).
3 覆盖质量与算法实现 3.1 网络覆盖质量的分析对监测区域覆盖过程中,在满足一定覆盖率的前提下,为进一步提高覆盖质量、减少网络能量的消耗、最大限度延长网络的生存周期[16, 17],在监测区域内,应对传感器节点工作进行有效地调度.所关注的目标一旦进入覆盖盲区,就会使覆盖过程失败.为了避免盲区的产生,同时要达到使用最少传感器节点数量完成覆盖的最大面积,即,在监测区域内,并不是对整个区域进行实时监测,只要对所关注的目标节点进行覆盖即可.当多个节点同时工作,并且任何两个节点之间的欧拉距离均小于或等于感知半径时,就会产生冗余节点.这样,只能通过节点调度机制关闭一些冗余节点,当再次唤醒时冗余节点时,冗余节点覆盖率须满足一定条件才可完成对目标节点的覆盖.也就是说:当冗余节点转化为工作节点时,如果冗余节点的覆盖率没有达到覆盖率的最小值时,该冗余节点转化为休眠状态.在监测区域内对传感器节点各种状态进行某种算法调度,以达到节省传感器节点能量,进而提高网络生存周期的目的[18, 19].对于在监测区域内的目标节点而言,由于目标节点的随机移动,就会使得某个传感器节点多次对某个目标节点进行覆盖,其首次完成对目标节点覆盖期望值的大小,取决于其覆盖率与目标转移的次数的比例关系.
推论 2. 在某监测区域内,设传感器节点覆盖率为 p,完成对目标节点首次覆盖后,其首次覆盖期望值是 E( X)=[1-(1- p) N] p-1, N是目标节点转移的次数.
证明:设 X是传感器节点首次完成对目标节点覆盖时目标节点转移的次数,则 X的可能取值范围是 X$ \in $[1,2,3,…, N].当 X= k时,且1≤ k≤ N-1表示前 N-1并没有覆盖目标节点,故 X的分布密度函数为
| \[P(X = k) = \left\{ {\begin{array}{*{20}{l}} {p{{(1 - p)}^{k - 1}},{\text{ }}k = 1,2,3,...,N - 1} \\ {{{(1 - p)}^{N - 1}},{\text{ }}k = N} \end{array}} \right.\] | (14) |
根据期望值定义可知,
| \[E(X) = \sum\limits_{k = 1}^{N - 1} {kp{{(1 - p)}^{k - 1}}} + N{(1 - p)^{N - 1}}\] | (15) |
令 q=1- p,$S = \sum\limits_{k = 1}^{N - 1} {k{{(1 - p)}^{k - 1}}} $,即$S = \sum\limits_{k = 1}^{N - 1} {k{q^{k - 1}}} $在左式两端乘以 q,可得$qS = \sum\limits_{k = 1}^{N - 1} {k{q^k}} $,即
| \[S = \frac{{1 - {q^{N - 1}}}}{{{{(1 - q)}^2}}} - \frac{{(N - 1){q^{N - 1}}}}{{1 - q}} = \frac{{1 - {{(1 - p)}^N}}}{{{p^2}}} - \frac{{N{{(1 - p)}^{N - 1}}}}{p}\] | (16) |
将公式(16)代入公式(15)可得:
| (17) |
即 E( X)=[1-(1- p) N] p-1.
某监测区域内工作的传感器节点通过时间 t覆盖后,其自身能量必然具有一定消耗.由于传感器节点自身能量的消耗,使其覆盖的面积也发生了变化.为了加强对所关注的目标节点的有效覆盖,在传感器节点能量消耗过程中,使得节点能量消耗后的覆盖面积所组成的序列集合不小于整个监测区域的面积,就可以完成对整个监测区域的有效覆盖,即完成了对关注目标节点的有效覆盖.
定理 3. 在二维平面内,设传感器节点能量消耗的拟合函数为 f( x, y),其能量衰减后所覆盖区域的面积为 Sn,其中, n$ \in $[1,2,3,…, N],所构成的有界闭域可以覆盖整个监测区域,即$\iint\limits_S {f(x,y){\text{d}}x{\text{d}}y = \mathop {\lim }\limits_{x \to \infty } \iint\limits_{{S_n}} {f(x,y){\text{d}}x{\text{d}}y}}.$
证明:任取有界闭域序列${S'_n}$,且该序列${S'_n}$覆盖整个监测区域,设${S'_1} \subset {S'_2} \subset {S'_3} \subset ... \subset {S'_n} \subset ... \subset S,$由于能量衰减函数为非负函数,故积分序列$\iint\limits_{{{S'}_n}} {f(x,y){\text{d}}x{\text{d}}y}$是呈现递增,设极限:
| \[I = \mathop {\lim }\limits_{x \to \infty } \iint\limits_{{{S'}_n}} {f(x,y){\text{d}}x{\text{d}}y}\] | (18) |
因此,只要证明:
| \[\mathop {\lim }\limits_{x \to \infty } \iint\limits_{{S_n}} {f(x,y){\text{d}}x{\text{d}}y} = I\] | (19) |
因数 I是有限数集,任给 e>0,由公式(18)可知:存在 N,使得当 n≥ N时,恒有:
| \[I - \varepsilon < \mathop {\lim }\limits_{x \to \infty } \iint\limits_{{{S'}_n}} {f(x,y){\text{d}}x{\text{d}}y} < I + \varepsilon \] | (20) |
设:存在一个 n0,当 n≥ n0时,${S_n} \supset {S'_n}$.从而,根据 f( x, y)的非负性和公式(20)可知,
| \[\iint\limits_S {f(x,y){\text{d}}x{\text{d}}y \geqslant \mathop {\lim }\limits_{x \to \infty } \iint\limits_{{{S'}_n}} {f(x,y){\text{d}}x{\text{d}}y}} > I - \varepsilon \] | (21) |
另一方面,对每个固定的 n≥ n0,又必然存在某个数值趋于无穷大,设为 kn,使${S'_{{k_n}}} \supset {S_n},$再由公式(20)可得:
| (22) |
即,当 n≥ n0时,恒有:
| \[I - \varepsilon < \mathop {\lim }\limits_{x \to \infty } \iint\limits_{{S_n}} {f(x,y){\text{d}}x{\text{d}}y} < I + \varepsilon \] | (23) |
故,公式(19)成立.
再设: I=+∞,任意给定 M>0,由公式(18)可知:存在 N1,使得:
| \[\iint\limits_{{{S'}_{{N_1}}}} {f(x,y){\text{d}}x{\text{d}}y} > M\] | (24) |
又存在 n1,当 n≥ n1时,恒有${S_n} \supset {S'_{{N_1}}}$,至此,
\[\iint\limits_S {f(x,y){\text{d}}x{\text{d}}y \geqslant \iint\limits_{{{S'}_{{N_1}}}} {f(x,y){\text{d}}x{\text{d}}y} > M}\]
(25)
OCPM算法以网络运行时间轮数作为基本单位,每轮包含有覆盖控制信息与节点状态稳定信息两个方面:在工作阶段,工作节点始终保持开启状态,所有冗余节点均处于关闭状态,以节省网络能量;在状态稳定阶段,每个节点共有5种运行状态,分别是判断、竞争、等待、启动和休眠这5种状态.
· 判断状态:在每一个时间轮开始时,节点处于判断状态.当节点满足冗余判断条件时,进入休眠状态;如果不满足条件,则进入竞争状态.
· 竞争状态:在节点处于竞争启动时,成功的节点可以进入到工作状态,不成功的节点则进入等待状态.
· 等待状态:竞争失败的节点转入等待状态,当其在初始时间内成功接收到领居节点发送的on-duty后,更新节点自身在本地信息后,转入判断状态.
· 启动状态:节点竞争成功时,转入启动状态.通过对节点覆盖率的计算,判断其感知区域处于启动状态的节点是否满足覆盖要求,若不满足,则发送on-duty消息调度,随后转入到判断状态.
· 休眠状态:在满足冗余判断条件时转入休眠状态,以节省节点能量的开销.在单位时间轮数下,节点轮为判断状态.
这5种状态之间的转换关系如图3所示.当某一监测区域的节点密度过大时,该区域的绝大多数节点都将满足冗余节点判断条件,此时,这些节点都会进入休眠状态.这种状态虽然能够抑制节点能量的消耗,但也存在着一定的不足.其原因在于:所感知邻居节点一旦进入休眠状态会造成监测区域内大量的覆盖盲区,从而降低覆盖质量[20, 21, 22].为了避免这种情况的发生,OCPM算法采用某节点一旦处于休眠状态时,马上唤醒其邻居节点,并让邻居节点处于等待状态.这样做的目的在于:首先,降低可能工作节点的密度,即,直接选举某个节点作为候选工作节点,剩下没有被选上的节点直接进入睡眠状态;然后,再在某个候选工作节点中进行冗余节点调度,每个候选节点以概率 P选举自己进入预工作状态,没有选举成功的候选节点则进入预睡眠状态.图3给出了覆盖控制阶段的节点调度关系.
|
图3 节点状态转换 Fig.3 State transition of nodes |
1. Input N, R, r, ε
2. Initialize the number of nodes,communication radius and perception radius,threshold value
3. for i=1 to N do
4. if coverage possibility exists then
5. determine coverage and computer coverage rate //determine the coverage area
6. state_ transition( nodes) //nodes state transition function
7. else
8. break
9. end if
10. end for
11. state_ transition( nodes)
12. while ( node energy> e)
13. state= wait
14. If random(0,1)>= p then
15. compete= state
16. work= compete //meet the conditions of coverage,activate the work nodes
17. else
18. wait= compete
19. end if
20. start timer Tn // Tn is next time
21. if ( d< r1 && d< r2) then
22. state= sleep //target nods is the neighbor nodes within the overlapping range
23. else if ( random(0,1)>= p)
24. compete= state
25. work= compete //meet the conditions of coverage,activate the work nodes
26. else
27. wait= state
28. end if
29. end if
30. end while
4 体系评估为了更好地验证本文算法的有效性和稳定性,使用MATLAB7.0作为仿真平台对本文算法进行实验与分析,所采用的计算机配置是:操作系统WINXP,INTEL双核1.7GHZ CPU,内存2G;仿真实验是将每个传感器节点以 r为半径随机部署在监测区域内,每个传感器节点的初始能量相同,为2J, d为通信模型与通信邻居节点的距离.发送与接收数据通信模型分别为
| \[{E_{Tr}}(k,d) = {E_{T{\text{ - }}elec}}k + {E_{amp}}(k,d) = \left\{ {\begin{array}{*{20}{l}} {{E_{T{\text{ - }}elec}}k + {\varepsilon _{fs}}{d^2}k,{\text{ }}d < {d_0}} \\ {{E_{T{\text{ - }}elec}}k + {\varepsilon _{amp}}{d^4}k,{\text{ }}d \geqslant {d_0}} \end{array}} \right.\] | (26) |
接收端能量消耗模型为
| \[{E_{Rx}}\left( l \right) = {E_R}_{ - elec}\left( l \right) = l{E_{elec}}\] | (27) |
其中, ET- elec和 ER- elec表示无线发送和接收模型的能耗, efs和 eamp分别表示自由空间模型和多路衰减模型的放大器能耗参数, d0表示通信节点之间距离门限值或称为比例纲量, k表示为通信节点距离 d上的节点数,节点发送和接收数据时能量衰减指数分别为2和4.其仿真参数见表1.
|
表1 仿真参数列表 Table 1 Simulation parameter list |
实验1. 在不同的监测区域内随机部署节点,通过传感器节点调度策略对通信路径进行优化,以减少传感器节点能量消耗,如图4所示.
图4给出了不同监测区域内传感器节点的初始状态分布以及对传感器节点通信路径优化后的状态示意图.以300x300m2为例,从图4中可以看出,在初始时刻,随机分布260个传感器节点,并构成了大量的通信路径,由于具有大量通信路径的存在,使得传感器节点能量出现过快消耗.在单位时间内,当传感节点能量大于等于能量阈值 e时,通过本文的OCPM算法可知:传感器节点本身所获得的覆盖率小于 P的节点转入等待状态;当节点本身所获得的覆盖率大于或等于 P时,则节点将转入竞争状态.一旦竞争成功,则该节点成为启动节点,并进入工作状态.当传感器节点感知某目标节点后,便唤醒其邻居节点,同时继续判断所唤醒节点是否以一个概率 P选举自己作为工作节点:如果获取的概率率大于或等于 P,则经竞争状态后进入工作状态;否则,由判断状态转为等待状态.经过多个单位周期时间后,随机部署的节点能量均达到平衡,此时,工作的传感器节点为数量为188,占总数量的72.3%.如果传感节点能量小于能量阈值 e,就说明该节点处于“死亡”状态,不会转入任何一个调度状态.其目的在于抑制大量传感节点能量的过快消耗,提高了网络生存周期,同时也保证了任意传感器节点之间通信链路的畅通[23].
|
图4 不同监测环境下随机部署优化 Fig.4 Random deployment optimization under different monitoring environment |
实验2. 以300x300m2监测区域作为研究对象,给出了在相同 k值下和不同覆盖率(coverage probability,简称CP)下,工作节点与传感器节点数量之间的比较关系,如图5所示.
|
图5 不同参数下网络覆盖率对比 Fig.5 Comparison of network coverage probability under different parameters |
图5给出了在相同 k值情况下,对于不同覆盖率(coverage probability,简称CP)的4种工作节点占总传感器节点数量的变化曲线.在图5(a)和图5(b)中,初始时刻,总传感器节点数在200~300之间时,4条曲线的上升速度较快,其主要原因是因为 k较小,所需要传感器工作节点数量较多,此时尚未达到99.9%的覆盖率;当大于350时,4条曲线趋于平稳.在同一个 k情况下,对于覆盖率较高的曲线来说,所需要较多的工作节点,所以覆盖率较高的曲线位于上端,而覆盖率较低的曲线位于下端.在图5(c)和图5(d)中,4条曲线基本上趋于平稳,主要是原因 k值相对于上述两种情况取值较大,并且对覆盖率低的曲线来说,工作节点数量基本保持在180至240之间,对于覆盖率较高的曲线来说,工作节点数量基本保持在220~240之间,说明本文的OCPM算法具有一定的扩展性.就总体而言,图5(c)和图5(d)的覆盖速度要高于图5(a)和图5(b);对于同一覆盖率而言,图5(c)和图5(d)所需的工作数量要小于图5(a)和图5(b),验证了本文OCPM算法的有效性.图5(e)和图5(f)反映了不同 k值参数在200x200m2和300x300m2的不同监测区域内与(square region-based coverage and connectivity probability,简称SCCP)[24]和(coverage configuration protocols,简称CCP)[25]这两种算法的覆盖率对比示意图.在图5(e)中,可以看到,SCCP和CCP覆盖率变化曲线位于 k=1.4和 k=1.6之间,这说明:当 k≤1.4时,所需要传感器工作节点数量略多于SCCP算法和CCP算法;当 k≥1.6时,所需传感器工作节点数量小于SCCP算法和CCP算法,其主要原因是:由于冗余节点数量的减少,导致了覆盖监测区域所需的工作节点数量较少,而参数 k的变化对传感器工作节点数量变化的影响并不是很大,但对于取值较大的参数 k来说,所需传感器节点的数量低于SCCP算法和CCP算法就可以达到对监测区域的有效覆盖.随着监测区域面积的增加,参数 k的作用对传感器工作数量的影响比较大,如图5(f)所示.可以看出,随着监测区域的增加,传感器工作节点的数量也是随之增加,但SCCP算法所需的传感器工作节点数量明显超过了 k=1.6时的传感器工作节点数量,说明了参数 k的值在较大的监测范围内对传感器工作节点数量的影响是比较大的,这进一步验证了本文的OCPM算法在不同的参数 k值作用下覆盖性能的增强性.
实验3. 为了进一步验证网络能量的均衡,采用了本文算法与文献[26]和文献[27]进行比对实验,实验分别采用了3种不同的监测区域,给出了在相同覆盖率(99.9%)条件下,对于不同参数的比对实验过程.如图6所示.
|
图6 不同监测环境下网络生存周期对比 Fig.6 Comparison of network lifetime under different monitoring environment |
图6给出了在不同监测区域内,网络生存周期随工作节点与目标节点变化示意图.与本文算法相对比的是Energy-efficient target coverage algorithm(ETCA)[26]和Linear programming maximum lifetime coverage with energy harvesting(LP_MLCEH)[27].从图6(a)中可知,在3种算法的运行初期,网络生命周期都是随着节点数量的增加而增加.但由于本文算法参数取值范围的限定和冗余节点的关闭状态,使得在最终达到网络能量均衡时,本文算法的网络生命周期值要小于上述两算法.在对目标节点覆盖的过程中,本文算法的网络能量也小于上述两种算法,其原因同上所述.在图6(c)中,由于监测区域面积的扩大,使得部分冗余节点处于工作状态,延长了网络生命周期.当参数 k=1.8时,本文算法计算所得到的网络生存周期的数值已大于ETCA算法;当参数 k=2时,网络生存周期的大于上述两种算法.图6(d)给出了对目标节点覆盖过程中的网络生存周期的变化曲线图,随着对目标数量的增加,3种算法的网络生存都有所降低,最后趋于能量平衡.但在下降过程中,本文算法的平均下降速度小于上述两种,其原因主要体现在:当监测区域中某个部分所部署的传感器节点密集的地方,即该区域覆盖的期望值较大,通过传感器节点调度机制唤醒部分冗余节点,使其成为工作节点,加大了覆盖强度,提高了网络生存周期.对于监测区域300x300m2而言,其原理同上所述.
5 结束语本文提出了一种基于概率模型下的覆盖算法.
· 首先,对无线传感器网络建立了概率模型,提出了四圆无缝对接时有效覆盖面积的求解过程.
· 其次,给出了概率模型中冗余覆盖率的求解过程;对于网络模型中三重正方形的层次结构,也给出了覆盖期望值和方差的证明过程.
· 再次,本文结合三重正方形的覆盖期望值和方差求解方法,对传感器节点完成首次对目标节点覆盖后期望值求解方法的验证,同时也给出了证明过程;在覆盖过程中,传感器节点能量有所衰减,针对能量衰减所形成的覆盖区域的有界闭域,本文也给出了详细的证明过程;通过传感器节点状态调度机制,完成了节点之间的状态转换.
· 最后,通过仿真实验验证了OCPM算法的有效性和易扩展性.
今后工作的重点是,如何实现随机二次线性归划以及如何提高有界性覆盖质量.
| [1] | Wang B, Chua KC, Srinivasan V, Wang W. Information coverage in randomly deployed wireless sensor networks. IEEE Trans. on Wireless Communications, 2007,6(8):2994-3004.[doi:10.1109/TWC.2007.051044] |
| [2] | Tseng YC, Chen PY, Chen WT. K-Angle object coverage problem in a wireless sensor network. IEEE Sensors Journal, 2012,12(12):3408-3416.[doi:10.1109/JSEN.2012.2198054] |
| [3] | Xiao Y, Chen H, Wu K, Sun B, Zhang Y, Sun XY, Liu C. Coverage and detection of a randomized scheduling algorithm in wireless sensor networks. IEEE Trans. on Computers, 2010,59(4):507-521.[doi:10.1109/TC.2009.170] |
| [4] | Wang HZ, Meng FZ, Li ZZ. Energy efficient coverage conserving protocol for wireless sensor networks. Ruan Jian Xue Bao/Journal of Software, 2010,21(12):3124-3137(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3693.htm[doi:10.3724/SP.J.1001.2010.03693] |
| [5] | He X, Gui XL, An J. A distributed area coverage algorithm based on delayed awakening in wireless sensor networks. Journal of Computer Research and Development, 2011,48(5):786-792(in Chinese with English abstract). http://crad.ict.ac.cn:81/CRAD/ePublish/Search/Search.asp |
| [6] | Tahiry R, David SR. Connectivity preservation and coverage schemes for wireless sensor networks. IEEE Trans. on Automatic Control, 2011,56(10):2418-2428.[doi:10.1109/TAC.2011.2163885] |
| [7] | Ammari HM, Das SK. Centralized and clustered k-coverage protocols for wireless sensor networks. IEEE Trans. on Computers, 2012,61(1):118-132.[doi:10.1109/TC.2011.82] |
| [8] | Du JZ, Wang K, Guo D. Maximizing the lifetime of k-discrete barrier coverage using mobile sensors. IEEE Sensors Journal, 2013, 13(12):4690-4701.[doi:10.1109/JSEN.2013.2270555] |
| [9] | Cardei M, Du DZ. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 2005,11(3):333-340.[doi:10.1007/s11276-005-6615-6] |
| [10] | Yang SH, Dai F, Cardei M, Wu J, Patterson F. On connected multiple point coverage in wireless sensor networks. Int'l Journal of Wireless Information Networks, 2006,13(4):289-301.[doi:10.1007/s10776-006-0036-z] |
| [11] | Liu H, Wan P, Yi CW, Jia XH, Makki S, Niki P. Maximal lifetime scheduling in sensor surveillance networks. In:Proc. of the 24th Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM 2005). Miami:IEEE, 2005. 2482-2491.[doi:10.1109/INFCOM.2005.1498533] |
| [12] | Mini S, Udgata S, Sabat S. Sensor deployment and scheduling for target coverage problem in wireless sensor networks. IEEE Sensors Journal, 2014,14(3):636-644.[doi:10.1109/JSEN.2013.2286332] |
| [13] | Jin Y, Jo JY, Wang L, Kim Y, Yang XZ. ECCRA:An energy-efficient coverage and connectivity preserving routing algorithm under border effects in wireless sensor networks. Computer Communications, 2008,31(10):2398-2407.[doi:10.1016/j.comcom. 2008.03.001] |
| [14] | Liu YH, He Y, Li M, Wang JL, Liu KB, Li XY. Does wireless sensor network scale? A measurement study on Greenorbs. IEEE Trans. on Parallel and Distributed Systems, 2013,24(10):1983-1993.[doi:10.1109/TPDS.2012.216] |
| [15] | Liu YH, Mao XF, He Y, Liu KB, Wei G, Wang JL. CitySee:Not only a wireless sensor network. IEEE Network, 2013,27(5):42-47.[doi:10.1109/MNET.2013.6616114] |
| [16] | Chen J, Zhang L, Kuo Y. Coverage-Enhancing algorithm based on overlap-sense ratio in wireless multimedia sensor networks. IEEE Sensors Journal, 2013,13(6):2077-2083.[doi:10.1109/JSEN.2013.2248144] |
| [17] | Falcon R, Li X, Nayak A. Carrier-Based focused coverage formation in wireless sensor and robot networks. IEEE Trans. on Automatic Control, 2011,56(10):2406-2417.[doi:10.1109/TAC.2011.2163989] |
| [18] | Sun ZY, Wu WG, Wang HZ, Chen H, Wei W. An optimized strategy coverage control algorithm for WSN. Int'l Journal of Distributed Sensor Network, 2014,11(9):1-12.[doi:10.1155/2014/976307] |
| [19] | Cheng TM, Savkin AV. A distributed self-deployment algorithm for the coverage of mobile wireless sensor networks. IEEE Communications Letters, 2009,13(11):877-879.[doi:10.1109/LCOMM.2009.091178] |
| [20] | Tseng YC, Chen PY, Chen WT. k-Angle object coverage problem in a wireless sensor network. IEEE Sensors Journal, 2012,12(12):3408-3416.[doi:10.1109/JSEN.2012.2198054] |
| [21] | Chen A, Kumar S, Lai TH. Local barrier coverage in wireless sensor networks. IEEE Trans. on Mobile Computing, 2010,9(4):491-504.[doi:10.1109/TMC.2009.147] |
| [22] | Sun ZY, Wu WG, Wang HZ, Chen H, Xing XF. A novel coverage algorithm based on event-probability-driven mechanism in wireless sensor network. EURASIP Journal on Wireless Communications and Networking, 2014,2014(1):1-17.[doi:10.1186/1687-1499-2014-58] |
| [23] | Su JS, Guo WZ, Yu CL, Chen GL. Fault-Tolerance clustering algorithm with load-balance aware in wireless sensor network. Chinese Journal of Computers, 2014,37(2):445-456(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2014.00445] |
| [24] | Xing XF, Wang GJ, Wu J, Li J. Square region-based coverage and connectivity probability model in wireless sensor networks. In:Proc. of IEEE the 5th Int'l Conf. on Collaborative Computing Networking, Applications and Worksharing (CollaborateCom 2009). Washington:IEEE, 2009. 1-8.[doi:10.4108/ICST.COLLABORATECOM.2009.8335] |
| [25] | Xing GL, Wang XR, Zhang YF, Lu CY, Pless R, Gill C. Integrated coverage and connectivity configuration for energy conservation in wireless sensor networks. ACM Trans. on Sensor Networks, 2005,1(1):36-72.[doi:10.1145/1077391.1077394] |
| [26] | Xing XF, Wang GJ, Li J. Polytype target coverage scheme for heterogeneous wireless sensor network using linear programming. Wireless Communications and Mobile Computing, 2014,14(8):1397-1408.[doi:10.1002/wcm.2269] |
| [27] | Yang CL, Chin KW. Novel algorithm for complete targets coverage in energy harvesting wireless sensor network. IEEE Communications Letter, 2014,18(1):118-121.[doi:10.1109/LCOMM.2013.111513.132436] |
| [28] | 王换招,孟凡治,李增智.高效节能的无线传感器网络覆盖保持协议.软件学报,2010,21(12):3124-3137. http://www.jos.org.cn/1000-9825/3693.htm[doi:10.3724/SP.J.1001.2010.03693] |
| [29] | 何欣,桂小林,安健.基于延迟唤醒的无线传感器网络的分布式区域覆盖算法. http://crad.ict.ac.cn:81/CRAD/ePublish/Search/Search.计算机研究与发展,2011,48(5):786-792.asp |
| [30] | 苏金树,郭文忠,余朝龙,陈国龙.负载均衡感知的无线传感器网络容错分簇算法.计算机学报,2014,37(2):445-456.[doi:10.3724/SP.J.1016.2014.00445] |