一种无线多跳网络的集中式优化分配方法   0    0

本发明公开了一种无线多跳网络的集中式优化分配方法。该方法包括初始化阶段、信息收集阶段、模型建立阶段、模型求解阶段、集合投影阶段、控制消息分发阶段和重启动阶段。该方法在网络中业务流路由确知的情况下，以最大化网络效用为目标，利用原始对偶内点法对模型进行求解，获得原始及对偶变量的牛顿方向用于迭代更新。由于在牛顿方向的更新过程中需要使用到全局的诸如节点功率、源节点发送速率等信息，所以需要在控制中心节点处统一计算处理。

1.一种无线多跳网络的集中式优化分配方法，其特征在于，该方法的步骤如下：
步骤一：初始化阶段：控制中心节点通过周期性“HELLO”消息的交换，获得本网络的拓扑信息，并根据最短路径路由算法周期性更新本网络路由表；
步骤二：信息收集阶段：控制中心节点周期性收集网络中所有节点的基本配置信息，包括信道带宽、是否业务流的源节点以及节点功率上界，并根据所获取的参数信息整理成已知参数库，更新源速率和功率更新可行域；
步骤三：模型建立阶段：控制中心节点建立系统优化模型；
步骤四：模型求解阶段：控制中心节点运用原始对偶内点法分别求得：
1)由业务流速率和链路功率构成的原始变量的更新公式；2)由链路拥塞价格和节点功率价格构成的对偶变量的更新公式；
步骤五：集合投影阶段：若步骤四中的更新结果超出了可行域，则根据集合投影的方法对结果进行调整；
步骤六：控制消息分发阶段：当原始变量与对偶变量更新至收敛后，控制中心节点将计算结果发送给网络中的各节点，各节点按照要求分配业务流速率和链路功率；
步骤七：重启动阶段：若网络拓扑发生改变或者有新的业务流加入，重新开始进入步骤一初始化阶段；否则，一直按照当前分配值运行系统；
所述步骤三的优化模型为：
约束条件为式(2)、(3)、(4)和(5)：
其中，U(fs)为效用函数，表示业务流的源速率为fs时，业务流s获得的效用；n和l分别表示网络节点集合与链路集合，网络中有S个端到端的业务流，cl(pl)为链路l发送功率为pl时的信道容量，B为信道带宽，L(s)表示业务流s的传输路径，O(n)表示节点n的输出链路集；
约束条件：(2)为链路信道容量约束，流经链路的业务流速率之和不能超过链路的信道容量；(3)为节点功率约束，节点分配给输出链路的功率之和不能超过节点具有的最大发送功率 (4)为业务流速率和链路功率的非负性约束；(5)为信道容量定义式，假设所有的信道都用带有路径损耗指数α的大尺度衰落和小尺度瑞利衰落建模；那么链路l的信噪比可以写为 式中，dl为链路l的距离，hl为信道增益系数，pl表示链路l的发送功
2
率，|hl|服从均值为1的指数分布；
T
所述步骤四的具体步骤为：定义原始变量y＝[f1,...,fS,p1,...,pL]表示所有的业务流速率和链路功率变量，利用障碍函数法将优化问题转化为无约束的优化问题，得到重构的最小化问题：
为障碍目标函数，其表达式为：
其中μ为障碍函数惩罚因子，用于调整与原优化问题的近似程度，μ越大，重构的优化问题的最优解与原问题的最优解越接近；
对障碍目标函数 进行求导，并令导数为0得到：
其中，当链路l在业务流fs的路由上时，1s(l)＝1，否则为0；
根据原始对偶内点法，定义对偶变量 和
分别表示链路拥塞价格和节点功率价格；用向量 表示所有的链路拥塞价格， 表示所有的节点功率价格， 表示全部
的对偶变量，得到重构优化问题的扰动KKT条件：平稳性(ST)，原始可行性(PF)，对偶可行性(DF)以及扰动互补松弛(CS)条件，其中，1表示全1向量，维度结合上下文确定：
(PF):y＞0,My‑e＜0                                  (11)
(DF):λ＞0                                         (12)
(CS):‑Diag{My‑e}λ＝1                              (13)
其中，
为定义的目标增强函数，M表示网络的路由信息和拓扑信息，e表示链路信道容量和节点发送功率的限制；
然后进一步用牛顿法处理由扰动KKT条件构成的非线性系统，求解出原始及对偶变量的牛顿方向；
根据牛顿法，原始变量y和对偶变量λ的迭代求解策略如下：
其中，π[t]表示迭代步长，Δy[t]表示原始变量的牛顿方向，Δλ[t]表示对偶变量的牛顿方向；
通过求解(10)和(13)组成的非线性系统得到：
其中， 表示fμ(y[t])的梯度矩阵， 表示fμ(y[t])的
Hessian矩阵， Λ[t]＝Diag{λ[t]}，Q[t]＝Diag{My[t]‑e[t]}，
Diag{*}表示对角化，I表示单位矩阵，维数结合上下文决定；
由上式可进一步求解得到原始变量及对偶变量的牛顿方向为：
其中
所以在时隙t，控制中心节点通过式(17)(18)计算原始及对偶变量的牛顿方向，然后通过式(15)完成对由业务流速率和链路功率构成的原始变量y的更新，以及由链路拥塞价格和节点功率价格构成的对偶变量λ的更新；
所述步骤五中集合投影方法为：
其中π∈(0,1]，为固定步长， 是可行域集合， 表示
(y,λ)在集合 上的投影结果，ε是一个趋近于0的任意正数， 是根据网络实际资源状况预设的一个大于0的常数，用来抑制突发性。

2.根据权利要求1所述的一种无线多跳网络的集中式优化分配方法，其特征在于，所述步骤一的具体步骤如下：
通过HELLO包交互获得邻居信息，并且计算出节点间链路的信噪比，以及交换彼此的操作权限信息；
通过GPS定位获得本节点位置信息；
通过相邻节点交互来获得其他节点位置信息，并计算相互之间的距离；
节点根据最短路径路由算法周期性更新本网络路由表。

3.根据权利要求1所述的一种无线多跳网络的集中式优化分配方法，其特征在于，所述步骤二的具体步骤如下：
各个节点通过周期性地发送控制信息将基本配置信息：信道带宽、是否业务流的源节点以及节点功率上界发送给控制中心；控制中心根据所获取的参数信息整理成已知参数库，更新源速率和功率更新可行域。