Ad Hoc网络中基于偏转次梯度方法的功率和速率控制方法

摘要

本发明涉及无线自组织网络，即Ad Hoc网络。尤其涉及一种无线自组织网络的功率和速率控制方法。包括以下步骤1、获取Ad Hoc网络各个链路的信道带宽、噪声功率、发送功率上界；2、根据信道带宽、噪声功率、发送功率上界确定网络节点的传输功率、传输速度和权值；3、网络节点按照所述确定的传输功率、传输速度和权值进行功率和速率控制。

说明书

技术领域

本发明属于通信技术领域，涉及无线自组织网络，即Ad Hoc网络。尤其涉及一种无线自组织网络的功率和速率控制方法。 

背景技术

无线网络以有没有固定设施为标准划分成无线局域网(WLAN)和无线自组织网络(Ad hoc网络)。其中Ad Hoc网络的传送方式是对等式,并且动态地移动,所以其拓扑结构比较复杂和不稳定。与依靠中心节点、利用电缆或光纤为传输介质与其他终端节点直接交互信息的WLAN网络本质区别。正由于这些特性一般还称无线自组织网络为“移动多跳网”。 

Ad Hoc网络的产生可以追溯到20世纪70年代的美国,美国将其应用于军事领域进行数据的传送和接收,随着Ad Hoc网络的发展过程中参考了PRNET、SURAN和GloMo等项目的核心思想,得到了当今先进的组网技术。Ad Hoc网络的对应用环境的要求不高,即可随时随地组建网络,进行通讯。其方便快捷的网络服务吸引了其应用范围的扩宽。民用工业利用Ad Hoc技术将网络直接部署于没有硬件基础设施支撑下的环境如：建筑工地等。用户群可以通过它完成信息通讯进而进行协同工作。它的应用大致可以分为以下这几个方面：①临时会议的召开，②智能控制家庭网，③紧急通讯使用，④传感器功能，⑤军事战场上应用，⑥商业界应用。 

现代移动无线自组织网络是支持各种服务的综合性平台，每一种服务要求的传输速率和发送功率分配不尽相同。加之无线传输环境的多变性和复杂性因素，设计、优化和求解Ad Hoc网络模型已是当今研究的热点和难点所在。 

一个网络的好坏通常需要考虑网络的传输性能、低耗能和公平性三重指标，一个好的网络要求对功率、速率和权值进行综合完善。效用函数是描述整个网络性能的有效工具。对效用函数进行合理转化解释，结合实际环境，采用罚函数法对模型优化求解，根据求解结果优化整个网络。求解过程中可以将全局最优化转变为分布式最优化，在节点上执行最优化。方便在网络中的直接部署和应用。 

发明内容

以下给出简化的概述，为本文所描述的一些方面提供基本的理解。此概述不是所要求保护的主题的详尽综述，也不试图标识所要求保护的主题的关键/必需元素或描述所要求保护的主题的范围。其唯一的目的是以简化形式给出某些概念，作为稍后给出的更具体描述的序言。 

本发明的目的在于为Ad Hoc网络优化传输速率或发送功率，以满足网络系统公平性的要求。 

本发明在以发送功率或数据速率为指标的前提下，添加了保证公平性的权值。并且使用罚函数与次梯度方法对模型进行分层式地求解，根据求解结果对网络优化。本发明中的算法充分考虑到无线自组织网的结构和工作模式，形成了基于该算法的Ad Hoc网络中功率或速率控制方法。基于该算法的Ad Hoc网络中功率或速率控制方法能够周期地协调各个发送节点的功率、速率、优先权值，以比较快的收敛速率达到全网效用的最大值。 

本发明提供了一种Ad Hoc网络中功率控制方法，其特征在于包括以下步骤： 

步骤1：获取Ad Hoc网络各个链路上节点信道带宽、噪声功率、发送功率上界； 

步骤2：根据信道带宽、噪声功率、发送功率上界确定网络节点的传输功率、传输速度和权值； 

步骤3：网络节点按照所述确定的传输功率、传输速度和权值进行功率和速率控制。 

所述的功率控制方法在根据信道带宽、噪声功率、发送功率上界确定网络节点的传输功率、传输速度和权值时使用偏转次梯度方法进行计算获得。所述基于偏转次梯度方法的功率控制方法中无线自组织网络的效用函数的优化模型为： 

$\underset{m_s\le x_s\le M_s}{\max }\underset{s}{\Sigma }{U}_s(x_s,p_s,w_s)---\left(6\right)$

