随着无线传感器网络在环境监测、战场监控、农业监测等方面的广泛应用, 近几年来, 越来越多的研究者从事相关研究^{[1, 2]}.无线传感器网络分为全向传感器网络和有向传感器网络, 全向传感器网络通过多跳通信的方式组成网络, 协作地对周边环境进行简单的数据采集(如温度、湿度等)^[3], 提供的监测能力非常有限.而监测环境的复杂多变, 迫切需要将信息量丰富的音频、图像、视频等信息引入到以无线传感器网络为基础的环境监测活动中, 实现精准的环境监测.具有更强通信、处理能力的有向传感器网络(视频传感器网络等)应运而生^[4].

覆盖问题是当前有向传感器网络的基本问题, 反映了网络对环境的监测质量.可将其分为以下几类:区域覆盖、目标覆盖、栅栏覆盖.从覆盖质量的角度, 又可分为K覆盖、全视域覆盖等^{[5, 6]}.目前, 越来越多的学者从事相关研究, 并取得了一定成果.Ma等人^[7]针对视频传感器网络的目标覆盖控制问题, 提出了一种不可旋转的扇形感知模型.Tao等人^[8]扩展了视频传感器网络扇形感知模型, 提出一种可旋转的扇形感知模型, 并利用凸理论及虚拟势场理论研究网络覆盖增强问题.文献[9]提出基于重覆盖质心及有效质心的虚拟势场覆盖优化算法, 并考虑了边界节点覆盖问题.文献[10]提出一种覆盖增强及节点调度算法(overlap-sense ratio coverage-enhancing algorithm, 简称OSRCEA), 利用重覆盖率调整节点方向实现覆盖增强, 但同样存在边界覆盖丢失问题.王晓晨等人^[11]针对节点落于区域边界造成覆盖损失等问题, 研究了考虑边界区域的覆盖增强算法.文献[12]针对目标覆盖问题, 提出利用分布式学习自动机解决连通目标覆盖问题.文献[13]针对最小暴露路径问题, 提出基于质心的Voronoi图算法.

当网络初始随机部署时, 为满足确定的覆盖率要求, 研究覆盖预测模型及数量估计问题是覆盖问题的基础, 它可以更好地指导初始部署, 从而避免存在过多冗余节点.针对全向传感器网络中的覆盖边界效应及连通问题, Xing等人^[14]研究了无线传感器网络的覆盖预测问题, 将目标区域进行划分, 提出基于概率的覆盖及连通估计模型.Ma等人^[7]提出了利用概率模型对网络初始部署进行预测, 建立了初始覆盖率P_cov、节点半径r、节点数量N、节点传感角度α、目标区域Ω之间的关系(coverage prediction model without boundary effect, 简称CPMOB).

$ {P_{{\mathop{\rm cov}} }} = 1-{\left( {1-\frac{{\alpha {r^2}}}{\mathit{\Omega }}} \right)^N} $

(1)

由公式(1)可知:目标区域内网络覆盖率至少达到P_cov时, 所需部署的节点数为$ N \ge \frac{{\ln (1-{P_{{\mathop{\rm cov}} }})}}{{\ln (\mathit{\Omega }-\alpha {r^2})-\ln \mathit{\Omega }}} $.

Liu等人^[15]证明了有向传感器网络在均匀随机部署中, 目标区域中某个子区域被K个节点感知到的概率符合泊松分布:

$ P[N(A) = k] = {e^{ -\lambda \mu (s)}} \times \frac{{{{(\lambda \mu (s))}^k}}}{{k!}} $

(2)

其中, A表示目标区域Ω的某个子区域, λ为节点密度, 即单位面积内节点数目, μ(s)为节点感知面积αr², k为目标区域内监测到任意一点的节点个数, 此模型可用于多重覆盖中.

Zhao等人^[16]根据文献[15]的模型, 研究了无线多媒体传感器网络在多种感知模型下的覆盖预测问题, 并建立了目标区域中任意一点至少被1个节点所感知的概率模型(node density model without boundary effect, 简称NDMOB), 证明了当节点感知区域远小于目标区域时, CPMOB和NDMOB结果相同.文献[17]研究了异构有向传感器网络中的覆盖估计问题, 提出一种异构覆盖预测模型.

