无线传感器网络中实现可信信息覆盖的能量感知的节点优化选择方法研究
Research on Energy-Aware Sensor Selection for Confidential Information Coverage in Wireless Sensor Networks

作者: 浦世亮 :杭州海康威视数字技术股份有限公司,浙江 杭州; 徐向华 :杭州电子科技大学计算机学院,浙江 杭州; 杨建旭 :中国人民银行清算总中心,北京;

关键词: 无线传感网络网络寿命节点选择能量感知0-1整数规划WSN Sensor Deployment Network Lifetime Sensor Node Selection Energy Aware 0-1 Integer Programming

摘要:
在无线传感器网络的区域监测应用中,保障区域可信监测覆盖的传感器节点优化选择是一个重要问题。本文提出了节点能量感知的传感器优化选择方法,基于监测值误差精度和传感器剩余能量约束,将传感器节点的优化选择问题转化为0-1整数规划问题并求解最少传感器选择集合,既保证了监测精度又延长了网络寿命。利用Inter Berkeley实验室的温度数据进行仿真实验,并针对不同的插值方法进行了实验对比分析,在满足相同监测精度误差情况下,网络寿命延长了2倍以上,优于同类算法。

Abstract: In the area monitoring applications of wireless sensor networks, the optimal selection of sensor nodes for confidential information coverage is an important issue. This paper presents an energy aware method of sensor node selection to satisfy the monitoring precision and sensor residual energy constraint. We transform the energy aware sensor node selection problem into a 0-1 integer programming problem, and solving the minimum selected sensor set, both to ensure the accuracy of monitoring and prolong the network lifetime. We use Intel Berkeley laboratory’s temperature data for simulation experiments. Compared with different interpolation methods, the network lifetime is extended by more than 2 times under the same monitoring precision error condition.

1. 引言

无线传感器网络(WSN)由许多小型的传感器节点组成,每个传感器节点具有采集、处理和转发数据的功能,采集的数据属性包括温度、湿度、光照强度、电压等等 [1] [2] [3] [4] [5] 。无线传感器网络广泛应用于震动监控、精准农业、路径追踪等各种应用场景 [6] [7] [8] 。在精准农业应用中,由于农田区域面积广大,需部署大量的传感器节点对农田的温度、湿度等属性值进行采样监测,如何合理部署并保证监测精度是其中一个重要问题 [1] [2] [3] [9] [10] 。

本文主要研究如何从区域随机部署的传感器中选择有限的传感器节点进行采样,并对未部署点的监测值进行估计,从而获得整个区域的监测属性值,实现对区域的可信信息覆盖(CIV-confidential information coverage) [3] [4] [5] ,也称为可信信息覆盖中的节点选择问题。在CIV的节点选择问题中,如何求解满足估计误差精度的条件下最小化传感器数目是主要目标。

Wang B [3] 针对满足可信信息覆盖的节点选择问题,利用Kriging插值法预估未部署点的监测值,以及用均方根误差对结果进行分析评价,但是并没有论证搜索半径对结果精度的影响。在 [4] [5] 中,S. P. Chepuri等人将传感器选择问题解释为一种优化问题,即在网络中满足误差约束的条件下选择最佳的传感器子集,设计了一种稀疏选择向量选择最优传感器集合。文献 [4] [5] 虽然考虑了误差精度,将传感器选择问题转化为0-1整数规划问题求解;然而S. P. Chepuri等人并有没考虑所选传感器节点的剩余能量因素,若所选传感器的剩余能量处于低能量,那么被选择的节点将很快失效。在 [11] 中,Sijia Liu等人针对传感器选择问题设计了一种稀疏促进罚函数避免重复选择相同传感器的情况,将问题公式化为凸二次规划求解,从而达到网络中传感器负载均衡的目的。然而同样作为区域重构问题,Sijia Liu等人将估计的误差精度作为凸二次规划的目标函数,这就使得产生的传感器集合存在并没有达到给定精度要求的情况。