$s.t.\underset{s}{\Sigma }{x}_s\le c_l\left(p_s\right)---\left(7\right)$

0≤p_s≤p_max           (8) 

0≤w_s≤1              (9) 

x_s、p_s为用户s的速率和功率，w_s为用户的权值。通过上述优化模型实现对网络传输功率、传输速率和权值联合优化。 

将有约束的优化问题转换为无约束的问题求解，要继承原目标函数和各约束函数所有性能，其罚函数选取为： 

$B_{d_k}(x_s,p_s,w_s)=d_k\{\underset{l}{\Sigma }{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2+\underset{l}{\Sigma }{\left[\min (0,(p_{\max }-p_s))\right]}^2+$

$\underset{s}{\Sigma }{\left[\min (0,(1-w_x))\right]}^2\}---\left(10\right)$

式中，p_l表示在链路l上的功率调整；d_k表示罚因子，相应的增广目标函数： 

$F_{d_k}(x_s,p_s,w_s)=\underset{s}{\Sigma }U(x_s,p_s,w_s)+B_{d_k}---\left(11\right)$

分布式问题代替原本复杂的整个网络集中优化控制问题，其形式为： 

$F(x_s,p_s,w_s)=\max U_s(x_s,p_s,w_s)+d_k\{{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2+{\left[\min (0,(p_{\max }-p_s))\right]}^2$

$+{\left[\min (0,(1-w_s))\right]}^2\}---\left(12\right)$

对特殊的效用函数，直接分离他们之间的影响，函数(12)的变量分离简化，得到分别以x_s,p_s,w_s为单自变量的函数，即为： 

U(x_s,p_s,w_s)＝f(x_s)+g(p_s)+h(w_s) 

因而优化问题可分解为 

代表速率优化问题的： 

代表功率优化问题的： 

max g(p_s)+d_k[min(0,(p_max-p_s))]²

代表权值优化问题的： 

maxh(w_s)+d_k[min(0,(1-w_s))]²

的三类问题。 

效用函数为一般形式，但对每个变量的偏导数都存在，用解析的方法对效用函数进行整体优化求解； 

令 

$\frac{\partial F_{d_k}}{\partial x_s}=0$

$\frac{\partial F_{d_k}}{\partial p_s}=0$

$\frac{\partial F_{d_k}}{\partial w_s}=0$

通过选择d_k数列，由以上三条式子,并将k的值选取为趋于无穷大，进而解出x_s,p_s,w_s达到全无线网络最优化。 

Ad Hoc网络中基于偏转次梯度方法的功率控制方法，特征在于 

当与的所形成的夹角并不是锐角时，采用偏转的次梯度方法，按照以下步骤进行 

用偏转后的替换原来的次梯度方向其表达式可写为： 

${\overrightarrow{\mu }}^k={\overrightarrow{s}}^k+{\delta }_k{\overrightarrow{\mu }}^{k-1},{\delta }_k>0$

δ_k是一个偏转因子，它选取为： 

${\delta }_k=\left(\begin{array}{c}-{\tau }_k\frac{s^k{\overrightarrow{\mu }}^{k-1}}{{\left|\right|{\overrightarrow{\mu }}^{k-1}\left|\right|}_2^2},s^k,{\mu }^{k+1}<0\\ 0,\mathrm{otherwise}\end{array}\right)$

当k＝1时，由上式可知，偏转后次梯度不仅与次梯度相 关，还与上一次迭代所得的偏转次梯度相关，选取以后与的夹角比为锐角，τ_k为控制参数， 

其迭代公式相应地写成： 

${\overrightarrow{y}}^{k+1}={\overrightarrow{y}}^k+t^k{\overrightarrow{\mu }}^k$

能量，容量，优先权被链路l相对应的节点所接收，本地的节点s根据自身的信息来调整相关的值，从而达到F(x_s,p_s,w_s)函数最优解，即求得原问题的最优解。 

本发明的根据信道带宽、噪声功率、发送功率上界确定网络节点的传输功率、传输速度和权值具体步骤如下： 

第一步：无线Ad Hoc网络功率模型的建立； 

通常来说，无线自组织网络主要的节点有三类： 

①感知节点（发送数据，监测信息） 

②处理节点（数据融合，转发功能） 

③目的节点（传输目的地）。 

通常感知节点和处理节点采用的是TDMA接入方式。这种方式可以避免冲突，但是所带来的麻烦是必须重传多次才能确保传输成功。这样会造成无线节点消耗能量的浪费。无线自组织网络传输是按以下过程进行的。 

N表示无线节点集，L表示节点直接通信时存在的逻辑链路集，网络中用户s发送速率用x_s来表示，其中s∈N,x_s∈[m_s,M_s]，m_s和M_s分别表示用户s最小传输速率和最大传输速率，并要求m_s≥0,M_s≤+∞。本发明假定各个节点是独立发送数据的。对于网络链路l，其中l∈L，其信道容量记为c_l。显然每条链路的数据传输速率的总和应小于或等于其信道容量，因而有： 

$\underset{s}{\Sigma }{x}_s\le c_l(\forall l\in L).---\left(1\right)$

香农信息论认为，无论何种信道，有线，无线，恒参还是变参，各种物理信道都存在传送信息量的最大极限。香农信息论针对离散无 记忆信道，变量独立随机，存在高斯白噪声干扰下，其信道容量为： 

(2)式中，W表示信道带宽,S/N为信号能量功率/噪声能量功率，c_l表示l链路的信道容量。 

信道容量c_l是无差错传送的最高比特速率的理论极限，再由(1)，得 

其中c_l(p_s)为功率的容量函数。 

无线自组织网络发送数据都具有周期性，但由于数据在传输过程中，信号都是衰减，所以信号总是做一些相应的线性或非线性的变化，周期一般不高于一个设定值T。由于数据感知和处理的耗能量远小于在传输信道上的节点耗能量，所以可以忽略不算。每个节点总存在关系式 

T=E/p_s

其中T表示网络周期，E表示网络总能量，p_s表示节点发送数据的功率，再由(1)得： 

p_max＝E/T₀               (4) 

p_max为节点发送功率的上界，T₀为网络节点周期。 

基于无线自组织网络的资源有限，单一数据重传和抢占信道的问题，考虑用户群的满意度和提高传输吞吐率，为每个节点增带一个权值w_s，其中s∈N 

w_s＝T_wait/d 

其中T_wait为等待时间，d为传输信道的长度。通常用户能接受的等 待时间很短，而信道的长度却很长，所以 

0≤w_s≤1                 (5) 

本发明对网络传输功率、传输速率和权值联合优化，制定出相应的效用函数U_s，一般定义关于速率、功率和权值的对数函数。根据(1)-(5)式的各种约束条件。另外有几点特别说明：①数据在信道上传输速率的函数，通常是一个可导并且单调递增的凹函数。②网络被能量限制传输,要保证数据在一定的时间内在信道里生存，综合网络服务要求得到相应的满足，提高网络性能，功率应该是一个凸的非线性函数。 

通过上述综合的分析可得无线自组织网络的效用函数的优化模型为： 

$\underset{m_s\le x_s\le M_s}{\max }\underset{s}{\Sigma }{U}_s(x_s,p_s,w_s)---\left(6\right)$

$s.t.\underset{s}{\Sigma }{x}_s\le c_l\left(p_s\right)---\left(7\right)$

0≤p_s≤p_max                 (8) 

0≤w_s≤1                  (9) 

第二步：利用罚函数将约束最优化问题转换为无约束最优化问题； 

对上述问题进行优化，s节点的效用函数与速率、功率和权值都相互关联，若从实际网络出发，调整数据发送效率同时既要对以它为节点的所有数据转发的速率改变的实现可能性不大，所以本发明对问题优化和求解采用的是罚函数分布式优化算法使函数即整个网络得到最优化。 

模型(6)-(9)简化等价转化为： 

$\underset{m_s\le x_s\le M_s}{\max }\underset{s}{\Sigma }{U}_s(x_s,p_s,w_s)$

$s.t.c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s\ge 0$

p_max-p_s≥0 

1-w_s≥0 

为了求解方便，将有约束的优化问题转换为无约束的问题求解，要继承原目标函数和各约束函数所有性能，其罚函数可选取为： 

$B_{d_k}(x_s,p_s,w_s)=d_k\{\underset{l}{\Sigma }{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2---\left(10\right)$

$+\underset{l}{\Sigma }{\left[\min (0,(p_{\max }-p_s))\right]}^2+$

$\underset{s}{\Sigma }{\left[\min (0,(1-w_x))\right]}^2\}$

式中，p_l表示在链路l上的功率调整；d_k表示罚因子，相应的增广目标函数： 

$F_{d_k}(x_s,p_s,w_s)=\underset{s}{\Sigma }U(x_s,p_s,w_s)+B_{d_k}---\left(11\right)$

往后的求解中，由于物理意义不同，s和l有时相通使用。 

由(11)式，显然增广函数可分解为多个子函数，每个子函数可以看作单个本地优化问题。并且每个子优化问题只含有它自身的变量。所以求解原问题(11)的最大值，可以将自变量细化到每个本地源节点s上单独实现，因而分布式问题代替了原本复杂的整个网络集中优化控制问题，其形式为： 

$F(x_s,p_s,w_s)=\max U_s(x_s,p_s,w_s)+d_k\{{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2$

$+{\left[\min (0,(p_{\max }-p_s))\right]}^2+{\left[\min (0,(1-w_s))\right]}^2\}---\left(12\right)$

若对于特殊的效用函数，可以直接分离他们之间的影响。那么函数(12)的变量再可以分离简化。得到分别以x_s,p_s,w_s为单自变量的函数，即： 

U(x_s,p_s,w_s)＝f(x_s)+g(p_s)+h(w_s) 

因而优化问题可分解为： 

代表速率优化问题的： 

代表功率优化问题的： 

max g(p_s)+d_k[min(0,(p_max-p_s))]²

代表权值优化问题的： 

maxh(w_s)+d_k[min(0,(1-w_s))]²

的三类问题。 

第三步：基于偏转次梯度算法的最优功率和速率控制算法； 

若效用函数为一般形式，但对每个变量的偏导数都存在，可用解析的方法对效用函数进行整体优化求解。 

令 

$\frac{\partial F_{d_k}}{\partial x_s}=0$

$\frac{\partial F_{d_k}}{\partial p_s}=0$

$\frac{\partial F_{d_k}}{\partial w_s}=0$

可以通过选择d_k数列，由以上三条式子,并将k的值选取为趋于无穷大，进而解出x_s,p_s,w_s达到全无线网络最优化。 

以上两种方案都是优化问题时的简化，而效用函数模型(6)-(9)不可能都是可以被分解的，也不可能总是严格的凸函数。而经常是不可导或者分段可导的函数，对应的罚函数的目标增广函数也就不能按照以上方法进行求解。此处引入偏转次梯度算法求解. 

其中通常按照以下的方法进行迭代得到更好的解，设： 

$\overrightarrow{y}=(x_s,p_s,w_s)$

那么迭代公式可写成： 

${\overrightarrow{y}}^{k+1}={\overrightarrow{y}}^k+t^k{\overrightarrow{s}}^k$

式中是模型的解在k+1次迭代后的结果t^k是第k次的迭代步长，t^k可选取为： 

$0<t_k\le \frac{{\lambda }_k(F\left({\overrightarrow{y}}^{*}\right)-F\left({\overrightarrow{y}}^k\right))}{{\left|\right|{\mu }^k\left|\right|}_2^2}$

是F(x_s，p_s，w_s)在当前迭代点的次梯度，是步长t^k所沿的方向。 

当与的所形成的夹角并不是锐角时，次梯度算法对解迭代效果就不明显，收敛性显然变慢，形成一个I型的拉锯现象。为了解决这个问题Camerini提出偏转的次梯度方法，应用于本发明的求解可按照以下步骤进行。 

用偏转后的替换原来的次梯度方向其表达式可写为： 

${\overrightarrow{\mu }}^k={\overrightarrow{s}}^k+{\delta }_k{\overrightarrow{\mu }}^{k-1},{\delta }_k>0$

δ_k是一个偏转因子，它选取为： 

${\delta }_k=\left(\begin{array}{c}-{\tau }_k\frac{s^k{\overrightarrow{\mu }}^{k-1}}{{\left|\right|{\overrightarrow{\mu }}^{k-1}\left|\right|}_2^2},s^k,{\mu }^{k+1}<0\\ 0,\mathrm{otherwise}\end{array}\right)$

当k＝1时，由上式可知，偏转后次梯度不仅与次梯度相关，还与上一次迭代所得的偏转次梯度相关。这样选取以后与 的夹角比为锐角。τ_k为控制参数。 

其迭代公式相应地写成： 

${\overrightarrow{y}}^{k+1}={\overrightarrow{y}}^k+t^k{\overrightarrow{\mu }}^k$

能量，容量，优先权可被链路l相对应的节点所接收。本地的节点s可根据自身的信息来调整相关的值，从而达到F(x_s,p_s,w_s)函数最优解，即求得原问题的最优解。整个网络最优化。 

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

1.本发明基于优化理论提出了更适用于实际的网络拥塞控制公平性新模型，模型中加入了权值，保证系统的公平性； 

2.利用罚函数对模型进行求解，罚函数的优点是，适用于等式约束和非凸优化，并且初始点可以任意选取，可应用于全局极值的求解。在一般问题中免去了对偶的转化，使求解更加直接。本发明对罚函数的处理扩展到次梯度算法，为了它可以使Lagrange乘子的迭代方向与现有的次梯度方向形成锐角，将原来的迭代方向偏转，而得到偏转次梯度法。并分析了该算法的收敛性。 

3.仿真结果表明，本发明所提算法可以较快的收敛到最优值，具有很好的收敛性，并且保证了系统的公平性。 

为达成前述及有关目的，本文中联合以下描述和附图对所要求保护的主题的某些示例性方面进行描述。但是，这些方面仅指示可使用所要求保护的主题的各原理的各种方式中的若干种，并且该要求保护的主题试图包括所有的方面及其等效技术方案。当结合附图考虑时，其它优点和新颖特征将从以下具体描述中变得显而易见。 

附图说明

图1：α＝1所对应的最优功率示意图； 

图2：α＝2所对应的最优功率示意图； 

图3：α＝8所对应的最优功率示意图； 

图4：α＝1时三个用户的收敛性图像示意图； 

图5：α＝2时三个用户的收敛性图像示意图； 

图6：α＝8时三个用户的收敛性图像示意图； 

图7：α＝1时12个用户的收敛性图像示意图； 

图8：α＝2时12个用户的收敛性图像示意图； 

图9：α＝8时12个用户的收敛性图像示意图。 

具体实施方式

以下参照附图，给出本发明具体实施方式，对本发明做进一步说明。 

本发明对网络传输功率、传输速率和权值联合优化，制定出相应的效用函数，根据(1)-(5)式的各种约束条件。另外有几点特别说明：①数据在信道上传输速率的函数，通常是一个可导并且单调递增的凹函数。②网络被能量限制传输,要保证数据在一定的时间内在信道里生存，综合网络服务要求得到相应的满足，提高网络性能，功率应该是一个凸的非线性函数。 

通过上述综合的分析可得无线自组织网络的效用函数的优化模型为： 

$\underset{m_s\le x_s\le M_s}{\max }\underset{s}{\Sigma }{U}_s(x_s,p_s,w_s)---\left(6\right)$

$s.t.\underset{s}{\Sigma }{x}_s\le c_l\left(p_s\right)---\left(7\right)$

0≤p_s≤p_max           (8) 

0≤w_s≤1              (9) 

基于偏转次梯度方法的功率控制方法 

对上述问题进行优化，s节点的效用函数与速率、功率和权值都相互关联，若从实际网络出发，调整数据发送效率同时既要对以它为节点的所有数据转发的速率改变的实现可能性不大，所以本发明对问题优化和求解采用的是罚函数分布式优化算法使函数即整个网络得到最优化。 

模型(6)-(9)简化等价转化为： 

$\underset{m_s\le x_s\le M_s}{\max }\underset{s}{\Sigma }{U}_s(x_s,p_s,w_s)$

$s.t.c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s\ge 0$

p_max-p_s≥0 

1-w_s≥0 

为了求解方便，将有约束的优化问题转换为无约束的问题求解，要继承原目标函数和各约束函数所有性能，其罚函数可选取为： 

$B_{d_k}(x_s,p_s,w_s)=d_k\{\underset{l}{\Sigma }{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2+\underset{l}{\Sigma }{\left[\min (0,(p_{\max }-p_s))\right]}^2+$

$\underset{s}{\Sigma }{\left[\min (0,(1-w_x))\right]}^2\}---\left(10\right)$

式中，p_l表示在链路l上的功率调整；d_k表示罚因子，相应的增广目标函数： 

$F_{d_k}(x_s,p_s,w_s)=\underset{s}{\Sigma }U(x_s,p_s,w_s)+B_{d_k}---\left(11\right)$

往后的求解中，由于物理意义不同，s和l相通使用。 

由(11)式，显然增广函数可分解为多个子函数，每个子函数可以看作单个本地优化问题。并且每个子优化问题只含有它自身的变量。所以求解原问题(11)的最大值，可以将自变量细化到每个本地源节点s上单独实现，因而分布式问题代替了原本复杂的整个网络集中优化控制问题，其形式为： 

$F(x_s,p_s,w_s)=\max U_s(x_s,p_s,w_s)+d_k\{{\left[\min (0,(c_l\left(p_s\right)-\underset{s}{\Sigma }{x}_s))\right]}^2---\left(12\right)$

$+{\left[\min (0,(p_{\max }-p_s))\right]}^2+{\left[\min (0,(1-w_s))\right]}^2\}$

若偶遇非常特殊的效用函数，可以直接分离他们之间的影响。那么函数(12)的变量再可以分离简化。得到分别以x_s,p_s,w_s为单自变量的函数，即为： 

U(x_s,p_s,w_s)＝f(x_s)+g(p_s)+h(w_s) 

因而优化问题可分解为： 

代表速率优化问题的： 

代表功率优化问题的： 

max g(p_s)+d_k[min(0,(p_max-p_s))]²

代表权值优化问题的： 

maxh(w_s)+d_k[min(0,(1-w_s))]²

的三类问题。 

若效用函数为一般形式，但对每个变量的偏导数都存在，可用解析的方法对效用函数进行整体优化求解。 

令 

$\frac{\partial F_{d_k}}{\partial x_s}=0$

$\frac{\partial F_{d_k}}{\partial p_s}=0$

$\frac{\partial F_{d_k}}{\partial w_s}=0$

可以通过选择d_k数列，由以上三条式子,并将k的值选取为趋于无穷大，进而解出x_s,p_s,w_s达到全无线网络最优化。 

以上两种方案都是优化问题时的简化，而效用函数模型(6)-(9)不可能都是可以被分解的，也不可能总是严格的凸函数。而经常是不可导或者分段可导的函数，对应的罚函数的目标增广函数也就不能按照以上方法进行求解。此处引入偏转次梯度算法求解. 

其中通常按照以下的方法进行迭代得到更好的解，设： 

$\overrightarrow{y}=(x_s,p_s,w_s)$

那么迭代公式可写成： 

${\overrightarrow{y}}^{k+1}={\overrightarrow{y}}^k+t^k{\overrightarrow{s}}^k$

式中是模型的解在k+1次迭代后的结果t^k是第k次的迭代步长，t^k可选取为： 

$0<t_k\le \frac{{\lambda }_k(F\left({\overrightarrow{y}}^{*}\right)-F\left({\overrightarrow{y}}^k\right))}{{\left|\right|{\mu }^k\left|\right|}_2^2}$

是F(x_s,p_s,w_s)在当前迭代点的次梯度，是步长t^k所沿的方向。 

从参考文献^[13，14]得出这样的论断：当与的所形成的夹角并不是锐角时，次梯度算法对解迭代效果就不明显，收敛性显然变慢，形成一个I型的拉锯现象。为了解决这个问题Camerini^[10]提出偏转的次梯度方法，应用于本发明的求解可按照以下步骤进行。 

用偏转后的替换原来的次梯度方向其表达式可写为： 

${\overrightarrow{\mu }}^k={\overrightarrow{s}}^k+{\delta }_k{\overrightarrow{\mu }}^{k-1},{\delta }_k>0$

δ_k是一个偏转因子，它选取为： 

${\delta }_k=\left(\begin{array}{c}-{\tau }_k\frac{s^k{\overrightarrow{\mu }}^{k-1}}{{\left|\right|{\overrightarrow{\mu }}^{k-1}\left|\right|}_2^2},s^k,{\mu }^{k+1}<0\\ 0,\mathrm{otherwise}\end{array}\right)$

当k＝1时，由上式可知，偏转后次梯度不仅与次梯度相关，还与上一次迭代所得的偏转次梯度相关。这样选取以后与 的夹角比为锐角。τ_k为控制参数。 

其迭代公式相应地写成： 

${\overrightarrow{y}}^{k+1}={\overrightarrow{y}}^k+t^k{\overrightarrow{\mu }}^k$

能量，容量，优先权可被链路l相对应的节点所接收。本地的节点s可根据自身的信息来调整相关的值，从而达到F(x_s,p_s,w_s)函数最优解，即求得原问题的最优解。整个网络最优化。 

最优化功率算法的收敛性分析，解本模型，当使用罚函数解析法对模型进行求解时，我们假定了：(6),(7),(8),(9)式都是Rⁿ上的连续函数。 则由外点法产生的任何收敛序列的极限点必然是约束最优化问题的(6)-(9)的极小值。^[15]所以模型肯定收敛到其最优值。以下是其证明过程： 

假定以为极限，为模型(6)-(9)的最优解。由在可行域里，所以 

$U\left({\overrightarrow{y}}^{*}\right)=F({\overrightarrow{y}}^{*},d_k)$

又因为为的极大值点，得： 

$F({\overrightarrow{y}}^{*},d_k)\le F({\overrightarrow{y}}^k,d_k)$

所以 

$U\left({\overrightarrow{y}}^{*}\right)\le F({\overrightarrow{y}}^k,d_k)$

又因为$B_{d_k}\left({\overrightarrow{y}}^k\right)\le 0,$所以 

$F_{d_k}({\overrightarrow{y}}^k,d_k)=U\left({\overrightarrow{y}}^k\right)+B_{d_k}\left({\overrightarrow{y}}^k\right)\le U\left({\overrightarrow{y}}^k\right)$

所以 

$U\left({\overrightarrow{y}}^{*}\right)\le U\left({\overrightarrow{y}}^k\right)$

当k→∞时， 

$U\left({\overrightarrow{y}}^k\right)\le U\left({\overrightarrow{y}}^{-}\right)$

再证${\overrightarrow{y}}^{-}\in R:$

因为不增序列和均有大于极限值，令： 

$\underset{k\to \infty }{\lim }{F}_{d_k}({\overrightarrow{y}}^k,d_k)=\stackrel{-}{F}\ge f\left({\overrightarrow{y}}^{*}\right)$

$\underset{k\to \infty }{\lim }U\left({\overrightarrow{y}}^k\right)=\stackrel{-}{U}\ge U\left({\overrightarrow{y}}^{*}\right)$

又因为： 

$F_{d_k}\left(\overrightarrow{y}\right)=U\left(\overrightarrow{y}\right)+B_{d_k}\left(\overrightarrow{y}\right)$

$B_{d_k}\left(\overrightarrow{y}\right)=\frac{F({\overrightarrow{y}}^k,d_k)-U\left({\overrightarrow{y}}^k\right)}{d_k}$

$\underset{k\to \infty }{\lim }{B}_{d_k}\left({\overrightarrow{y}}^k\right)=\underset{k\to \infty }{\lim }\frac{F({\overrightarrow{y}}^k,d_k)-U\left({\overrightarrow{y}}^k\right)}{d_k}=0$

因为g_i和h_j都假定为连续： 

$B_{d_k}\left({\overrightarrow{y}}^{-}\right)=\underset{k\to \infty }{\lim }{B}_{d_k}\left({\overrightarrow{y}}^k\right)=0$

因为是模型(6)-(9)的极大值，所以有综上所述有 $U\left({\overrightarrow{y}}^{*}\right)=U\left({\overrightarrow{y}}^{-}\right),$即是极大值点。 

偏转次梯度算法优越于其他的迭代方法，因为它并不是以直角直接下降为某点的迭代方向，而是选取合适的迭代步长，夹角在90°以内，避免出现拉锯现象，保证了最终能收敛到最优解而不是在某个范围内徘徊。其证明为 

先证： 

${\overrightarrow{\mu }}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^{k+1})\ge 0$

${\overrightarrow{\mu }}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^{k+1})={\overrightarrow{\mu }}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)-{\overrightarrow{\mu }}^k({\overrightarrow{y}}^{k+1}-{\overrightarrow{y}}^k)$

$\ge s^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)-{\overrightarrow{\mu }}^k({\overrightarrow{y}}^{k+1}-{\overrightarrow{y}}^k)$

$\ge F\left({\overrightarrow{y}}^{*}\right)-F\left({\overrightarrow{y}}^k\right)-{\overrightarrow{\mu }}^k({\overrightarrow{y}}^{k+1}-{\overrightarrow{y}}^k)$

$\ge F\left({\overrightarrow{y}}^{*}\right)-F\left({\overrightarrow{y}}^k\right)-{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2{\left|\right|{\overrightarrow{y}}^{k+1}-{\overrightarrow{y}}^k\left|\right|}_2$

$=F\left({\overrightarrow{y}}^{*}\right)-F\left({\overrightarrow{y}}^k\right)-t_k{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2$

$\ge t_k{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2-t_k{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2$

$=0$

令UB_k为第k次迭代的估算上界，又由于δ_k和t^k的选取可得： 

${\overrightarrow{\mu }}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)\ge {\overrightarrow{s}}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)$

$\frac{{\overrightarrow{\mu }}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2}\ge \frac{{\overrightarrow{s}}^k({\overrightarrow{y}}^{*}-{\overrightarrow{y}}^k)}{{\left|\right|{\overrightarrow{s}}^k\left|\right|}_2}$

$\left|\right|{\overrightarrow{y}}^{k+1}-{\overrightarrow{y}}^{*}\left|\right|={\left|\right|{\overrightarrow{y}}^k+t_k{\overrightarrow{\mu }}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2$

$={\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{t_k}^2{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2+2t_k{\overrightarrow{\mu }}^k({\overrightarrow{y}}^k-{\overrightarrow{y}}^{*})$

$={\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{t_k}^2{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2+2t_k({\overrightarrow{s}}^k+{\delta }_k{\overrightarrow{\mu }}^k)({\overrightarrow{y}}^k-{\overrightarrow{y}}^{*})$

$={\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{t_k}^2{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2+2t_k{\overrightarrow{s}}^k({\overrightarrow{y}}^k-{\overrightarrow{y}}^{*})-2t_k{\delta }^k{\overrightarrow{\mu }}^{k-1}({\overrightarrow{y}}^k-{\overrightarrow{y}}^{*})$

$\le {\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{t_k}^2{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2+2t_k{\overrightarrow{s}}^k({\overrightarrow{y}}^k-{\overrightarrow{y}}^{*})$

$\le {\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{t_k}^2{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2+2t_k{\overrightarrow{s}}^k(F\left({\overrightarrow{y}}^k\right)-F\left({\overrightarrow{y}}^{*}\right))$

$\le {\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+\frac{{\lambda }_k^2{({\mathrm{UB}}_K-F\left({\overrightarrow{y}}^k\right))}^2}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2}$

$+2\frac{{\lambda }_k({\mathrm{UB}}_K-F\left({\overrightarrow{y}}^k\right))}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2}(F\left({\overrightarrow{y}}^k\right)-{\mathrm{UB}}_K)$

$={\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+\frac{{\lambda }_k^2{({\mathrm{UB}}_K-F\left({\overrightarrow{y}}^k\right))}^2}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2}-2\frac{{\lambda }_k({\mathrm{UB}}_K-F\left({\overrightarrow{y}}^k\right))}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2}$

$={\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|}_2^2+{\lambda }_k({\lambda }_k-2)\frac{({\mathrm{UB}}_K-F\left({\overrightarrow{y}}^k\right))}{{\left|\right|{\overrightarrow{\mu }}^k\left|\right|}_2^2}$

$<\left|\right|{\overrightarrow{y}}^k-{\overrightarrow{y}}^{*}\left|\right|$

上面的证明可看出，迭代点将逐步逼近最优值点，达到全局收敛的效 果。 

本节通过仿真实验验证算法的收敛性。考虑三个用户的系统,设置目标函数如下： 

$U\left(x_s\right)=\left(\begin{array}{c}\log x_s\alpha =1\\ {(1-\alpha )}^{-1}{x^{1-\alpha }}_s\alpha \ne 1\end{array}\right)$

公平性研究 

公平性是评价一个算法好坏的重要指标,它决定了在相同网络资源条件下,用户对网络资源的占有情况.我们首先令α＝1此时为比例公平性,然后让α＝2此时为调和平均公平性,在让α＝8两个值称为最大最小公平性,其仿真图形如图1,2,3.从图中我们看到随着α的增大,功率越来越趋向于同一个值,这也说明本发明所提算法满足公平性。 

收敛性比较 

收敛性是衡量系统性能的重要指标。本发明考虑2个系统：3个用户和12个用户的系统。图4给出了效用函数对应的系统效用收敛图像,从图中可以看出本发明所提算法比梯度算法和拟牛顿算法的收敛性都要好.从图5中可以看出，当α＝1，本发明所提算法的收敛性并不是最好的，因为这种情形是属于凸优化问题，拟牛顿方法会收敛更快一些。但当α＝2和α＝8，对应的优化问题为非凸优化，本发明所提算法要比梯度投影算法和拟牛顿算法都要更有效。 

当系统很大时，本发明所提算法仍有很好的性能，如图7，8，9所示。 

上述内容包括所要求保护的主题的若干示例。当然，出于描述所要求保护的主题的目的而描述各组件和方法的每一种可构想的组合是不可能的，但是本领域技术人员可认识到，许多其它的组合和变换是可能的。由此，所要求保护的主题旨在包含所有落入所附权利要求书的精神和范围之内的此类改变、修改、和变体。此外，在详细描述或权利要求书中使用术语“包括”的意义上，该术语意图如术语“包含”那样为包含性的，如“包含”在权利要求书中用作过渡词时所解释的。