以上模型均忽略了目标区域的边界问题, 认为节点感知区域均在目标区域内.实际应用环境中, 网络随机初始部署时, 经常会出现部分节点的感知区域落在目标区域外面, 从而导致Zhao等人^[10]的模型理论值与实验真实值误差较大, 节点规模预测不够准确, 不能较好地指导部署.

本文针对随机部署的有向传感器网络, 为满足确定初始覆盖率要求, 更好地预测初始部署的网络规模, 当网络随机初始部署时, 充分考虑了部分节点落在边界区域的情况, 创新性地提出了一种基于概率的网络覆盖预测模型(probability-based coverage prediction model with boundary effect, 简称PCPMB), 并对PCPMB, CPMOB及NDMOB模型理论值及实验真实值进行比较分析.

1 网络感知模型与相关定义 1.1 有向传感器网络感知模型

本文假设所研究的有向传感器节点均具有如下特点.

假设1.网络是同构的, 所有节点具有相同的传感视角及感知半径, 且知道各自的位置信息及主感知方向等信息.

假设2.节点随机部署在边长为L的正方形目标区域内, 且节点位置不可移动.

与全向传感器网络不同, 有向传感器网络的感知区域为可旋转的扇形区域, 用五元组 < S_i, α, r, V_i, β_i>表示感知模型, 如图 1所示.其中, S_i(x_i, y_i)表示节点S_i的位置坐标, r表示节点S_i的感知半径, V_i表示节点的感知方向, 2α表示节点S_i的视角, α为传感角度.β_i表示V_i与水平X轴之间的夹角, 称为方向角, 0≤β_i≤2p.

1.2 相关定义

为方便描述目标区域的边界问题, 定义如下.

1.2.1 感知区域和可能感知区域

在目标区域内, 节点在某一时刻所监测到的区域即为感知区域, 通过旋转节点所监测到的整个圆即为可能感知区域, 如图 2所示.

1.2.2 内区域、边角区域与边区域

如图 3所示.

· 在目标区域Ω中, 与边界距离大于节点感知半径的点构成的区域Ω₁, 则称Ω₁为内区域;

· 位于目标区域4个边角的区域Ω₂称为边角区域;

· 除内区域及边角区域外的区域Ω₃称为边区域.

1.2.3 内节点、边角节点与边节点

当随机部署节点时, 落于内区域的节点称为内节点.相应的, 落于边角区域的节点称为边角节点, 落于边区域的节点称为边节点, 如图 3所示, S₁为内节点, S₂和S₃为边节点, S₄为边角节点.

2 基于概率的覆盖预测模型及数量估计 2.1 覆盖预测及数量估计

在均匀随机部署节点的应用场景中, 目标区域中某个子区域被k个节点感知到的概率符合泊松分布^[9].因为$ \mu (A) = \alpha {r^2} = \pi {r^2} \times \frac{\alpha }{\pi } $, 现设$ E(S) = \pi {r^2} $, 即, 节点的可能感知区域.$ P = \frac{\alpha }{\pi } $, 即感知区域在可能感知区域中的比例.则公式(2)可表示为

$ P[N(A) = k] = {{\rm{e}}^{ -\lambda \times E(S) \times P}} \times \frac{{{{(\lambda \times E(S) \times P)}^k}}}{{k!}} $

(3)

针对随机部署的有向传感器网络, 为满足初始覆盖率要求, 更好地预测初始部署的节点规模, 当随机初始部署时, 充分考虑部分节点落在边界的情况, 应将节点的可能感知区域落在目标区域外部的部分去掉, 从而得出较为准确的覆盖预测模型.为了方便求解, 将目标区域划分为内区域、边区域与边角区域, 如图 3所示.当随机部署网络时, 部分节点将落在内区域内, 部分节点位于边区域及边角区域内.根据全概公式, 初始部署后网络的覆盖率为

