基于I-Greedy求解CVaR模型的传感器网络布局优化

高安迪，吴晓霞，李 峰

（1.河北机电职业技术学院，信息工程系，河北 邢台 054000；2.河北科技大学，信息科学与工程学院，河北 石家庄 050018）

1 引言

无线传感器网络在机械设备状态监测领域有着重要的作用，是工业自动化制造水平高低的一个重要标准。在构建无线传感器网络的过程中，需要合理设置布局以获得最优节点位置与传感器个数，从而实现目标区域的监测功能，这已经成为无线传感器应用的一项关键内容，对网络监测的准确性起到了决定作用［1-3］。进行信息提取时，当构建传感器网络后可以实现对所在区域的多个感知节点进行全面监测，从而获得更全面的位置信息，经过不同位置的信息融合后达到比单路以及多路方法更高价值的信息。并且随着节点部署数量的增加，传感器网络对目标区域的感知能力也越强［4-5］。

传感器节点运行过程中需消耗能量的部分主要包括信息采集以及数据传输二个过程。其中，进行数据传输时，涉及功率调节、信道传输、睡眠—激活控制等环节。MAC层是调度享信道传输过程的主要部位，该层结构属于可以实现物理层与网络层数据转换的连接部分，由此万网络数据的直接调控，信道能耗以及传输损耗情况受到该层控制性能优劣性的直接影响［6-8］。现阶段，基本都是以信道介质来完成控制协议的访问功能，可以将在各时刻下对网络包含的节点按照多信道方式实施通信，从而对各类资源达到充分利用的作用［9-10］。随着传输协议效率的提高，维护过程所需的资金也明显增加，而实际获得网络寿命延长并未达到理想的程度，这就要求针对各项参数采集进行传感器调度的过程深入分析。例如对系统运行数据实施采集的过程中先调度传感器，再通过对各类节点数据进行分组实现特定区间内的数据收集［11］。文献［12］利用高斯概率模型仿真测试传感器网络的感知过程，并专门利用概率感知模型确定了传感器的合理调度方案：在确保可以满足传感器网络测试要求的情况下，数据采集过程中进行传感器网络分组来实现更长的网络使用时间。无线传感器网络在机械设备状态监测领域有着重要的作用，为了解决传统随机优化方法不适合某些复杂场传感器网络布局景的问题，提出了一种基于IGreedy求解CVaR模型。

2 基于CVaR布局模型

2.1 基于CVaR布局模型

考虑到部署过程受到不确定性的影响，函数值除了会受到子集S的影响之外，外部条件也会对其造成干扰，此时构建的效益函数内包含了与最优子集S存在独立联系的变量y，对布局状态造成较大影响。把存在不确定性因素的布局模型表示为下述的形式：

根据CVaR判断损失情况，将CVaR加入模型内，以其表示处于最差状态下形成的互信息均值，包含不确定节点的情况下，布局过程形成了最大CVaR，使布局过程产生明显鲁棒性。以下是根据CVaR构建的布局模型：

对CVaRα(S)进行优化时选择辅助函数H(S，τ)的方式来实现，将其转变成优化S与τ的辅助函数H(S，τ)，由此得到以下的表达式：

2.2 改进算法性能分析

Kf表示效用函数的曲线斜率，以贪婪算法确定解集子模效用函数f并计算最优解OPT解集S*子模效用函数H(S，τ)表达式如下：

以非标准化单调子模函数H(S)，τ完成归一化后再代入式（4）中可以得到：

对以上式子转换后得到：

利用式（6）计算出各个τi对应的最优解集

设定上界条件：

对于τ=τi，通过搜索间隔Δ完成求解过程，计算得到结果跟最优解集H(，τ*)之间满足下述关系：

把式（10）代到式（11）中可以得到：

根据以上式子，利用I-Greedy算法计算得到解集(SG，τG) 和最优解(S*，τ*)的对应关系如下：

2.3 I-Greedy算法

为简化算法时间复杂度，采用惰性赋值的方法完成算法的简化过程。式（6）表示模型目标函数，算法性能受到参数τ的明显影响，为确定最优解，为τ设置了相应的搜索间隔Δ和搜索区间（0，Γ），之后完成有序搜索，防止算法出现局部最优解的情况。通过惰性赋值的方式实现快速搜索的功能。由此得到以下的IGreedy算法的实现过程：

（1）设定τ搜索范围介于（0，Γ）区间内，各参数依次为置信水平α、间隔Δ、地集V、约束条件I，经初始化得到空集。

