2018, Vol. 39
2. 东软集团 软件架构新技术国家重点实验室, 辽宁 沈阳 110169;
3. 德克萨斯主教学校,德克萨斯 圣安东尼奥 78249
2. State Key Laboratory of Software Architecture, Neusoft Corporation, Shenyang 110169, China;
3. The Episcopal School of Texas, San Antonio 78249, USA
与传统的无线传感器网络(wireless sensor networks, WSNs)相比, 引入了多媒体传感器的无线多媒体传感器网络(wireless multimedia sensor network, WMSNs)在环境监测、视频监控、目标跟踪等应用领域都有着非常明显的优势[1].多样化的多媒体数据带来了更大的能量消耗[2].所以, 需要更加有效的节能技术和策略来面对新的能效挑战[3].
分簇式的拓扑结构被认为是最优化配置网络能量消耗的有效手段并且在节点管理等方面也有着特殊的优势[4].在一个密集部署的网络中, 相机视野(field of view, FoV)存在着较大程度的重叠覆盖, 因此他们所感知到的图像也会存在较大的视觉相关性(visual correlation, VC)[5].通过计算相机之间的VC, 可以估计感知数据的联合熵, 进而可以进行按簇数据压缩以减少传输的数据量[6].因此, 基于视觉相关性的分簇节能策略被提出.Alaei等基于等腰三角形FoV模型, 提出了一种基于FoV覆盖重叠率的单分簇成员(SCM)算法[7].该算法通过设置FoV覆盖重叠率阈值以最大化各个簇的平均覆盖重叠率.文献[8]改进了文献[7]的工作, 提出了一种多成员能效分簇(MCM)算法.MCM算法基于这样一个假设:如果拥有重叠FoV的相机之间的VC超过覆盖重叠率阈值, 则可以被同时分到多个簇中.Zhang等[9]利用改进的FoV模型—扇形FoV模型, 提出了基于节点相关性的WMSN节能分簇(NCC)算法.NCC算法采用网格计数方式来估算扇形相交面积, 取得了很好的实验效果, 同时该算法具有算法简单, 系统开销小等优点.以上这些算法都将VC定义为FoV的重叠覆盖率, 这种定义不能够准确地描述相机之间的视觉相关性而导致节能算法的性能相应地下降.另外, 以上的节能算法都是集中式的, 不利于将算法移植到较大规模的WMSNs中.
针对以上工作中存在的不足, 本文引入更加准确的VC定义并改进了视觉相关性系数(visual correlation coefficient, VCC)算法, 同时提出了一种基于VCC向量的分布式节能(VC-DEC)策略.实验结果表明该算法能够有效地减少能量消耗和提升相机能效平衡.
1 视觉相关性算法如前文所述, 相机的观测范围被限制于有向的FoV内.基于2D理想平面的简单FoV模型, 如图 1a所示.由图 1a可知, 相机的FoV可以被表示为一个4元组:(L, R, 
|
图 1 扇形视野模型和文献[5]提出的视觉相关性模型 Fig.1 Fan-shaped FoV model and the visual correlation model in literature [5] (a)—扇形视野模型; (b)—文献[5]提出的视觉性惯性模型. |
文献[5]通过对视觉成像原理的研究, 定义了视觉信息空间相关性模型以描述相机感知图像之间的相关性特征.其基于坐标变换理论, 通过比较同一参考点的多个参考向量在不同相机像平面上投影的差异度来定义相机的空间相关性.该方法充分利用了几何变换的优势, 获得了远低于图像匹配相关性算法的计算复杂度.
如图 1b所示, 以被观测目标为原点建立平面直角坐标系, 两个相机Ci和Cj部署在XoY平面上.其中, 
|
(1) |
其中, δij表示Ci和Cj之间关于被观测目标的视觉相关性系数.一般来说, δ∈[0, 1], ρ→1的过程, 表示两个传感器的相关性变大; δ→0时, 表示两个传感器之间的相关性变小.
通过以上的计算, 可以得到两个相机之间的视觉相关性系数.然而, 该方法只适用于可以忽略尺寸的被观测目标, 即将被观测物近似地视为一个场景点.不过, WMSN应用往往需要获取相机之间对整个观测区域的视觉相关性.因此, 本文改进了上述方法并提出了VCC算法, 其计算视觉相关性的过程如下.
首先, 相机Cs和Ck之间在整个感知区间上的视觉相关性系数VCCsk可以定义为
|
(2) |
其中, SCsk(P)表示相机Cs和Ck关于场景点P的空间相关性函数.显然, 复杂的积分运算将带来大量的额外开销.因此, 引入网格技术将式(2)离散化为
|
(3) |
其中, Lh表示第h个网格的位置坐标.这样获得VCCsk的计算复杂度就取决于网络尺寸的大小.在不影响准确性的情况下, 网格尺寸应该尽量选择得大一些.
然后, 将相机Cs的FoV等分成M(行)×N(列)个片, 如图 2所示.每片的面积Sp可以表示为
|
(4) |
|
图 2 FoV覆盖重叠 Fig.2 Overlapped FoV |
因此, VCCsk可以被表示为
|
(5) |
定义片Psij(第s相机、第i行、第j列)的坐标为片中心点CPsij的坐标, 即
|
(6) |
|
(7) |
其中, (xs, ys)是相机Cs的坐标.由此可以得到, 如果片Psij属于相机Cs与Ck之间的视野重叠区域, 那么有
|
(8) |
|
(9) |
其中, CPsij表示片Psij的中心; Lk和
|
(10) |
最后, 式(5)可以被改写为
|
(11) |
和LEACH协议[10]相似, 本文提出的VC-DEC策略也是以轮为单位在运行过程中不断地循环执行.VC-DEC策略的基本流程如图 3所示.
|
图 3 VC-DEC策略流程图 Fig.3 Flow chart of the VC-DEC strategy |
如图 3所示, 每一轮又分成:初始化、路由形成、稳定运行3个阶段.首先, 所有相机初始化参数并且生成视觉相关性系数向量(visual correlation coefficient vector, VCCV); 然后, 各个相机确定自己的身份并且建立分簇路由; 最后是准备阶段.其中, 第一阶段只需要运行一次, 在策略运行过程中除非发生特殊事件, 否则不需要再次运行.由于VC-DEC策略是完全分布式的, 所以每一个相机都是并行运行的.以相机Ci为例, VC-DEC策略的伪码如表 1所示, 步骤如下所述.
|
表 1 VC-DEC策略伪代码 Table 1 Pseudo-code of the VC-DEC strategy |
1) Ci初始化并与一跳距离内的相机交换相机参数, 之后运行VCC算法得到VCCVi, 其中Ci:{(Li, Ri,
2) 利用VCCVi和Eresi计算Ci的竞争筹码(competitive chip, CC), 并确定Ci的角色.函数Determine_role的伪代码表示如表 2所示.
|
|
表 2 函数Determine_role的伪代码 Table 2 Pseudo-code of the Determine_role function |
定义1 若某一相机在本轮成为CH, 它的竞争筹码是对它本轮之后的剩余能量的估计.
在给出参数CC的表达式之前, 先分析一下簇头(cluster head, CH)的能量消耗.利用能量消耗模型, CH的传输能量消耗为
|
(12) |
|
(13) |
其中:d0是一个距离阈值; l表示一个数据帧的比特数; h表示CH的邻居相机数; VCCi表示CH和第i个相机的VCC; dnext表示CH到下一跳距离.因此, 表达式(h+1)·Eelec是一个定值, dnext会随着下一跳而改变.这样, 定义竞争筹码CCi为
|
(14) |
|
(15) |
其中:Eresi表示相机Ci的剩余能量; Fnum表示每轮的数据帧数量; dij和VCCij分别是相机Ci和Cj之间的距离及VCC; dthreshold是一个和相机密度相关的经验参数.
3) 如果rolei=′CH′, Ci计算一跳范围内各个CH的簇头权重CHWj, 然后选择权重最大的CH为自己的下一跳并广播下一跳ID, 特别地, 如果Ci到下一跳的距离小于到Sink节点的距离, 那么修改下一跳ID为Sink节点.Ci的第j个CH的簇头权重CHWj的定义:
|
(16) |
其中:EresCHj表示第j个CH的剩余能量; dCHj, sink表示第j个CH到Sink节点的距离.
4) 如果rolei=′CM′, Ci计算自己与一跳范围内的各个CH的亲密度Intij, 然后宣布成为亲密度最小的CH的簇成员(cluster member, CM), 并广播自己的簇ID.
定义2 亲密度是衡量一个相机与不同CH通信带来的能量消耗.其表达式:
|
(17) |
其中, di, CHij和VCCi, CHij分别表示Ci与自己一跳范围内第j个CH之间的距离和VCC.
3 实验及分析为了评估节能策略的性能, 本文采用MATLAB 2012a对VC-DEC策略和已存在算法进行仿真实验.在实验中, 假设100到400个同质相机均匀部署在200 m×200 m的正方形FoI中, Sink节点位于FoI的左下角.在相机FoV参数中, R=40 m, α=60°, β∈[0, 2π).相机的初始能量为1 000 J, 每一轮发送1 000个数据帧, 帧的大小为4 kB.
3.1 参数dthreshold的确定参数dthreshold决定了簇的规模进而影响簇内相机的平均数量和路由次数.随着dthreshold的增加, 簇内相机的平均数量会下降, 而簇的个数也会相应地下降.这会导致VC-DEC优化作用的弱化, 因此平均能量消耗将会增加.相反, 在dthreshold的值较小时, 簇内相机数量减少, 频繁的路由带来了大量额外的能量消耗.因此dthreshold的值直接影响到VC-DEC节能策略的性能.
所以, 本文设计实验:通过在不同的相机密度下改变dthreshold的值来确定最合适的经验参数dthreshold.各个相机100轮的总能量消耗的均值和标准差如图 4所示.
|
图 4 100轮后各相机总能耗的均值和标准差 Fig.4 Mean and standard deviation of the energy consumption of each camera after 100 rounds (a)—能耗均值; (b)—)能耗标准差. |
由图 4可知, 4条实线分别对应4种相机密度下dthreshold和能量消耗之间的关系.虽然它们之间是独立的, 但是却大致表现出一致的变化趋势.平均能量消耗随着dthreshold的增加先减后增, 而标准差则先下降随后趋于稳定.实验的结果和之前对于dthreshold的分析是基本一致的.同时考虑到dthreshold较大时, 会增加网络的延迟开销.综上所述, 本文的后续实验, dthreshold被统一赋值为30.
3.2 性能比较为了直观地反映VC-DEC策略的性能, 在不同的相机密度下, 与SCM算法、LEACH协议以及直接传输方式进行对比实验.100轮之后相机平均剩余能量的均值和方差如图 5所示.
|
图 5 100轮后各相机剩余能量的均值和标准差 Fig.5 Mean and standard deviation of the residual energy of each camera after 100 rounds (a)—能耗均值; (b)—能耗标准差. |
实验结果显示, 本文提出的VC-DEC策略比已存在的对比算法在能效优化方面有一定的优势.然而这种优势会随着网络相机密度的增加而减少.这是因为, 对于一个随机部署的WMSN, 随着相机数量的增加, 相机之间的平均距离会减少; 与此相反, FoV的覆盖重叠率反而会相应地增加.因此同时优化传输距离和感知覆盖率的VC-DEC策略的优化作用被弱化了.通过图 5a可以得到VC-DEC策略在不同的相机密度下性能都比较稳定.另一方面, 通过图 5b可知, 与已存在的算法相比, VC-DEC策略在能量平衡性方面也有一定的提升.当网络达到某一密度(相机数量大于200)之后, 相机的能效平衡趋于稳定.
4 结论本文针对视觉相关性节能算法中视觉相关性定义不准确和集中式计算难以适用于大型网络的问题, 通过引入更加准确的视觉相关性定义改进了已有的视觉相关性系数算法, 并提出了一种完全分布式节能策略.该策略通过计算竞争筹码、亲密度和簇头权重来合理化网络分簇路由, 由此延长了网络生命周期.实验结果表明, 本文提出的节能策略在增加能效和平衡能耗方面具有一定的优势.
| [1] |
Akyildiz I F, Melodia T, Chowdury K R.
Wireless multimedia sensor networks:a survey[J]. IEEE Wireless Communications, 2007, 14(6): 32–39.
DOI:10.1109/MWC.2007.4407225 |
| [2] |
Baccarelli E, Chiti F, Cordeschi N, et al.
Green multimedia wireless sensor networks:distributed intelligent data fusion, in-network processing, and optimized resource management[J]. IEEE Wireless Communications, 2014, 21(4): 20–26.
DOI:10.1109/MWC.2014.6882292 |
| [3] |
Zhang Z J, Lai C F, Chao H C.
A green data transmission mechanism for wireless multimedia sensor networks using information fusion[J]. IEEE Wireless Communications, 2014, 21(4): 14–19.
DOI:10.1109/MWC.2014.6882291 |
| [4] |
Ehsan S, Hamdaoui B.
A survey on energy-efficient routing techniques with QoS assurances for wireless multimedia sensor networks[J]. IEEE Communications Surveys & Tutorials, 2012, 14(2): 265–278.
|
| [5] |
Dai R, Akyildiz I F.
A spatial correlation model for visual information in wireless multimedia sensor networks[J]. IEEE Transactions on Multimedia, 2009, 11(6): 1148–1159.
DOI:10.1109/TMM.2009.2026100 |
| [6] |
Wang P, Dai R, Akyildiz I F.
A spatial correlation-based image compression framework for wireless multimedia sensor networks[J]. IEEE Transactions on Multimedia, 2011, 13(2): 388–401.
DOI:10.1109/TMM.2010.2100374 |
| [7] |
Alaei M, Barcelo-Ordinas J M.
A method for clustering and cooperation in wireless multimedia sensor networks[J]. Sensors, 2010, 10(4): 3145–3169.
DOI:10.3390/s100403145 |
| [8] |
Alaei M, Barcelo-Ordinas J M.
A collaborative node management scheme for energy-efficient monitoring in wireless multimedia sensor networks[J]. Wireless Networks, 2013, 19(5): 639–659.
DOI:10.1007/s11276-012-0492-6 |
| [9] |
Zhang Q, Wang R, Chao S H A, et al.
Node correlation clustering algorithm for wireless multimedia sensor networks based on overlapped FoVs[J]. The Journal of China Universities of Posts and Telecommunications, 2013, 20(5): 37–44.
DOI:10.1016/S1005-8885(13)60087-4 |
| [10] |
Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. NewYork: IEEE, 2000: 10-13.
|