$ E(S) = P({\mathit{\Omega }_1})E({\mathit{\Omega }_1}) + P({\mathit{\Omega }_2})E({\mathit{\Omega }_2}) + P({\mathit{\Omega }_3})E({\mathit{\Omega }_3}) $

(4)

其中, P(Ω₁), P(Ω₂)和P(Ω₃)分别表示节点落在内区域Ω₁、边角区域Ω₂和边区域Ω₃的概率, E(Ω₁)表示内节点的可能感知区域面积期望值, E(Ω₂)表示边角节点的可能感知区域面积期望值, E(Ω₃)表示边节点的可能感知区域面积期望值.

如图 3所示, 由于节点是随机部署在目标区域Ω中, 且服从均匀分布, 因此可求出节点落在内区域、边角区域和边区域的概率分别为

$ P({\mathit{\Omega }_1}) = \frac{{{S_{{\mathit{\Omega }_1}}}}}{{{S_\mathit{\Omega }}}} = \frac{{{{(L-2r)}^2}}}{{{L^2}}} $

(5)

$ P({\mathit{\Omega }_2}) = \frac{{{S_{{\mathit{\Omega }_2}}}}}{{{S_\mathit{\Omega }}}} = \frac{{4{r^2}}}{{{L^2}}} $

(6)

$ P({\mathit{\Omega }_3}) = \frac{{{S_{{\mathit{\Omega }_3}}}}}{{{S_\mathit{\Omega }}}} = \frac{{4r(L-2r)}}{{{L^2}}} $

(7)

当节点位于内区域时, 节点的感知区域全部落在目标区域内, 将其视为无边界效应问题.可得内节点的可能感知区域面积期望值.

$ E({\mathit{\Omega }_1}) = \pi {r^2} $

(8)

如图 4所示, 节点s(x, y)是边角节点, 可得到此时节点s(x, y)的可能感知区域在目标区域内的面积C_Ω2为

$ {{C}_{{{\mathit{\Omega }}_{2}}}}={{S}_{oAsE}}+{{S}_{\Delta ABs}}+{{S}_{\Delta EDs}}+{{S}_{\overset\frown{sBCD}}}=xy+\frac{y\sqrt{{{r}^{2}}-{{y}^{2}}}}{2}+\\\frac{x\sqrt{{{r}^{2}}-{{x}^{2}}}}{2}+\left( \frac{\pi /2+\arcsin (y/r)+\arcsin (x/r)}{2\pi } \right)\pi {{r}^{2}} $

(9)

因此, 可以计算得到边角节点的可能感知区域面积期望值E(Ω₂)为

$ \begin{align} &E({{\mathit{\Omega }}_{2}})=\frac{1}{{{r}^{2}}}\int\limits_{0}^{r}{{{C}_{{{\mathit{\Omega }}_{2}}}}}\rm{d}x\int\limits_{0}^{r}{\rm{d}y}=\frac{1}{{{r}^{2}}}\int\limits_{0}^{r}{\left[xy+\frac{y\sqrt{{{r}^{2}}-{{y}^{2}}}}{2}+ \right.} \\ &\frac{x\sqrt{{{r}^{2}}-{{x}^{2}}}}{2}+\left. \left( \frac{\frac{\pi }{2}+\arcsin \left( \frac{y}{r} \right)+\arcsin \left( \frac{x}{r} \right)}{2} \right){{r}^{2}} \right]\rm{d}x\int\limits_{0}^{r}{\rm{d}y} \\ \end{align} $

(10)

如图 5所示, s₁(x, y)和s₂(x, y)均为边节点, 当边节点落于边区域且与边区域左右边界距离小于r时, 如图 5中边节点s₁(x, y).可得到此时节点s₁(x, y)的可能感知区域在目标区域内的面积C_Ω3¹为

