基于原始－对偶内点法的无线传感网平均数据流最优传输研究

谭 力 俞 腾 刘枝辰

（浙江工业大学信息工程学院，浙江杭州310023）

0 引言

无线传感器网络[1]是由大量的静止或移动的传感器节点以自组织和多跳的方式构成的无线网络，其目的是协作地感知、采集、处理和传输网络覆盖地理区域内感知对象的监测信息，并报告给用户。 无线传感网在环境、医疗、工业、建筑、空间和海洋探索以及军事上方面具有广泛的应用前景[2]。

其中数据路由[3]在无线传感网中显得十分重要，关键技术之一就是如何能够在完整传输所有数据流的情况下，如何尽可能的平均每一条链路上的数据流。

1 数学模型

图1 模拟的无线节点网络图

如图1 所示， 无线传感网抽象为有权图， 节点的数量用n 表示，V＝｛v1，v2，…，vn｝表示网络中节点所组成的非空集合；节点产生的数据用S 表示，即Sn表示第n 个节点产生的数据流；节点之间的链路用节点和节点之间的有向虚线线段表示，链路的集合用r 表示，rij表示第i 个节点向第j 个节点传输的数据流，r 表示所有数据流的平均，D（r）表示所有数据流的方差。 方差越大，表示数据流越不平均；反之，表示数据流越平均。

所以目标函数为：

为了优化分析的问题，并做如下假设：

a. 假设每一条链路所能承受的数据流大小存在一个极限值Rij，即：

b.假设所有的传感器节点都可以收发数据，同时传感器也会产生信息量，任意传感器节点的所收发的数据量等于与之相连的各条链路上的数据流之和，即

c.每个节点之间都可以进行双工通信，所以可以同时存在rij和rji两条链路，定义平均数据流：

将式（3）化成矩阵形式可得A*r≤B（6），其中r＝［r12，r23，…，rij，r］，A 为不等式的系数矩阵，B 为不等式的常数矩阵；由式（4），（5）可得C*r＝D（7），其中r＝［r12，r23，…，rij，r］，C 为等式的系数矩阵，D 为等式的常数矩阵。

综上所诉， 无线传感网的均衡路由问题可用以下的数学模型表示：

2 原始-对偶内点法求解平均数据流最优解

由上述可知，平均数据流最优解是一个非线性规划凸优化[4]问题。而原始-对偶内点法[5]是现代内点算法中最优秀的算法。它从理论上被证明具有多项式时间复杂性[6]。当约束条件和变量数目增加时，该算法的迭代次数随着系统规模的变化比较小、收敛速度快、精度高，适合求解大规模非线性系统[7]。 原始-对偶内点法求解非线性规划问题的步骤，可参考文献[8-9]。 而该问题满足原始对偶内点法的应用条件，所以可用原始-对偶内点法求解该问题，步骤如下：

Step0：初始化。 在任意取一组数据流数据r，只要满足f1（x）＜0，…，fm（x）＜0，λ≻0，μ＞1，εfeas＞0，ε＞0.，并且确定迭代的精度范围。 在这里初始化μ＝10，εfeas＝10-8，ε＝10-8；

Step1： 确定解决问题的目标函数的不等式方程和等式方程的系数。 在该问题中目标函数是式（1），不等式方程的系数是A，等式方程的系数是C；

Step3：列出一个矩阵方程，如下：

其中rdual＝Δf0（x）+Df（x）Tλ+ETv，rcent＝-diag（λ）f（x）-（1/t）1，rpri＝E-b；

Step4：计算Δy（Δx，Δλ，Δv）；

Step5：计算线长s＝min（1.0，0.99/max（-dλ/λ）），并满足s＞0；

Step6：更新y，使得y＝y+s*Δy；

3 仿真结果与讨论

3.0 初始化各个数据

