[發(fā)明專利]一種多并發(fā)流無線網(wǎng)狀網(wǎng)中的機會路由方法

有效

• 申請?zhí)枺?/td>: 201310648264.3
• 申請日: 2013-12-04
• 公開（公告）號: CN103619047A
• 公開（公告）日: 2014-03-05
• 發(fā)明（設(shè)計）人: 張大方;何施茗;謝鯤;張繼;喬宏
• 申請（專利權(quán)）人: 湖南大學
• 主分類號: H04W40/02
• 分類號: H04W40/02
• 代理公司: 長沙正奇專利事務(wù)所有限責任公司 43113
• 代理人: 馬強

1.一種多并發(fā)流無線網(wǎng)狀網(wǎng)中的機會路由方法，其特征在于，該方法為：

1）將多并發(fā)流無線網(wǎng)狀網(wǎng)對應成一個無向圖G=(V,E)，所述無向圖包含N個節(jié)點，其中V為節(jié)點集，E為節(jié)點間鏈路的矩陣，存在K條多并發(fā)流，源節(jié)點和目的節(jié)點分別為{(s_k,d_k),k=1..K}；

2）建立多并發(fā)流無線網(wǎng)狀網(wǎng)中各條網(wǎng)絡(luò)流吞吐量λ_k之積的目標函數(shù)模型maximizeΠk∈[1,K]λk,maximizeΠk∈[1,K]λk]]>等價為maximizeΣk∈[1,K]ln(λk):]]>

maximizeΣk∈[1,K]1n(λk)s.t.αuvk=βuk*βvk*BHuv,∀k∈[1,K],∀(u,v)∈EΣvαuvkrk(u,v)-Σwαwukrk(w,u)=hk(u),∀k∈[1,K],∀u∈Vαuvkrk(u,v)=rk(u,v)∀k∈[1,K],∀(u,v)∈EΣk∈[1,K]βukbk(u)+Σk∈[1,K]Σv∈R(u)βvkbk(v)≤C,∀u≠skβukbk(u)=bk(u),∀k∈[1,K],∀u∈Vbk(u)*p(u,v)≥rk(u,v),∀k∈[1,K],∀(u,v)∈Eαuvk={0,1},∀k∈[1,K],∀(u,v)∈Eβuk={0,1},∀k∈[1,K],∀u∈V0≤rk(u,v)≤C,∀k∈[1,K],∀(u,v)∈E0≤bk(u)≤C,∀k∈[1,K],∀u∈V;]]>

其中，s.t.表示約束條件；表示節(jié)點u是否作為第k條流的候選轉(zhuǎn)發(fā)節(jié)點，若節(jié)點u作為第k條流的候選轉(zhuǎn)發(fā)節(jié)點，則為1，否則為0；表示節(jié)點v是否作為第k條流的候選轉(zhuǎn)發(fā)節(jié)點，若節(jié)點v作為第k條流的候選轉(zhuǎn)發(fā)節(jié)點，則為1，否則為0；表示節(jié)點u和v之間的鏈路是否為第k條流所用，若節(jié)點u和v之間的鏈路是否作為第k條流所使用，則為1，否則為0；BH_uv表示節(jié)點u和v的鄰居關(guān)系，u和v互為鄰居時BH_uv值為1，否則為0；r_k(u,v)表示第k條流在鏈路(u,v)上的流速率；r_k(w,u)表示第k條流在鏈路(w,u)上的流速率；λ_k表示第k條流的吞吐量；b_k(v)為節(jié)點v的平均廣播速率；b_k(u)為節(jié)點u的平均廣播速率，表示節(jié)點u在第t個調(diào)度時槽是否為第k條流傳輸數(shù)據(jù)，為1表示發(fā)送，否則為0；T為調(diào)度時槽個數(shù)；C為MAC層的容量；b_k(v)為節(jié)點v的平均廣播速率;p(u,v)表示鏈路(u,v)的包投遞率；

3）將上述目標函數(shù)模型的等價表達式轉(zhuǎn)化為以下優(yōu)化模型：