$ \begin{align} &C_{{{\mathit{\Omega }}_{3}}}^{1}={{S}_{\Delta {{A}_{1}}{{B}_{1}}{{s}_{1}}}}+{{S}_{\Delta {{E}_{1}}{{D}_{1}}{{s}_{1}}}}+{{S}_{\overset\frown{{{A}_{1}}{{s}_{1}}{{E}_{1}}}}}+{{S}_{\overset\frown{{{B}_{1}}{{C}_{1}}{{D}_{1}}}}} \\ &\text{ }=y\sqrt{{{r}^{2}}-{{y}^{2}}}+x\sqrt{{{r}^{2}}-{{x}^{2}}}+\left( \frac{2\text{ }\!\!\pi\!\!\text{ }-2\arccos (y/r)-2\arccos (x/r)}{2\text{ }\!\!\pi\!\!\text{ }} \right)\text{ }\!\!\pi\!\!\text{ }{{r}^{2}} \\ &\text{ }=y\sqrt{{{r}^{2}}-{{y}^{2}}}+x\sqrt{{{r}^{2}}-{{x}^{2}}}+(\text{ }\!\!\pi\!\!\text{ }-\arccos (y/r)-\arccos (x/r)){{r}^{2}} \\ &E({{\mathit{\Omega }}_{3}})=\frac{1}{(L-2r)r}\left( 2\int\limits_{0}^{r}{C_{{{\mathit{\Omega }}_{3}}}^{1}\text{d}x\int\limits_{0}^{r}{\text{d}y+\int\limits_{r}^{L-3r}{C_{{{\mathit{\Omega }}_{3}}}^{2}\text{d}x\int\limits_{0}^{r}{\text{d}y}}}} \right) \\ \end{align} $

(11)

当边节点落于边区域且与边区域左右边界距离大于等于r时, 如图 5中边节点s₂(x, y).可得此时节点s₂(x, y)的可能感知区域在目标区域内的面积C_Ω3²:

$ C_{{{\mathit{\Omega }}_{3}}}^{2}=\text{ }\!\!\pi\!\!\text{ }{{r}^{2}}-({{S}_{\overset\frown{{{s}_{2}}{{A}_{2}}{{B}_{2}}{{C}_{2}}}}}-{{S}_{\mathit{\Delta }{{A}_{2}}{{s}_{2}}{{C}_{2}}}})=\\\frac{1}{2}{{r}^{2}}(2\text{ }\!\!\pi\!\!\text{ }-2\arccos (y/r)+\sin (2\arccos (y/r))) $

(12)

因此, 可以计算得到边节点的可能感知区域面积期望值E(Ω₃)为

$ E({{\mathit{\Omega }}_{3}})=\frac{1}{(L-2r)r}\left( 2\int\limits_{0}^{r}{C_{{{\mathit{\Omega }}_{3}}}^{1}\rm{d}x\int\limits_{0}^{r}{\rm{d}y+\int\limits_{r}^{L-3r}{C_{{{\mathit{\Omega }}_{3}}}^{2}\rm{d}x\int\limits_{0}^{r}{\rm{d}y}}}} \right) $

(13)

根据以上推理, 当节点随机部署在目标区域内时, 考虑到边界效应影响, 目标区域中某个子区域被k个节点感知到的概率为

$ P[N(\mathit{\Omega })=k]={{e}^{-\lambda \times E(S)\times P}}\times \frac{{{(\lambda \times E(S)\times P)}^{k}}}{k!} $

(14)

其中, E(S)=P(Ω₁)E(Ω₁)+P(Ω₂)E(Ω₂)+P(Ω₃)E(Ω₃), $ P[N(\mathit{\Omega }) = k] = {e^{ -\lambda \times E(S) \times P}} \times \frac{{{{(\lambda \times E(S) \times P)}^k}}}{{k!}} $; λ为节点密度, 即单位面积内节点数目; k为目标区域内监测到任意一点的节点个数.与NDMOB模型一样, 此模型可用于多重复覆盖问题.现以一重覆盖为例, 得出覆盖预测及数量估计公式.已知考虑边界效应的节点可能感知区域面积期望值为E(S), 求目标区域Ω中任意一点至少被1个节点感知的概率为

$ {P_{{\rm{cov}}}} = P[N(\mathit{\Omega }) \ge 1] = 1 - P[N(\mathit{\Omega }) = 0] = 1 -{e^{ -\lambda \times E(S) \times P}} $