内点法初始数据εfeas＝10-8，ε＝10-8，μ＝10，α＝0.01，β＝0.5， 图1 中各个节点的数据，以向量形式表示：S＝［9，7，-5，6，0，-3，-2，-4，-4，-4］。图2 所示横轴是次数，纵轴是迭代的值与最优解的差值；图3 所示横轴是次数，纵轴是迭代算出的值。

图2 迭代次数与目标解差值

图3 迭代次数与迭代算出的值

3.1 分析图2 和图3 得出如下结论

a.由图2 可知，求出的值与目标的最优解不断减小，说明该算法在上述初始条件下，是收敛的。且最后的差值在指定的误差范围内，验证了该算法的可行性。

b.由图3 可知，所求的最优解最后趋近于某一个数值，所以可以用这个值去非常近似的去代替真实的最优解，体现了原始对偶内点法的迭代。

3.2 比较

计算出的各个链路数据如图4 所示：

图4 仿真后的网络图

随机给出的各个链路数据如图5 所示：

图5 随机产生的网络图

通过对比最优解下的各个链路和随机解得各个链路得到如下现象：

a.最优解下的链路的最大值为15.9866，而随机解下的链路的最大值为17.5；同理，最优解最小值为4.4866，而随机解下的最小值为0.5；

b.最优解下存在的最大值链路只有1 条，最小值只有1 条；而随机解下最大值有3 条，最小值有3 条；

c. 最优解下平均的每条链路的信息量为8.9855， 大于随机解的8.0055。

综上所论，虽然求出的最优解的无线传感网的信息量可能大于随机解的无线传感网的信息量，即总体耗电量可能偏大；但是随机解中存在有很多的链路信息流很大，而其他链路信息流偏小，这样容易导致部分链路上的通信拥塞以及某些节点耗电量的增加，不利于整个无线传感网的维护。

4 结论

通过对上述10 个节点的拓扑图的仿真计算， 验证了用原始对偶内点法的可行性，所求出的解是收敛于真实的最优解。 并且证明了该算法可以求出在满足整个无线传感网数据流需求的情况下的平均数据流最优解。

而如果整个无线网络如果能尽可能的满足用该解法算出的结果，不仅能避免数据流在整个网络上的拥堵；同时也能够避免某几个节点由于传输大量数据而导致电量消耗过快而引起整个无线传感网无法正常工作的问题，提高了整个无线传感网的稳定性。

［1］崔莉，鞠海玲，苗勇，等.无线传感器网络研究进展[J].计算机研究与发展，2005，42(1)：763-774.

［2］杜磊，詹晓，刘曼.无线传感网应用现状[J].工会博览：理论研究，2011(11).

［3］樊凯，李令雄，龙冬阳.无线mesh 网中网络编码感知的按需无线路由协议的研究[J].通信学报，2009，30(1).

［4］范宏，韦化.基于扰动KKT 条件的原始一对偶内点法和分支定界法的最优潮流研究[J].电力自动化设备，May.2004 Vol.24 No.5:5-6.

［5］刘小兰，周密，何诣然.广义凸优化问题的Fenchel-Lagrange 对偶[J].四川师范大学学报(自然科学版)，Jan，2008 V01.31.No.1：31-32.

［6］李劲波，周理.基于仿射变换内点算法的大电网无功优化[J].电网技术，1997，21(3)：22-24.LI Jin.bo.Zhou Li.An affine transformation based interior point algorithm for bulk power System var optimization [J].Power System Technology，1997，21(3)：22-24.

［7］WEI H，SASAKH，KUBOKAWA J，et al.Large scale hydro—thermal optimal power flow problems based on interior point nonlinear pr0gramming [J].IEEE Transactions on Power Systems，2000，15(1)：396-403.

［8］WEI H，SASAKI H，KUBOKAWA J，et a1.An interior point nonllinear programming for optimal power flow problems with a novel data strutcture[J].IEEE Transactions on Power Systems，1998，13(3)：870-877.

［9］郭靖，陈青.电力系统无功优化的原对偶内点剪法及其应用[J].电力自动化设备，2004，24(5)：41-43.