maximizeΣk∈[1,K]1n(λk)s.t.bk(u)*p(u,v)≥rk(u,v),∀k∈[1,K],∀(u,v)∈EΣvrk(u,v)-Σwrk(w,u)=hk(u),∀k∈[1,K],∀u∈VΣk∈[1,K]bk(u)+Σk∈[1,K]Σv∈R(u)bk(v)≤C,∀u≠sk0≤rk(u,v)≤C,∀k∈[1,K],∀(u,v)∈E0≤bk(u)≤C,∀k∈[1,K],∀u∈V;]]>

4）將上述優(yōu)化模型轉(zhuǎn)化為以下標準形式：

minimize-Σk∈[1,K]1n(λk)s.t.rk(u,v)-bk(u)*p(u,v)≤0,∀k∈[1,K],∀(u,v)∈EΣvrk(u,v)-Σwrk(w,u)=hk(u),∀k∈[1,K],∀u∈VΣk∈[1,K]bk(u)+Σk∈[1,K]Σv∈R(u)bk(v)-C≤0,∀u≠sk;0≤rk(u,v)≤C,∀k∈[1,K],∀(u,v)∈E0≤bk(u)≤C,∀k∈[1,K],∀u∈V]]>

5）初始化，設(shè)定i為0，隨機設(shè)定初始參數(shù)其中和分別表示和的對偶參數(shù)；

6）設(shè)定i為1；

7）為步驟4）中的模型引入對偶參數(shù)，建立拉格朗日函數(shù)，其中約束條件的對偶參數(shù)是x(u),約束條件的對偶參數(shù)是y_k(u,v)，根據(jù)對偶和子梯度法求解方法，利用下式更新對偶參數(shù)：

x(i)(u)=max(0,x(i-1)(u)+ηMu(i-1))yf(i)(u,v)=max(0,yk(i-1)(u,v)+ηH(k,u,v)(i-1))Mu(i-1)=Σf∈[1,F]u≠skbk(i-1)(u)+Σf∈[1,F]Σv∈R(u),u≠skbk(i-1)(v)-CH(k,u.v)(i-1)=rk(i-1)(u,v)-bk(i-1)(u)p(u,v);]]>

其中，x^(i-1)(u)和為第i-1次迭代的對偶參數(shù)，η為步長，η>0；分別為x(u)和y_k(u,v)的對偶梯度，為第i-1次迭代中節(jié)點u的平均廣播速率，為第i-1次迭代中鏈路(u,v)在第k條流上的流速率；

8）根據(jù)第i次迭代的對偶參數(shù)，計算第i次迭代中第k條流在鏈路(u,v)上的流速率和節(jié)點u的平均廣播速率

bk(i)(u)bk(i-1)(u)+12ϵ(Σ(u,v)∈Eyk(i)(u,v)p(u,v)-x(i)(u)u≠sk-Σv∈R(u),v≠skx(i)(v))]]>

其中：為第i次迭代中第k條流的流速率；π為第k條流源節(jié)點到目的節(jié)點的任意一條路徑；為第i次迭代鏈路(u,v)的對偶參數(shù)，即鏈路(u,v)的開銷；為第i次迭代中第k條流中開銷最小的路徑的開銷；若鏈路(u,v)∈arg minπΣ(u,v)∈πyk(i)(u,v),]]>則rk(i)(u,v)=Γki;]]>否則rk(i)(u,v)=0;]]>

9)計算第i次迭代中第k條流在鏈路(u,v)上的平均流速率計算第i次迭代中節(jié)點u的平均廣播速率的平均值判斷前后兩次迭代的差是否小于10^-4，若是，進入10）；否則，令i=i+1，返回7），直到當前迭代次數(shù)i大于最大迭代次數(shù)run，run>0，得到收斂后的進入10）；

10）利用收斂后的根據(jù)下式得到最大的目標函數(shù)值

11）利用收斂后的和根據(jù)下式得到和

αuvk=1,r~k(i)(u,v)≠00,r~k(i)(u,v)=0,∀k∈[1,K],∀(u,v)∈E;]]>

βuk=1,b~k(i)(u)≠00,otherwise∀k∈[1,K].]]>