[發明專利]日盲紫外非視距Ad-hoc通信網絡共享信道優化方法

有效

• 申請號: 201310750756.3
• 申請日: 2013-12-30
• 公開（公告）號: CN103647603A
• 公開（公告）日: 2014-03-19
• 發明（設計）人: 楊娟;李曉毅;趙芳
• 申請（專利權）人: 中國人民解放軍重慶通信學院
• 主分類號: H04B10/11
• 分類號: H04B10/11;H04L29/06;G06N3/12
• 代理公司: 重慶博凱知識產權代理有限公司 50212
• 代理人: 王海鳳

1.日盲紫外非視距Ad-hoc通信網絡共享信道優化方法，其特征在于，包括如下步驟：

步驟1：建立了日盲紫外非視距Ad-hoc通信網絡三種信道模式下的沖突避免模型：

S11：全向——全向通信方式的沖突避免模型如式（1）：

|N1-N2|≥(1+Δ)(r₁+r₂)??（1）；

其中，Δ>0，表示保護帶區域，N1和N2均表示日盲紫外非視距Ad-hoc通信網絡的節點，r₁和r₂分別表示節點N1，N2在全向數據傳輸時的有效傳輸距離；

S12：全向——定向通信方式下的沖突避免模型如式（2）：

|N1-N2|≥(1+Δ)(r₁'+r₂)??（2）；

其中，Δ>0，表示保護帶區域，N1和N2均表示日盲紫外非視距Ad-hoc通信網絡的節點，r₁'表示節點N1在定向數據傳輸時的有效傳輸距離，r₂表示節點N2在全向數據傳輸時的有效傳輸距離；

S13：定向——定向通信方式下的沖突避免模型如式（3）：

|N1-N2|≥(1+Δ)(r₁'+r₂')??（3）；

其中，Δ>0，表示保護帶區域，N1和N2均表示日盲紫外非視距Ad-hoc通信網絡的節點，r₁'表示節點N1在定向數據傳輸時的有效傳輸距離，r₂'表示節點N2在定向數據傳輸時的有效傳輸距離；

步驟2:構建日盲紫外非視距Ad-hoc通信網絡的局部鏈路沖突圖，具體步驟如下：

S21：構造鏈路干擾近似模型：

每條鏈路僅和自身的ξ跳內的鄰居鏈路存在干擾，其中R=min{r_i,r_i'}表示節點的傳輸半徑，R'=max{r_i,r_i'}表示節點的干擾半徑；

S22：利用日盲紫外非視距Ad-hoc通信網絡中節點的計算能力計算，各節點產生包含有自己業務傳輸及所受干擾信息的廣播數據包，用全向光束將該廣播數據包發送給其ξ跳內的鄰居鏈路節點；

S23：每個節點都保存它的ξ跳內節點發送的廣播包，并生成日盲紫外非視距Ad-hoc通信網絡的局部鏈路沖突圖；

步驟3：根據步驟2建立的日盲紫外非視距Ad-hoc通信網絡的局部鏈路沖突圖計算最優染色序列，具體如下：

S31：設步驟2建立的日盲紫外非視距Ad-hoc通信網絡的局部鏈路沖突圖為M_λ,c=(Λ,l_λ,c)，該局部鏈路沖突圖的μ—點染色是從局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)的頂點集Λ到色數集PC(μ)的一個映射σ；當且僅當λ_i,λ_j∈Λ，且λ_iλ_j∈l_λ,c時，σ(λ_i)≠σ(λ_j)，局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)的μ—點染色集合記為Ξ_μ(M_λ,c)，若|Ξ_μ(M_λ,c)|≠0，則稱局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)是μ—點可染色的，其中，λ_i，λ_j分別表示鏈路沖突圖M_λ,c=(Λ,l_λ,c)的頂點集Λ中的第i個和第j個頂點，l_λ,c表示沖突鏈路集，σ(λ_i)表示λ_i的染色值，σ(λ_j)表示λ_j的染色值，色數集PC(μ)表示染色值構成的集合；

S32：采用遺傳算法與貪心算法相結合進行鏈路沖突圖的染色，具體步驟如下：

S321：構建染色體空間：

用A(M_λ,c)=(ai_j)_k×k表示局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)的鄰接矩陣，具體如式（4）：

aij1ifλiλj∈lλ,c0ifλiλj∉lλ,c---(4);]]>

其中k表示鏈路沖突圖M_λ,c=(Λ,l_λ,c)的階數，a_ij表示鄰接矩陣A(M_λ,c)=(ai_j)_k×k中的元素，對局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)頂點的所有染色方案構成染色體空間；

對染色體空間作如下編碼：

設M_λ,c=(Λ,l_λ,c)的k個頂點的一種順序為n₁，n₂...n_k，其中n₁，n₂...n_k是自然數的{1,2,...,k}的一種排列，對應于一個長度為k的序列x₁x₂...x_i...x_k，其中x_i表示對M_λ,c=(Λ,l_λ,c)的頂點λ_i所著的顏色，x_i∈PC(μ)；