网络中传感器的电池的剩余能量各不相同,因此为了延长网络生命周期,在保证监测采样精度情况下,传感器节点的剩余能量也是需要考虑的重要因素。然而上述已有研究中,并没有考虑CIV节点选择中考虑节点剩余能量因素,影响到节点能量受限的传感器网络的覆盖监测寿命。

本文针对可信信息覆盖的节点选择问题,考虑传感器节点的剩余能量因素,将传感器选择公式化为0-1整数规划进行求解最优的传感器节点选择集合,使得所有监测点的检测值满足给定的估计误差精度要求,而且同时满足给定的剩余能量要求,从而实现网络负载均衡,延长网络生命周期。本文主要贡献如下:

Ÿ 在可信信息覆盖的区域监测传感器选择问题中引入剩余能量约束,避免选择剩余能量过低的传感器,延长网络寿命并保证区域监测覆盖和监测值精度。

Ÿ 提出了能量约束的传感器选择问题的优化求解方法,将传感器优化选择问题转化为0-1整数规划问题,并求解最少传感器选择集合,实现可信信息覆盖。

Ÿ 利用Inter Berkeley实验室的温度数据进行仿真实验,并针对不同的插值方法进行了实验对比分析,在满足相同监测精度误差情况下,网络寿命延长了2倍以上。

本文组织结构:第2节给出了无线传感器网络的区域监测应用中的节点优化选择问题定义,以及考虑剩余能量因素的节点优化选择的0-1整数规划建模描述;第3节给仿真实验和对比分析比较结果;最后,第4节是本文总结。

2. 问题定义

问题描述:针对无线传感器网络的区域监测问题,在区域中部署N个传感器节点,每个节点每隔一定时间间隔对所在位置的属性值(温度、湿度等)进行采样。在满足区域可信监测信息覆盖下,即监测的给定误差精度阈值和节点剩余能量阈值约束条件下,所选择的监测传感器数量最少,实现有效监测精度的区域监测覆盖应用。

我们考虑通常情况,即在区域中部署多个传感器节点,每个节点每隔一定时间间隔对所在位置的属性值(温度、湿度等)进行采样。文中将传感器节点简称为节点,二者含义相同。表1给出文中用到的一些符号表示。

我们假设 f ( t k , s n ) 表示位置sn上的节点第k时刻的采样值。由于采样过程中会产生误差,我们将该误差表示为 e k , n 。那么,采样模型可以表示为:

y k , n = f ( t k , s n ) + e k , n (1)

其中, e k , n ~ ( 0 , σ 2 ) σ 2 是噪音的协方差矩阵。 k = 1 , 2 , , k n = 1 , 2 , , n 。令:

Table 1. Definition of parameters and symbols

表1. 参数与符号定义

y = [ y 1 , 1 , , y K , 1 , , y 1 , N , , y K , N ] T

f = [ f ( t 1 , s 1 ) , , f ( t K , s 1 ) , , f ( t 1 , s N ) , , f ( t K , s N ) ]

e = [ e 1 , 1 , , e K , 1 , , e 1 , N , , e K , N ] T

进一步可以将公式(1)简化表示为:

y = f + e (2)

我们的目标是区域可信监测覆盖下通过已知监测节点对未部署点的监测属性值进行估计。假设未部署点值为 θ ,坐标为 δ ,那么:

θ = { f ( t 1 , δ ) , f ( t 2 , δ ) , , f ( t k , δ ) } (3)

然而,针对估计问题,统计学中有多种插值方法,不同插值方法应用场合不同,效果也不同。这里,我们采用简单的线性插值模型,即:

θ ¯ = W F ( y ) + c (4)

其中,W为未知的估计系数,F(y)为插值函数,由于无偏性要求, c = 0

特别地,当插值函数为线性插值时,

θ ¯ = W y (5)

根据均方误差公式 E { ( θ θ ¯ ) ( θ θ ¯ ) T } ,再结合公式(4),我们就可以得到误差公式:

J ( w ) = n = 1 N E [ θ n ( w n ) T F ( y ) ] 2 (6)

将公式(5)展开后得:

J ( w ) = n = 1 N E [ θ n 2 2 w n T F ( y ) θ + w n F ( y ) F ( y ) T w n T ] (7)

因为 y = f + e ,那么令,

E ( F ( y ) F ( y ) T ) = E [ F ( f + e ) F ( f + e ) T ] = p

E ( F ( y ) θ ) = E [ F ( f + e ) θ ] = E [ F ( f ) f ( t k , δ ) ] = q

E ( θ n 2 ) = N σ f 2

其中, σ f 2 为采样值的方差,根据上述换元公式,可以将公式(6)简化表示为:

J ( w ) = N σ f 2 2 n = 1 N q w n + n = 1 N ( w n ) T p w n (8)

公式(8)给出的是在区域可信信息覆盖中对未部署点估计值的误差精度要求,也就是最终选出的传感器集合要满足给定的误差精度阈值。

然而,若仅仅只是根据估计值的误差精度来选择传感器集合是不完善的。因为存在这样的情况,假如根据公式(8)选出的传感器的剩余能量过低,可能导致节点在短时间内消耗完节点能力。为了延长网络生命周期,我们应该在选择传感器集合的时候同时考虑节点的剩余能量。

对于相同规格的传感器节点,其初始能量以及无线传送功率都是一定的,根据这两个已知量再结合采样频率,我们就可以得到各个时刻传感器节点的剩余能量。我们可以公式化剩余能量约束为:

w n λ i λ , n = 1 , , n (9)

其中 λ i 是第i个传感器的当前剩余能量, λ 为给定的剩余能量阈值。根据公式(9),我们可以将可信信息覆盖中的传感器选择问题公式化为0-1整数规划问题(10):

