一种基于次梯度投影的无线传感器网络资源分配优化方法

本发明涉及通信技术领域，尤指一种基于次梯度投影的无线传感器网络资源分配优化的实现方法。

无线通信技术正飞速发展并日趋成熟，运用无线通信技术进行数据采集、传输及通信的方案被广泛采用。无线传感器网络(Wireless Sensor Networks，WSN)是由无线通信技术组成的网络系统，集结了传感器、单片机和网络三大技术，通过采集、感知和处理网络覆盖范围内感知对象的传输数据，能实时监测、感知与传输网络所在区域信息，被广泛地应用于军事、国防、医疗、航空和工业等各个领域。无线传感器网络传输数据通过节点自组织和多跳的方式组网，节点具有双重功能，能进行数据采集和融合转发数据。节点把搜集到的数据信息以及接收到的来自其他节点的数据信息进行处理和融合，并把处理后的信息发送给用户，对信息的获取和处理带来了一种全新的方式，对未来信息时代的发展产生巨大的影响。

目前无线传感器网络技术仍处在快速发展阶段，低功耗和高性能是其发展方向之一。然而，由于节点的能量有限，使得传感器的寿命有限，那么，延长传感器的节点寿命，提高传感器节点能量的利用率是需要迫切解决的问题。由于无线传感器网络节点一般是用能量有限的电池来供电的，并且无线传感器网络所应用的环境通常来说都比较恶劣，所需能量较大，对于工作人员来说更换电池是极其困难，所以追求节点的低功耗称为了研究与设计无线传感器网络主要设计准则之一。在现有研究中，部分研究只考虑低功耗这一指标而降低传输功率，使得传输数据的准确度及传输距离等性能降低，有的提高了传输速率使得传输性能大大提高，但增加了功耗。本发明均衡无线传感器网络高性能与低功耗两需求，利用功率与速率两个指标对性能与功耗进行量化，建立性能与功耗相结合的模型，从而得出协调性能和功耗的最优功率与速率指标，从而能更加高效利用无线传感器网络中有限的能量资源。

为解决上述问题，本发明提出基于次梯度投影法的无线传感器网络资源分配最优化数学模型，并提出相应的资源分配优化方法，可有效减少网络系统的能量消耗，从而提高无线传感器网络性能和服务质量，主要包括以下步骤：

建立无线传感器网络资源分配最优化数学模型：

假设无线传感器网络是由K(k＝1,2,...,K)个传感器节点和L(l＝1,2,...,L)条链路组成的连通守恒系统。无线传感器网络能耗主要由两部分组成：第一部分是非发射设备和发射设备所产生的总耗能，分别记为Ee和Ea，当无线传感器节点传输数据时，节点传输数据的耗能Et可以表示为：

Et＝Ee+Ea

其中β为常数，R为该节点的传输半径，γ为所在路径的衰减因子，ηa为发射器的放大率；第二部分是传感器节点在单位时间内接收单位数据的总耗能，记为Er,满足：

其中Pk为传感器节点k进行传输数据的功率，xk为传感器节点k进行传输数据时的传输速率，U(xk)为xk的效用函数，代表用户的满意程度。因此得到当网络数据包长度为b时，节点单跳时所消耗的能量Etotal可表示为：

本发明考虑传感器节点每次成功地传输相应的数据所消耗的能量是不确定的，消耗的能量不仅与网络中触发事件的个数有关且与其竞争的节点个数也有关。当节点在1～T(T为总传输时间)之间随机等概率地选择一个时间点进行传输数据，那么节点选择时隙t进行数据传输的概率为：p(t)＝1/T。若共有k个相邻的节点在该点同时竞争信道，那么，传输节点在t时隙成功传输所要传输数据的可能概率psucc(t)为：

其中代表的是任意从K个节点中选取一个节点，p(t)代表的是选中节点在第t时隙来进行传输的概率，代表的是剩余的节点只能够选择t之后的时隙来传输数据，节点进行数据传输时，选择了t时隙进行传输。若信道比较拥挤，节点会选择避让。

数据在该机制下传输成功发送所消耗的总能量记为Etol，由此得到数据传输成功发送所消耗的总能量的期望值是：

其中Ebusy是传感器节点进入退避时状态共消耗的能量值。