（2）根据Δ对搜索范围中的τ实施搜索，对符合约束条件I的集合点从中选择达到最大效益的元素组成最优解，通过惰性赋值的方式提升搜索效率。

3 仿真结果分析

3.1 实验步骤

进行布局优化时需满足二个目标，包括获得良好布局效果以及降低网络不确定性引起的损失。根据互信息评价布局效果，当传感器网络受不确定印刷影响造成的损失通过计算损失量实施评估。同时设计对比实验分析该算法是否满足有效性。以下为各实验步骤：

（1）从80个备选点中选择40个组成部署参数集合，并对该集合进行测试。

（2）以Matlab构建仿真模型，对不同类型的传感器布局形式开展仿真处理，通过判断参数τ的置信水平α确定最优结果。

（3）对各算法对比差异性，对相同条件下的各算法互信息、不确定因素损失与时间复杂度进行测试。

3.2 参数引起的解集变化分析

图1（a）显示，在一个任意置信水平α下，设定上限Γ，利用这里的算法按照步长等于1的条件由0至上界Γ有序搜索，最终可以获得局部最优解。并且随着Γ的增大，便可以得到与全局最优解更接近的局部最优解，因此需尽量提高Γ的值。根据互信息评估布局效果，图1（a）分析发现，τ搜索上界Γ设定成50时，能够确保各置信水平搜索后得到全局最优解。

图1 参数τ和α对H（SG）的影响Fig.1 Effect of τ and α on H（SG）

根据图1（b）可知，以不同置信水平α计算得到的最大效益存在一定的差异性。保持固定参数τ的条件下，对比各个置信水平α下计算得到的效益H可以发现，提高置信水平α之后，根据最优解计算的布局效益H也持续提高。

为进一步增加传感器网络效益，计算得到的最终解为α=0.9的部署集合SG0。

3.3 算法互信息对比

为了对I-Greedy算法进行有效性验证，在设置同样传感器节点数的条件下分别测试了贪婪算法、随机部署算法与这里的算法部署结果与效益。

首先针对各算法设计了布局示意图。从图2（a）中可以看到，按照随机方式部署传感器节点时，形成了无序的位置分布状态，中间区域几乎不包含部署节点，无法获得理想的布局结构。采用传统贪婪算法处理时，可保证目标区形成均匀分布的数据，并且还需为目标区域靠近边缘的部位设置大量节点，导致大量的资源浪费，实际并不能达到布局效益的有效提升。图2（c）显示，设计算法的节点在目标区域内形成了均匀分布的形态，同时降低了边缘位置的节点数量，布局效益获得了明显提升。

图2 传感器网络布局Fig.2 Layout of Sensor Networks

利用互信息评价传感器网络布局性能。逐渐增加传感器的节点数情况下，获得了更高的布局效益，当目标区中部署了40个传感器节点时，以三种不同部署算法获得的互信息依次是33、29与18，以这里算法计算获得的互信息比随机部署方法提升67%，同时比传统贪婪算法提高14.3%，由此判断以该算法能够达到理想布局的效果，如图3所示。

图3 传感器网络信息增益Fig.3 Information Gain of Sensor Networks

3.4 模型损失对比

根据表1 结果可以发现，传感器网络存在不确定风险时，CVaR布局模型相对传统布局模型可以达到更低损失程度，由在不确定条件下，该模型能够获得更优布局结果，提升了模型鲁棒性。

表1 模型损失对比Tab.1 Model Loss Comparison

3.5 算法时间复杂度对比

分析表2可以发现，不管出于何种网络规模下，I-Greedy 算法的z都比传统贪婪算法更小，并且增加传感器网络规模后，IGreedy算法效率也发生了持续升高。这里研究结果表明，新设计的算法能够显著降低时间复杂度，特别是进行大规模传感器布局时表现出了更强的优越性。

表2 时间复杂度对比Tab.2 Time Complexity Comparison

4 结论

（1）τ搜索上界Γ设定成50和置信水平α=0.9时，能够确保各置信水平都搜索获得全局最优解。

（2）逐渐增加传感器节点数量后，布局效益获得了持续提升。计算得到互信息相对随机部署方法增加69%，与传统贪婪算法相比增加14.1%。

（3）CVaR布局模型相对传统布局模型可以达到更低损失程度，能够获得更优布局结果，提升了模型鲁棒性。

（4）算法能够显著降低时间复杂度，特别是进行大规模传感器布局时表现出了更强的优越性。