(15)

$ \lambda =-\frac{{\ln (1-{P_{{\mathop{\rm cov}} }})}}{{E(S) \times P}} $

(16)

由式(15)、式(16)可知:当要求目标区域内网络覆盖率至少达到P_cov时, 所需部署的节点数为

$ N = \mathit{\Omega }\lambda $

(17)

2.2 模型概率属性

命题1. P_cov=1-e^-λ×E(S)×P满足概率属性

证明:当没有节点落在目标区域时, 即λ→0, 于是可得:

$ \mathop {\lim }\limits_{\lambda \to 0} {P_{{\mathop{\rm cov}} }} = \mathop {\lim }\limits_{\lambda \to 0} (1-{{\rm{e}}^{-\lambda \times E(S) \times P}}) = 0. $

当整个目标区域布满节点时, 即λ→∞, 可得:

$ \mathop {\lim }\limits_{\lambda \to \infty } {P_{{\mathop{\rm cov}} }} = \mathop {\lim }\limits_{\lambda \to \infty } (1-{{\rm{e}}^{-\lambda \times E(S) \times P}}) = 1. $

由于e^-λμ(s)是λ的单调减函数, 于是, P_cov=1-e^-λ×E(S)×P是λ的单调增函数, 因此可得:0≤P_cov≤1.

命题2.当节点感知区域远小于目标区域时, 即, 近似目标区域不存在边界效应, 则PCPMB与NDMOB的结果相同.

证明:PCPMB与NDMOB的比值为:$ f = \frac{{1-{{\rm{e}}^{-\lambda \times E(S) \times P}}}}{{1-{{\rm{e}}^{ - \lambda \mu (S)}}}} $.

由于$ \mu (S) = \alpha {r^2} = {\rm{\pi }}{r^2} \times \frac{\alpha }{{\rm{\pi }}} $, 现设E(S')=πr², 即, 节点的可能感知区域; $ P = \frac{\alpha }{{\rm{\pi }}} $, 即, 感知区域在可能感知区域中的比例, 与PCPMB模型中的P相同.即f表示为:$ f = \frac{{1-{{\rm{e}}^{-\lambda \times E(S) \times P}}}}{{1-{{\rm{e}}^{ - \lambda \mu (S)}}}} = \frac{{1 - {{\rm{e}}^{ - \lambda \times E(S) \times P}}}}{{1 - {{\rm{e}}^{ - \lambda \times E(S') \times P}}}} $.

当节点感知区域远小于目标区域时, 近似目标区域不存在边界效应.边节点、节角节点的可能感知区域面积期望值与内节点的可能感知区域面积期望值近似相等, 即:E(Ω₁)~E(Ω₂)~E(Ω₃)=πr².

可知:

$ \begin{array}{l} E(S) = P({\mathit{\Omega }_1})E({\mathit{\Omega }_1}) + P({\mathit{\Omega }_2})E({\mathit{\Omega }_2}) + P({\mathit{\Omega }_3})E({\mathit{\Omega }_3}) \cong \\ \frac{{{{(L-2r)}^2}}}{{{L^2}}} \times {\rm{\pi }}{r^2} + \frac{{4{r^2}}}{{{L^2}}} \times {\rm{\pi }}{r^2} + \frac{{4r(L-2r)}}{{{L^2}}} \times {\rm{\pi }}{r^2} = {\rm{\pi }}{r^2}. \end{array} $

于是可得:

$ f = \frac{{1-{{\rm{e}}^{-\lambda \times E(S) \times P}}}}{{1-{{\rm{e}}^{ - \lambda \times E(S') \times P}}}} \sim 1. $

即证明了命题2成立.

实验验证如图 6所示, 横坐标表示目标区域边长L与节点感知半径r的比值, 纵坐标表示PCPMB与NDMOB所得覆盖率比值.

3 模型性能分析与评价

本实验在Windows 7环境下, 利用matlab 7.0进行仿真, 并分析了CPMOB, NDMOB及PCPMB之间的性能, 验证了PCPMB跟实际部署情况更加符合, 准确性更好.实验仿真参数见表 1.

3.1 覆盖预测分析

通过一系列仿真实验来说明3个主要参数对CPMOB, NDMOB及PCPMB的影响, 分别是:节点规模、感知半径、节点传感角度.针对此3个参数, 本节将对模型所得理论覆盖率进行比较, 并与实验真实覆盖率进行比较, 以此判断模型的准确性.

为更加清晰地比较模型理论结果与实验真实覆盖率之间的近似程度, 本实验定义覆盖误差率(coverage error rate, 简称CER)的概念, 即

$ CER = \frac{{TheoreticalResults-ExperimentalResults}}{{ExperimentalResults}}. $

通过反复对随机部署的有向传感器网络进行仿真, 并计算其覆盖率, 本实验中所得的实验真实覆盖率为30次仿真的平均值.

如图 7(a)变化曲线可以看出:当r和α一定时, 网络覆盖率随着节点规模N的不断增加而扩大, 且增加速度较快.当节点规模非常大时, 4条曲线趋向一致.这是由于当节点规模非常大时, 整个目标区域将被完全覆盖, 即覆盖率1.同时, 在相同的节点规模下, PCPMB的理论覆盖率与实验真实覆盖率误差非常小, 拟合度好.从图 7(b)中曲线可知:本文所提模型与实验真实值之间的覆盖误差率基本都保持在1%之内, 最大误差率小于2.5%.其他两种模型的覆盖误差率最小值大于3%, 最高误差率接近10%.

感知半径r对CPMOB, NDMOB, PCPMB和实验真实覆盖率的影响也类似.当节点规模一定时, 节点感知半径越大, 说明节点可感知面积越大, 从而覆盖率会随之不断上升.由图 8(a)可知:PCPMB的理论覆盖率与实验真实覆盖率误差非常小, 拟合度好.从图 8(b)中曲线可知:本文所提模型理论值与实验真实值之间的覆盖误差率基本都保持在1.3%之内, 最大误差率小于2%.其他两种模型的覆盖误差率最小值大于4.1%, 最高误差率接近8%.

同样地, 传感角度α对CPMOB, NDMOB, PCPMB和实验真实覆盖率的影响也类似.当节点规模一定时, 传感角度越大, 说明节点可感知面积越大, 覆盖率会不断上升.由图 9(b)可知:本文所提模型理论值与实验真实值之间的覆盖误差率基本都保持在1.5%之内, 最大误差率小于1.8%.其他两种模型的覆盖误差率最小值大于5%, 最高大于9%的误差.

综合上述3组对比实验得知:PCPMB模型准确度更好, 对初始部署时网络覆盖率的预测更加准确.说明其在覆盖率预测等方面有着更优的性能, 与实际情况更加吻合.

3.2 节点规模数量分析

图 10(a)表示PCPMB模型节点数量估计理论值在不同目标区域不同覆盖率情况下的变化曲线.由图 10(a)的曲线可知:随着网络覆盖率的提高, 初始随机部署时所需的节点数量增长速度大致呈指数级的增加; 随着覆盖率要求的不断提高, 初始部署时所需节点数量也不断增加; 同时, 随着目标区域的增大, 实现相同覆盖率所需部署的节点数量也会快速增加.

从图 10(b)可以看出:随着网络覆盖率的提高, 目标区域中所需部署的节点数量也相应增加, 且增加速度较快; 当初始网络覆盖率较低时, 边界效应对网络影响较小, 两条曲线趋向一致; 在相同网络覆盖率时, PCPMB对部署节点数量的预测更加准确.

4 结束语

本文针对有向传感器网络随机部署节点环境下的网络覆盖及节点规模预测问题, 提出了一种基于概率的覆盖预测模型, 该模型反映了节点密度、节点感知半径、传感角度与覆盖率之间的数学关系.最后, 通过一系列仿真实验, 说明本文所提出的模型在预测性能上有较大提升.由于充分考虑了目标区域边界效应, 与实际随机部署环境更加符合, 当初始随机部署需要满足确定覆盖率时, 通过该模型准确的预测节点数量来指导部署.