功率控制是无线传感器网络节点能耗的重要方面，较低的功率能够提高网络系统容量、节省节点功耗和延长节点寿命，但过低功率也会导致通信质量下降，连接不可靠，所以有效实现功率控制是非常有必要的。数据的传输功率不仅可以大大地减小信号间的干扰，从而提高数据信号的传输的质量。节点数据的发射功率易受到与其相邻的节点总数量的影响。功率对物理层、MAC层及网络层都有一定的影响。所以本发明限制数据信息进行传输时产生的误码率不超过该系统能够承受的限定值，即每条链路上的信号噪声干扰比SIR必须大于限定值βl：

其中SIRl代表的是第l条链路上的信噪比；Gll代表第l条链路上的发送端到第m条链路的接收端所产生的链路增益，链路增益Gll与数据的传输距离d的α(α≥2)次方构成反比，用公式表示为：

其中υ为常量值；Pl是第l条链路上的平均的传输功率；σ2为接收的噪声功率，其主要来自于其他的链路造成的干扰总和。在物理层上功率的控制一般是为了减少造成的干扰，MAC上的功率控制常常是用来实现全网上传输功率达到最小化，以此来提高传感器节点能量效率。

无线传感器网络数据信息的传输，可以直接选择较大的功率来直接进行，也可以选择较小的功率，运用多跳的方式来进行传输，这两种方式的进行都会使得两个节点之间进行直接通信。在链路上的节点成功地接收来自其他节点所传输的数据对功率是有一定的要求的，设限定的节点k接收功率为Pk，成功地接收信息的最小发射功率Pmin满足：

其中γ代表路径衰落指数，κ为常数，则节点的发射功率P需要满足的条件为：

Pmin≤Pk≤Pmax

其中Pmax表示的是该节点的最大传输功率值。

若xk为传感器节点k∈K发送数据信息的速率，则有xk应该满足条件：xk＞0，同时也有Mk≥xk≥mk，其中Mk表示传输数据的最大传输速率，mk表示传输数据的最小传输速率。用cl来表示无线网络中链路l的信道容量，则有，对每一条链路来说，速率的和不能超过cl:

假设无线网络环境下的噪声为高斯加性白噪声，利用香农公式信道容量计算，用N0来表示信道上的功率谱密度，用W来代表所在信道的带宽，那么在高斯白噪声下相应的信道容量有：

由上式可得本发明所建最优化模型的速率约束为：

本发明充分考虑功率与速率两个性能指标，定义每个传感器节点k处的净效用为为达到优化速率和降低总功耗的目标，建立满足上述目标函数和约束条件的优化模型：

s.t.Pmin≤Pk≤Pmax

∑xk≤cl(P)

mk≤xk≤Mk

基于次梯度投影法的资源分配最优化方法

次梯度法是求解凸函数最优化问题的一种迭代法，与牛顿法和内点法等优化方法不同，次梯度法只需要很少的存储需求，并且能够可优化不可微的目标函数，但其收敛较慢。投影次梯度算法(projected sub-gradient method,PSM)是次梯度算法的一种扩展，具有次梯度的优点，且收敛速度较快，能够有效地求解带约束且在凸集上不可微的优化问题。当优化解沿着下降方向迭代时，可能会导致不可行的点，投影次梯度法通过对负梯度进行投影保证迭代可行性，从而得到最优解。

对于目标函数：

min f(x)

s.t.h(x)≤0

对应的次梯度投影算法的迭代公式为：

x(i+1)＝Pr(x(i)-αig(i))

其中，i＝1,...,I为迭代次数，Pr为集合上的投影值，g(i)为f在x(i)处的次梯度，表示f的次微分，αi代表步长，为更好地保证算法的收敛性，本发明将对步长进行改进。若当前点为可行点，则次梯度值为原目标函数的次梯度，否则值为不满足约束的函数的次微分。

基于次梯度投影的资源分配最优化方法步骤如下：

(1)任取初始点P0∈Rn,x0∈Rn和i＝0，i为迭代次数；

(2)构造拉格朗日函数L(x,P；λ,μ)；

(3)利用次梯度投影公式对所求量Pi和xi进行迭代；

(4)利用改进方法求步长αi；

(5)如果xi+1＝xi；Pi+1＝Pi，算法停止；否则，令i＝i+1，转步骤(3)，最终求出最优解Pi*和

与现有技术相比，本发明具有以下优点：

1.针对未来通信技术低时延和低功耗的要求，本发明充分考虑功率与速率两个指标，对性能与功耗进行量化定义，提出一种基于次梯度投影法的无线传感器网络的最优资源分配方法。为更好适应实际网络情况，模型考虑误码率约束、速率约束、功率约束和信道容量等符合实际网络情况的约束。