minimize w n 0 , 1 { J ( w ) = n = 1 N ( w n ) T p w n 2 n = 1 N q w n ϵ w n λ i λ , n = 1 , , n w n 1 (10)

3. 仿真实验

为了求解0-1整数规划问题,我们的实验平台为Matlab CVX工具箱 [12] ,也称之为SeDuMi [13] 。我们使用Inter Berkeley实验室的温度数据,通过部署54个传感器利用TinyDB收集了从2004年2月28号到4月5号的属性值。我们将区域中未部署点设置为δ = (3.5,13),并在δ周围部署7个传感器节点对温度值进行采样,7个节点的位置坐标分别为s1 = (0.5, 17),s2 = (1.5, 8),s3 = (1.5, 2),s4 = (4.5, 18),s5 = (5.5, 10),s6 = (5.5, 3),s7 = (8.5, 6)。

我们的优化目标是在满足误差精度阈值和剩余能量阈值的条件下,最小化传感器选择集合。表2显示了不同误差精度和剩余能量取值的选择结果,0表示不选,1表示选,−1表示无解。

图1显示了在特定剩余能量阈值( λ = 60 )的情况下,不同误差精度阈值的取值对网络生命周期的影响。可以看到,随着误差的放大,生命周期能够快速延长,但是增长都一定范围之后,剩余能量约束将抑制其增长速度。

最后,图2显示了当 ϵ = 10 ,剩余能量分别取 λ = 60 λ = 40 λ = 20 的取值时,本文考虑节点剩余能量的选择算法与不考虑剩余能量算法 [2] 对网络生命周期的影响。可以看到,本文提出的剩余能量约束条件能有效延长网络生命周期,大约是没有考虑剩余能量的2倍。

Figure 1. The error’s effect on the life cycle of the network

图1. 误差对网络生命周期的影响

Table 2. Nodes selection with different thresholds

表2. 不同阈值的节点选择

Figure 2. The network lifetime of our node selection algorithm is compared with algorithm [2] that does not consider the residual energy

图2. 本文考虑节点剩余能量的选择算法与不考虑剩余能量算法 [2] 的网络生命周期对比

4. 总结

本文针对区域监测应用中的传感器优化选择问题,引入剩余能量约束,避免选择剩余能量过低的传感器,延长网络寿命并保证监测值精度。我们提出了能量约束的传感器选择问题的优化求解方法,将传感器优化选择问题转化为0-1整数规划问题并求解最少传感器选择集合。利用Inter Berkeley实验室的温度数据进行仿真实验,并针对不同的插值方法进行了实验对比分析,在满足相同监测精度误差情况下,网络寿命延长了2倍以上,优于同类算法。

致谢

本文受到国家自然科学基金(61370087),浙江省重点研发计划(2017C01022)资助。

文章引用: 浦世亮 , 徐向华 , 杨建旭 (2017) 无线传感器网络中实现可信信息覆盖的能量感知的节点优化选择方法研究。 计算机科学与应用, 7, 1199-1205. doi: 10.12677/CSA.2017.712135

参考文献

[1] Liu, S., Chepuri, S.P., Fardad, M., et al. (2016) Sensor Selection for Estimation with Correlated Measurement Noise. IEEE Transactions on Signal Processing, 64, 3509-3522.
https://doi.org/10.1109/TSP.2016.2550005

[2] Kail, G., Chepuri, S.P. and Leus, G. (2017) Robust Censoring Using Metropolis-Hastings Sampling. IEEE Journal of Selected Topics in Signal Processing, 10, 270-283.
https://doi.org/10.1109/JSTSP.2015.2506142

[3] Wang, B., Deng, X., Liu, W., et al. (2013) Confident Information Coverage in Sensor Networks for Field Reconstruction. Wireless Communications IEEE, 20, 74-81.
https://doi.org/10.1109/MWC.2013.6704477

[4] Chepuri, S.P. and Leus, G. (2015) Continuous Sensor Placement. Signal Processing Letters IEEE, 22, 544-548.
https://doi.org/10.1109/LSP.2014.2363731

[5] Chepuri, S.P. and Leus, G. (2014) Sparsity-Promoting Adaptive Sensor Selection for Non-Linear Filtering. Proceedings of IEEE International Conference of Acoustics, Speech and Signal Processing (ICASSP), May 2014, 5100-5104.
https://doi.org/10.1109/ICASSP.2014.6854570

[6] Liu, S., Masazade, E., Fardad, M., et al. (2014) Sparsity-Aware Field Estimation via Ordinary Kriging. 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 3948-3952.
https://doi.org/10.1109/ICASSP.2014.6854342

[7] Jiang, F., Chen, J. and Swindlehurst, A.L. (2013) Linearly Reconfigurable Kalman Filtering for a Vector Process. 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 5725-5729.
https://doi.org/10.1109/ICASSP.2013.6638761

[8] Masazade, E., Fardad, M. and Varshney, P.K. (2012) Sparsity-Promoting Extended Kalman Filtering for Target Tracking in Wireless Sensor Networks. Signal Processing Letters IEEE, 19, 845-848.
https://doi.org/10.1109/LSP.2012.2220350

[9] Chepuri, S.P. and Leus, G. (2013) Sparsity-Promoting Sensor Selection for Non-linear Measurement Models. Processing IEEE Transactions on Signal, 63, 684-698.
https://doi.org/10.1109/TSP.2014.2379662

[10] Liu, S., Masazade, E. and Varshney, P.K. (2012) Temporally Staggered Sensing for Field Estimation with Quantized Data in Wireless Sensor Networks. IEEE Statistical Signal Processing Workshop (SSP), 512-515.
https://doi.org/10.1109/SSP.2012.6319746

[11] Liu, S.J., Vempaty, A., Fardad, M., et al. (2014) Energy-Aware Sensor Selection in Field Reconstruction. IEEE Signal Processing Letters, 21, 1476-1480.
https://doi.org/10.1109/LSP.2014.2342198

[12] Strum, J.F. (1999) Using SeDuMi 1.02, a MATLAB Toolbox for Optimization over Symmetric Cones. Optimization Methods & Sofware, 625-653.

[13] Grant, M., Boyd, S. and Ye, Y. (2006) CVX: Matlab Software for Disciplined Convex Programming. Global Optimization, 155-210.
https://doi.org/10.1007/0-387-30528-9_7

分享
Top