[0094] 下面结合附图对本发明实施例作详细说明，图1为本发明的流程图。
[0095] 以最大化网络整体效用为目标函数，联合拥塞控制、路由及功率分配的优化模型为：
[0096]
[0097]
[0098]
[0099]
[0100]
[0101] 其中，Uf(sf)为效用函数，表示业务流f的源速率为sf时，网络能够获得的效用；约束条件(2)为节点流平衡约束，对于网络中的任意节点n(除了业务流的目的节点)，它产生的速率与其输入链路的速率之和不能大于其输出链路的速率之和， 表示业务流f在链路l上的链路速率，I(n)表示节点n的输入链路集合，O(n)表示节点n的输出链路集合，当节点n是业务流f的源节点时，1f(n)等于1，否则为0；(3)为信道容量约束，流经链路的业务流速率之和不能超过它的信道容量，Cl(pl)表示链路l传输功率为pl时的信道容量；(4)为节点功率约束，节点分配给输出链路的功率之和不能超过节点最大发送功率 (5)为业务流速率和链路功率的非负性约束；
[0102] 业务流f在节点n处的队列长度变化如下：
[0103]
[0104] 式中，t为时隙下标，(*)+＝max{0,*}， 表示实际的速率， 因为Tx(l)处能够传输的数据量可能会少于分配的 令 表示时隙t时所有缓存区内的队列长度。
[0105] 所有的信道都用路径损耗指数α的大尺度衰落和小尺度瑞利衰落建模，链路l的信噪比可以写为 式中，dl为链路l的距离，hl为信道增益系数，pl表示链路l的噪2
声归一化发送功率，|hl|服从均值为1的指数分布。因此链路l的信道容量为
[0106]
[0107] 其中B为信道带宽。
[0108] 引入松弛变量 vl，λn将优化问题中的不等式约束条件(2)‑(5)转化为等式约束条件，对于松弛变量 规定n≠Dst(f)。对于大于零的约束，采用对数障碍函数，将其加入到目标函数中，最后通过牛顿法进行求解。于是，重构的优化问题为：
[0109] min fμ(y) (8)
[0110]
[0111]
[0112]
[0113] 其中，原始变量
[0114] 其包含了全部的源速率、链路速率、链路功率以及所有的松弛变量。
[0115]
[0116] 是障碍目标函数，μ＞0为障碍函数惩罚因子。
[0117] 如图2a所示，考虑一个节点功率受限的无线多跳网络，网络拓扑G＝{N,L}，N,L分别表示网络节点集合与链路集合，网络节点数目|N|＝N，网络链路数目|L|＝L，网络中有F个端到端的业务流，业务流集合为F，对于每条业务流f∈F，分别用Src(f)和Dst(f)表示其源节点和目的节点，且Src(f)不等于Dst(f)。网络中的链路是双向的，业务流能够从源节点(f) (N‑1)×L通过多跳及多径路由将数据传输到目的节点。定义节点‑链路关联矩阵A ∈R ,和节点‑流向量
[0118]
[0119]
[0120] 其中Tx(l)表示链路l的发射节点，Rx(l)表示链路l的接收节点。
[0121] 定义网络拓扑信息矩阵
[0122]
[0123] 矩阵内元素定义如下：
[0124] (1)B＝Diag{b(1),...,b(F)}∈R(N‑1)F×F；(N‑1)F×FL
[0125] (2)A＝[A1,...,AL]∈R ，其中 Diag{*}表示对角(f)
化，向量 是节点‑链路关联矩阵A 的第l列(即 )；
[0126] (3)Ru＝Diag{11×F,...,11×F}∈RL×LF；
[0127] (4)
[0128] (5)I0∈R(N‑1)F×(N‑1)F，I1∈RL×L，I2∈RN×N，均为单位矩阵；
[0129] (6)规定1n×m表示维数为n×m的全1矩阵，0n×m表示维数为n×m的全0矩阵，简便起见，部分右上角未标维数的全1或全0矩阵，其维数可根据上下文决定。定义表示链路信道容量和节点最大功率的限
制。Cl表示链路l的信道容量。
[0130] 基于上面定义的矩阵，约束条件(9)(10)(11)可联合表示成矩阵形式约束：
[0131] My＝e (13)
[0132] 由于定义的矩阵中去掉了n＝Dst(f)所在的行，因而网络拓扑信息矩阵M是行满秩矩阵。
[0133] 给定一个初始可行的原始变量y[0]，采用牛顿法得到集中式算法迭代更新式为：
[0134] y[t+1]＝y[t]+π[t]Δy[t] (14)
[0135] 其中，π[t]是迭代步长，Δy[t]是原始变量的牛顿方向，通过求解下面的由重构优化问题KKT条件构成的非线性系统得到：
[0136]
[0137] 其中， 表示fμ(y[t])的梯度向量， 表示fμ(y[t])的Hessian矩阵； w[t]是对偶变量，内部元素如下：
[0138]
[0139] 其中，
[0140] (1) n≠Dst(f),与流平衡约束相关联，表示节点拥塞价格；
[0141] (2) 与链路信道容量约束相关联，表示链路拥塞价格；
[0142] (3) 与节点功率约束相关联，表示节点功率价格。
[0143] 求解式(15)分别得到原始变量的牛顿迭代方向和对偶变量的更新式：
[0144]
[0145]
[0146] 其中，
[0147] 根据障碍目标函数的定义式(12)，得到：
[0148] fμ(y[t])的梯度向量：
[0149]
[0150] 其中，矩阵内元素结构如下：
[0151] (1)
[0152] (2)
[0153] (3)
[0154] fμ(y[t])的Hessian矩阵：
[0155]
[0156] 矩阵内元素结构如下：
[0157]
[0158]
[0159]
[0160] 对于向量e[t]，根据信道容量表达式(7)有：
[0161]
[0162]
[0163] 式中，
[0164] 分别表示信道容量关于链路功率一阶导数和二阶导数；
[0165]
[0166] 因此， 能够表示为下面的对角结构：
[0167]
[0168] 内的矩阵都是对角矩阵，所以 的逆矩阵很容易分布式求得，只需要对内部元素求逆即可。
[0169] 因此结合(17)式得到业务流源速率、链路速率、链路功率及松弛变量牛顿方向的分布式更新公式如下：
[0170]
[0171]
[0172]
[0173]
[0174]
[0175]
[0176] 对偶变量计算式(18)中，G[t]不具有对角结构，因此需要收集整网的速率、功率及信道状态信息等才能够计算出其逆矩阵。为了实现对偶变量的分布式计算，我们首先将式(18)变形为下列线性方程组：
[0177]
[0178] 将G[t]分裂为 其中Φ[t]＝diag{G[t]}，表示由G[t]对角元素构成的对角矩阵，Ω[t]＝G[t]‑Φ[t]，表示去掉G[t]对角元素后剩余的非对角部分，是一个对角矩阵，其对角元素 表示Ω[t]的各行元素绝对值之和。
是一个用于调节收敛速度的参数。则w[t]可以通过下面的迭代公式进行求解：
[0179]
[0180] 当k→∞时，式(32)收敛至
[0181] Φ[t]的对角结构(下文省略时隙下标[t])：Φ＝Diag{ΦA,ΦB,ΦC}，其中，[0182] (1)ΦA∈R(N‑1)F×(N‑1)F:
[0183]
[0184]
[0185] (2)ΦB∈RL×L:
[0186]
[0187]
[0188] (3)ΦC∈RN×N:
[0189]
[0190]
[0191] 的对角结构(下文省略时隙下标[t])： 其中，
[0192] (1)
[0193]
[0194]
[0195] 规定
[0196] (2)
[0197]
[0198]
[0199] 其中，
[0200]
[0201]
[0202]
[0203] 根据式(32)和G[t]的分裂结果，得到节点拥塞价格 链路拥塞价格 和节点功率价格 的分布式更新公式：
[0204]
[0205]
[0206]
[0207] 根据上述迭代公式可以看出，网络节点在计算节点拥塞价格 链路拥塞价格和节点功率价格 时，所需要的信息来自节点本身、节点收发链路以及与节点相连的一跳邻居，即意味着只需单跳信息交互。
[0208] 式(14)中的迭代步长π[t]计算如下：
[0209] π[t]＝(1+λ(y[t]))‑1 (36)[0210] 式中， 称为牛顿减量。由于H[t]是对角矩阵，于是牛顿减量可以在各节点分布式计算：
[0211]
[0212] 各节点将计算结果广播给其他节点，最终计算获得λ(y[t])。
[0213] 因此在每个时隙，业务流源速率、链路速率以及链路功率及松弛变量的更新式为：
[0214] sf,[t+1]＝sf,[t]+π[t]Δsf,[t] (38)[0215]
[0216] pl,[t+1]＝pl,[t]+π[t]Δpl,[t] (40)[0217]
[0218] vl,[t+1]＝vl,[t]+π[t]Δvl,[t] (42)[0219] λn,[t+1]＝λn,[t]+π[t]Δλn,[t] (43)[0220] 当λ(y[t])≤ε时，更新惩罚因子μ＝kμ(k＞1)，如果μ→∞，则停止迭代，各节点按照优化结果对网络进行配置；否则t＝t+1，继续更新。
[0221] 图2a显示了一个简单的无线多跳网络的逻辑拓扑。网络中有6个节点，2条业务流，网络中的链路是双向的。业务流1的源节点为N1，目的节点为N6；业务流2的源节点为N2，目的节点为N5。图2b和图2c分别显示了业务流1和业务流2的最终速率分配结果以及节点缓存区队列积压情况。
[0222] 图3比较了所提出的方法与原始对偶一阶方法以及新型背压方法的网络效用，从图中可以看出，所提出的方法在大约200个时隙就达到收敛，相对于另外两种算法在大约900个时隙收敛，收敛速度大幅提升，并且由于所提出的方法对链路功率进行了优化，解决了在固定功率分配下的链路拥塞瓶颈，使得网络效用有所提升。
[0223] 图4比较了所提出的方法与原始对偶一阶方法以及新型背压方法的能量效用，从图中可以看出，所提出的方法优化功率分配后，降低了不必要的功率消耗，能量效用提升了24.68％。
[0224] 图5比较了所提出的方法与原始对偶一阶方法以及新型背压方法的网络平均队列长度，所提出的算法的平均队列长度最低，很好地控制了队列积压，这也意味着网络延时较低。
[0225] 以上对本发明的优选实施例及原理进行了详细说明，对本领域的普通技术人员而言，依据本发明提供的思想，在具体实施方式上会有改变之处，而这些改变也应视为本发明的保护范围。