2.本发明所采用的次梯度投影法，存储需求少，能够有效地求解带约束且在凸集上不可微的优化问题。当优化解沿着下降方向迭代时，可能会导致不可行的点，投影次梯度法通过对负梯度进行投影保证迭代可行性，保持求解结果的准确性，降低了计算量，更适合具有不稳定性和大规模数据的无线传感器网络系统资源分配方法。

图1：本发明验证不同迭代次数下无线传感器网络资源分配方法对应的最优速率收敛示意图；

图2：本发明验证不同迭代次数下无线传感器网络资源分配方法对应的最优功率收敛示意图；

图3：本发明验证不同迭代次数下无线传感器网络资源分配方法对应的网络系统能耗收敛示意图。

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述。本实施基于次梯度投影法的无线传感器网络的最优资源分配方法，通过以下技术方案实现：

建立无线传感器网络资源分配最优化数学模型：

假设无线传感器网络是由K(k＝1,2,...,K)个传感器节点和L(l＝1,2,...,L)条链路组成的连通守恒系统。无线传感器网络能耗主要由两部分组成：第一部分是非发射设备和发射设备所产生的总耗能，分别记为Ee和Ea，当无线传感器节点传输数据时，节点传输数据的耗能Et可以表示为：

Et＝Ee+Ea

其中β为常数，R为该节点的传输半径，γ为所在路径的衰减因子，ηa为发射器的放大率；第二部分是传感器节点在单位时间内接收单位数据的总耗能，记为Er,满足：

其中Pk为传感器节点k进行传输数据的功率，xk为传感器节点k进行传输数据时的传输速率，U(xk)为xk的效用函数，代表用户的满意程度。因此得到当网络数据包长度为b时，节点单跳时所消耗的能量Etotal可表示为：

本发明考虑传感器节点每次成功地传输相应的数据所消耗的能量是不确定的，消耗的能量不仅与网络中触发事件的个数有关且与其竞争的节点个数也有关。当节点在1～T(T为总传输时间)之间随机等概率地选择一个时间点进行传输数据，那么节点选择时隙t进行数据传输的概率为：p(t)＝1/T。若共有k个相邻的节点在该点同时竞争信道，那么，传输节点在t时隙成功传输所要传输数据的可能概率psucc(t)为：

其中代表的是任意从K个节点中选取一个节点，p(t)代表的是选中节点在第t时隙来进行传输的概率，代表的是剩余的节点只能够选择t之后的时隙来传输数据，节点进行数据传输时，选择了t时隙进行传输。若信道比较拥挤，节点会选择避让。

数据在该机制下传输成功发送所消耗的总能量记为Etol，由此得到数据传输成功发送所消耗的总能量的期望值是：

其中Ebusy是传感器节点进入退避时状态共消耗的能量值。

功率控制是无线传感器网络节点能耗的重要方面，较低的功率能够提高网络系统容量、节省节点功耗和延长节点寿命，但过低功率也会导致通信质量下降，连接不可靠，所以有效实现功率控制是非常有必要的。数据的传输功率不仅可以大大地减小信号间的干扰，从而提高数据信号的传输的质量。节点数据的发射功率易受到与其相邻的节点总数量的影响。功率对物理层、MAC层及网络层都有一定的影响。所以本发明限制数据信息进行传输时产生的误码率不超过该系统能够承受的限定值，即每条链路上的信号噪声干扰比SIR必须大于限定值βl：

其中SIRl代表的是第l条链路上的信噪比；Gll代表第l条链路上的发送端到第m条链路的接收端所产生的链路增益，链路增益Gll与数据的传输距离d的α(α≥2)次方构成反比，用公式表示为：

其中υ为常量值；Pl是第l条链路上的平均的传输功率；σ2为接收的噪声功率，其主要来自于其他的链路造成的干扰总和。在物理层上功率的控制一般是为了减少造成的干扰，MAC上的功率控制常常是用来实现全网上传输功率达到最小化，以此来提高传感器节点能量效率。

无线传感器网络数据信息的传输，可以直接选择较大的功率来直接进行，也可以选择较小的功率，运用多跳的方式来进行传输，这两种方式的进行都会使得两个节点之间进行直接通信。在链路上的节点成功地接收来自其他节点所传输的数据对功率是有一定的要求的，设限定的节点k接收功率为Pk，成功地接收信息的最小发射功率Pmin满足：

其中，γ代表路径衰落指数，κ为常数，则节点的发射功率P需要满足的条件为：