對染色體空間進行編碼后，利用貪心算法產生由整數組成的N條染色體組成的初始種群，則對應于一個長度為k的序列x₁x₂...x_i...x_k成為一條染色體x，x_i則成為該條染色體的第i個基因；

S322：設定適應度函數：

定義罰函數如式（5）:

p(x)=Σi=1.j=i+1kη(λi,λj)---(5);]]>

且

η(x)表示染色體空間中染色體x違反約束的邊的數目；

定義適應度函數如式（7）：

ρ(x1x2...xk)=1p(x)+|χ(x)-ϵ-1|---(7);]]>

其中χ(x)是染色體x=(x₁x₂...x_k)中所用的顏色數,ε為已求得的μ—點可染色方案中所用的顏色最小值；

S333：遺傳選擇概率γ_i的確定：

對于適應度值為ρ_i的第i條染色體x，它的遺傳選擇概率γ_i可用公式（8）計算：

γi=ρiΣj=1pop_sizeρj---(8);]]>

其中求和上限pop_size的取值是種群規模N；

S324：交叉算法的確定：

設x=(x₁x₂..x_i..x_k)和z=(z₁z₂...z_i...z_k)是參加交叉的兩個父代染色體，依次對基因x_i,(i=1,2,...,k)和z_i,(i=1,2,...,k)分如下兩類情況交叉：

1）當基因x_i<ε和z_i<ε時,若使得(λ_i,λ_j)∈l_λ,c,x_i=x_j，則令x_i=z_i；

2）否則，令x_i=min(x_i,z_i)；

S325：變異算法的確定：

在染色體x=(x₁x₂...x_k)中隨機選擇兩個位置,對這兩個位置之間的基因值進行重新排序,其它位置的基因保持原來的值不變；

S326：逆轉算法的確定：

在染色體x=(x₁x₂...x_k)中隨機選取兩個位置,然后將這兩個位置之間的基因值逆轉；

S327：遺傳算法的終止條件：

每一代種群的平均適應度值可通過（9）計算:

ρ‾=Σj=1pop_sizeρjN---(9);]]>

遺傳算法的終止條件為0<θ<1；

步驟4：求解表示局部鏈路沖突圖最優染色的染色序列，具體步驟如下：

輸入：局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)，鄰接矩陣A(M_λ,c)=(ai_j)_k×k；

輸出：表示局部鏈路沖突圖最優染色的染色序列；Step1群體初始化,設置控制參數，群體規模為N,最大進化代數為gen,交叉概率為γ_c,變異概率為γ_m；

Step2貪心算法:

使用整數字符串編碼方式，采用貪心算法得到N個局部次優解，使群體初始化，具體貪心算法如下：

A1如果局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)中還有未染色頂點，執行步驟A2，否則貪心算法結束，執行遺傳算法；

A2從任一極大團Q內任一頂點出發，尋找與它拓撲距離最短另一極大團P的頂點，染相同的顏色T，以組成可以并發的鏈路集合；

A3繼續尋找與步驟A2中的極大團Q拓撲距離最短且和該極大團Q中所有頂點都不相連的頂點，對該頂點染與步驟A2中相同的顏色T，并添加進可以并發的鏈路集合；

A4重復步驟A3，如果無法再找到符合條件的頂點添加進可以并發的鏈路集合，執行步驟A5；

A5從局部鏈路沖突圖M_λ,c=(Λ,l_λ,c)中刪去前述已染色頂點以及與前述頂點相連的邊，再執行步驟A1；

Step3遺傳算法：

B1gen=0，生成初始種群Pop(0)，初始種群Pop(0)中有N條染色體；

B2利用適應度函數（7）計算gen代種群中N條染色體的適應度值；

B3若滿足算法遺傳算法的終止條件,則輸出滿足算法終止條件的染色體，該染色體上的基因序列即為表示局部鏈路沖突圖最優染色的染色序列；否則執行B4；

B4采用式（8）確定的遺傳選擇概率γ_i復制初始種群中的N條染色體得到新的N條染色體；

B5對新的N條染色體按照交叉概率γ_c成對選擇N_c條染色體，應用步驟S234確定的交叉算法在成對的兩條染色之間進行交叉；再按照變異概率γ_m選擇N_r條染色體，應用步驟S325確定的變異算法進行變異；然后再隨機選擇的N_n條染色體，

應用步驟S326中的逆轉算法進行逆轉，得到下一代種群，設gen=gen+1，返回B3；

步驟5：基于步驟4得到表示局部鏈路沖突圖最優染色的染色序列建立日盲紫外非視距Ad-hoc通信網絡的非競爭MAC協議，具體如下：

將日盲紫外非視距Ad-hoc通信網絡中染相同顏色的節點分配在同一時隙，染不同顏色的節點分配在不同時隙，時隙的個數等于隨染色數；

在所述非競爭MAC協議中，若干個時隙組成一幀，每一幀分為控制子幀和數據子幀，每一幀的開始是控制子幀，利用控制子幀將各節點傳輸業務分配到數據子幀中各數據時隙，處于沖突域范圍內的所有節點共享控制子幀的調度及數據時隙分配信息。