Pmin≤Pk≤Pmax

其中Pmax表示的是该节点的最大传输功率值。

若xk为传感器节点k∈K发送数据信息的速率，则有xk应该满足条件：xk＞0，同时也有Mk≥xk≥mk，其中Mk表示传输数据的最大传输速率，mk表示传输数据的最小传输速率。用cl来表示无线网络中链路l的信道容量，则有，对每一条链路来说，速率的和不能超过cl:

假设无线网络环境下的噪声为高斯加性白噪声，利用香农公式信道容量计算，用N0来表示信道上的功率谱密度，用W来代表所在信道的带宽，那么在高斯白噪声下相应的信道容量有：

由上式可得本发明所建最优化模型的速率约束为：

本发明充分考虑功率与速率两个性能指标，定义每个传感器节点k处的净效用为为达到优化速率和降低总功耗的目标，建立满足上述目标函数和约束条件的优化模型：

s.t.Pmin≤Pk≤Pmax

Σxk≤cl(P)

mk≤xk≤Mk

基于次梯度投影法的资源分配最优化方法

次梯度法是求解凸函数最优化问题的一种迭代法，与牛顿法和内点法等优化方法不同，次梯度法只需要很少的存储需求，并且能够可优化不可微的目标函数，但其收敛较慢。投影次梯度算法(projected sub-gradient method,PSM)是次梯度算法的一种扩展，具有次梯度的优点，且收敛速度较快，能够有效地求解带约束且在凸集上不可微的优化问题。当优化解沿着下降方向迭代时，可能会导致不可行的点，投影次梯度法通过对负梯度进行投影保证迭代可行性，从而得到最优解。

对于目标函数：

min f(x)

s.t.h(x)≤0

对应的次梯度投影算法的迭代公式为：

x(i+1)＝Pr(x(i)-αig(i))

其中，i＝1,...,I为迭代次数，Pr为集合上的投影值，g(i)为f在x(i)处的次梯度，表示f的次微分，αi代表步长，为更好地保证算法的收敛性，本发明将对步长进行改进。若当前点为可行点，则次梯度值为原目标函数的次梯度，否则值为不满足约束的函数的次微分。

基于次梯度投影的资源分配最优化方法步骤如下：

(1)任取初始点P0∈Rn,x0∈Rn，设i＝0，i(i＝1,...,I)为迭代次数；

(2)构造本发明优化模型中的目标函数所对应的拉格朗日函数L(x,P；λ,μ)，如下式：

其中λ与μ分别为拉格朗日数乘子。

由此得到本发明中原优化问题目标函数所对应的对偶函数为：

min L(x,p；λ,μ)

s.t.Pmin≤Pk≤Pm

mk≤xk≤Mk

(3)利用次梯度投影公式对所求量进行迭代:

式子中α(i)与β(i)所代表的是迭代的步长，[λ1(i)-α(i)fl]+和[μk(i)-β(i)gk]+表示在其在非负实数集上面的投影值。

(4)利用改进方法求步长α(i)和β(i)，如下式：

(5)如果xi+1＝xi；Pi+1＝Pi，算法停止；否则，令i＝i+1，转步骤(3)，最终求出最优解Pi*和

经过分布式次梯度投影法的不断迭代，算法能够有效地控制各个节点数据传输速率及功率，最终使得节点能耗与发射速率的分配情况达到最优。

数值仿真

为了验证本发明方法的有效性,对本发明所提基于次梯度投影法的无线传感器能耗优化资源分配方法进行仿真实验。考虑无线传感器网络用户随机均匀分布在500m*500m的监测区域内，节点数为30，节点感知半径为25m,功率最大值为10mW，迭代次数设为I＝500。

将基于梯度方法(Newton Method)、次梯度方法(Quasi-Newton Method)和本发明所提次梯度投影方法(BFGS Method)进行比较，如图1、2所示,给出了不同迭代次数下不同方法获得的最优传输速率和功率，可以看出本发明所提方法存储需求小，对目标函数要求不严使得每步迭代计算量减少，克服了次梯度法收敛速度慢和梯度对目标函数要求严的缺点，从而使得求解结果较次梯度法和梯度具有更高的准确性和更高的效率。图3给出了不同方法所对应的系统能耗，可以看出由于本发明所提方法在优化解沿着下降方向迭代时，对负梯度进行投影保证迭代可行性，从而使得所提资源分配最优化方法具有更优的性能，有效降低了网络能耗。