認知AdHoc網絡的分布式拓撲控制方法

2023-09-11 14:29:00 1

認知Ad Hoc網絡的分布式拓撲控制方法
【專利摘要】本發明公開了一種認知Ad Hoc網絡的分布式拓撲控制方法，主要解決現有技術中次用戶網絡的連通性不能保證和次用戶相互幹擾的問題。其實現過程為：網絡中的每個節點先後廣播兩次HELLO包，並接收初始鄰節點的HELLO包，建立局部兩跳拓撲子圖；基於局部兩跳拓撲子圖，先根據能耗鏈路代價權重，構建最短路徑樹，然後基於最短路徑樹構建可保證次用戶連通的局部生成子圖；根據局部生成子圖中的一跳鄰節點調整發射功率；由網絡中的所有節點以及節點與其邏輯鄰節點間的鏈路構成全網拓撲；拓撲構建完成後，網絡中的節點獨立的進行信道選擇。本發明具有保證次用戶網絡連通，消除次用戶幹擾，複雜度低的優點，可用於認知Ad Hoc網絡。
【專利說明】認知AdHoc網絡的分布式拓撲控制方法

【技術領域】
[0001] 本發明屬於無線通信領域，特別涉及一種構建網絡拓撲結構的方法，可用於認知 AdHoc網絡。

【背景技術】
[0002] 認知AdHoc網絡是認知網絡與傳統AdHoc網絡的結合，是一種充滿發展潛力的 無線網絡通信系統，該網絡除了具有傳統AdHoc網絡的自組織、自配置、自適應能力之外， 還具有對頻譜資源的感知、機會接入以及動態分配的能力，能夠靈活地用於各種無固定通 信基礎設施支撐的環境，提高現有頻帶資源的利用率。
[0003] 在影響認知AdHoc網絡性能的眾多因素之中，網絡的拓撲結構是不可忽視的一 個重要方面，因此如何優化認知AdHoc網絡的拓撲結構、增強網絡拓撲的容錯能力並為 上層通信協議提供良好的底層拓撲支撐是拓撲控制技術研究的重點。在認知AdHoc網絡 中，用戶分為兩類，一類是主用戶，另一類是次用戶。主用戶享有信道的優先使用權。當主 用戶不使用信道時，次用戶可以使用該信道。由於次用戶只能機會式地接入信道，次用戶 網絡的連通性容易受到主用戶的影響。當主用戶要使用某個信道時，次用戶為了保護主用 戶的正常通信就會空出該信道並處於靜默狀態，靜默節點會降低次用戶網絡的連通性，嚴 重時會導致網絡的分割。為了減小主用戶對次用戶網絡連通性的影響，研究者已經提出 了一些拓撲控制算法，如JingZhao等作者在IEEEINF0C0M2012上發表的文章"Robust TopologyControlinMulti-hopCognitiveRadioNetwork，'，以及HaiLiu等作者在 IEEEICCCN2012 上發表的文章"Generalized-Bi-ConnectivityforFaultTolerant CognitiveRadioNetwork"。JingZhao等的算法可以保證次用戶網絡的連通，但不能消除 次用戶之間的幹擾。HaiLiu等的算法可以進一步消除次用戶的幹擾，但是不能分布式的執 行，而且算法複雜度高。


【發明內容】

[0004] 本發明的目的在於針對上述現有技術的問題，提出一種認知AdHoc網絡的分布式 拓撲控制方法，保證次用戶網絡的連通性，消除次用戶之間的幹擾，降低複雜度。
[0005] 為了實現上述目的，本發明網絡拓撲控制方法包括如下步驟：
[0006] (1)網絡中每個節點u發送自己的HELL0-1包，並接收一跳鄰節點發送的HELL0-1 包，該HELL0-1包中包括u節點的ID序列號和位置信息；
[0007] (2)網絡中每個節點u發送自己的HELL0-2包，並接收一跳鄰節點發送的HELL0-2 包，該HELL0-2包中包括u節點的一跳鄰節點的ID序列號和位置信息；
[0008] (3)網絡中每個節點u構建自己的局部兩跳拓撲子圖:
[0009] (3a)網絡中的每個節點u根據接收到的HELL0-1和HELL0-2包信息，確定自己與 兩跳鄰節點的連接關係，以及這些鄰節點之間的連接關係，建立局部兩跳拓撲子圖g;
[0010] (3b)根據局部兩跳拓撲子圖，每個節點u計算局部兩跳拓撲子圖中任意兩個有連 接關係的節點X，y之間的鏈路能耗權重wp (X，y)和鏈路距離權重wd (X，y);
[0011] ⑷網絡中每個節點U構建局部生成子圖Su= (V(SU)，E(SU)):
[0012] (4a)網絡中的每個節點u將局部生成子圖Su的節點集合V(SU)初始化成局部兩 跳拓撲子圖中的所有節點，將邊集合E(SU)初始化成空集；
[0013] (4b)基於局部兩跳拓撲子圖(7,)，每個節點u根據鏈路能耗權重Wp(x，y)，構建 以u為根，遍及局部兩跳拓撲子圖中所有節點的最短路徑樹Tu =(V(Tu)，E(Tu))，其中 K(7；,) =K(G,))為局部兩跳拓撲子圖中的所有節點，E(TU)為構成最短路徑樹的所有邊，並將 這些邊記錄到局部連通子圖Su中，S卩￡(6'")e￡(7：)U);
[0014] (4c)網絡中的每個節點u根據最短路徑樹Tu找到與自己衝 突的節點，構成集合CNU，並初始化衝突子圖為CSU，其中V(CSU) =CNU， Eev)e ;
[0015] (4d)每個節點u檢測各自的衝突連通子圖CSU是否連通，如果連通，節點u則在 CSU上構建局部生成子圖Tu';如果不連通，節點u則在句\?上構建斯坦納生成樹Tu';如 果上述兩個步驟均無法執行，節點u則獲知h跳鄰節點信息，構建局部h跳拓撲子圖G,)，並 在上構建斯坦納生成樹Tu';
[0016] (4e)節點u將邊集EOV)記錄到局部生成子圖的邊集E(Su)中，即 ￡(S")e￡(7:,')U￡(S"),將節點V(Tu')記錄到局部生成子圖的節點集V(Su)中，即 K(S")e)U【/(\)，將節點V(Tu')記錄到邏輯衝突鄰居集LCNu中，即LCNu= V(V)，然後節點u通過洪泛的方式把LCNU和E(Su)的拓撲信息發送給Su中的所有節點；
[0017] (4f)每個節點U根據其他節點發來的拓撲信息更新自己的局部生成子圖Su和邏 輯衝突鄰居集LCNU，將局部生成子圖Su上的一跳鄰節點v作為邏輯鄰節點，並構成邏輯鄰 節點集：LNU={vGV(Su) | (u,v)GE(Su)};
[0018] (5)網絡中每個節點u確定自己的發射功率，即將發射功率調整為能夠覆蓋到所 有邏輯鄰節點所需要的最小功率：C、.. =max丨/V,.卜'eh
[0019] (6)將網絡中的所有節點以及每個節點與自己的邏輯鄰節點間的鏈路組合起 來，構成最終的全網拓撲，即G= (V(G)，E(G))，其中V(G)為網絡中所有節點，E(G)= {(u,v)IuGV(G), VGLNJ；
[0020] (7)拓撲構建完成後，網絡中的每個節點u開始分配信道：
[0021] (7a)節點u向邏輯衝突鄰居集LCNU中的所有節點發送請求分配信道包 RAC(RequireAssignmentChannel)；
[0022] (7b)LCNU中的所有節點在收到RAC包後，回饋信道分配包AC(Assignment Channel)給節點u，告知其已經分配的信道；
[0023](7c)節點u收集所有LCNU中的節點回饋的AC包，選擇還未被佔用的、信道質量最 好的信道（或主用戶佔用概率最小的信道），作為自己的可用信道；
[0024] (7d)每個節點獨立執行上述過程，直到所有節點都分配完信道為止。
[0025] 本發明具有如下優點：
[0026] 1)本發明聯合功率控制和信道分配，通過功率控制使得次用戶網絡的獨立集不構 成網絡的割集，從而保證次用戶網絡的連通性；通過信道分配給相互幹擾的次用戶分配不 同的信道，從而消除次用戶之間的幹擾。
[0027] 2)本發明通過功率控制構造適合於信道分配的拓撲，避免了高複雜度的連通性判 斷，從而降低了算法的整體複雜度。而且次用戶只需局部拓撲信息，因此算法可以分布式運 行。
[0028] 3)本發明由於減小了節點的發射功率，所以為保證次用戶網絡的連通性和無衝突 所需的信道數少。

【專利附圖】

【附圖說明】
[0029] 圖1為本發明適用的認知AdHoc網絡場景示意圖；
[0030] 圖2為50節點網絡場景時形成的最大功率拓撲；
[0031] 圖3為本發明的流程圖；
[0032] 圖4為本發明中構建局部生成子圖的子流程圖；
[0033] 圖5為本發明中節點u拓撲構建的示例圖；
[0034] 圖7為本發明生成拓撲的仿真驗證圖；
[0035]圖8為本發明與其他拓撲控制算法平均傳輸半徑的仿真對比圖；
[0036]圖9為本發明與其他拓撲控制算法平均信道數和最大信道數的仿真對比圖。

【具體實施方式】
[0037] 下面將結合附圖對本發明實施方式做進一步詳細描述。
[0038] 參照圖1，本發明使用的認知AdHoc網絡由n個分布在二維平面區域內的節點組 成。每個節點代表一個次用戶，且具有唯一的ID序列號，並可以通過GPS或是其他定位技 術來獲取它自身的位置信息。所有的節點受到同一個主用戶的影響，主用戶可以使用C個 信道中的任意一個信道。每個節點可以在C個信道中任意一個信道中發送數據，同時在其 他所有信道上偵聽數據，除此之外每個節點在物理結構、初始設置、功能特性、參數指標等 方面不存在任何差異。在網絡中，任意節點間的無線信道為加性高斯白噪聲信道。節點通 過全向天線與周圍節點通信，最大發射功率均為P_。任意節點u的發射功率Pu可以在最 小和最大之間連續調節，即〇 <Pu<P_。傳輸半徑r為對應於節點發射功率的傳輸距離， 任意兩個節點之間存在無線鏈路的充要條件為它們之間的歐式距離小於或等於節點的傳 輸半徑r。當網絡中每個節點均使用最大功率傳輸時形成的拓撲結構為最大功率拓撲，如 圖2所示，最大功率拓撲表示為：6_=(￥(6_)3(6_))，其中￥(6_)為節點集合，表示網 絡節點，E(Gmax)為邊集合，表示節點間存在的無線鏈路。
[0039] 參照圖3,本發明的實現步驟如下：
[0040] 步驟1，網絡中每個節點u發送自己的HELL0-1包，並接收一跳鄰節點發送的 HELL0-1 包。
[0041] 位於節點u的傳輸半徑範圍內的所有節點，組成節點u的一跳鄰節點集WV；: ^|=_卜'|#((7|,",、）|("小） ￡￡((7|,1;1、）丨_，其中次用戶力和次用戶11的距離為1跳；
[0042] 網絡中的每個節點u以最大發射功率Pmax向u的一跳鄰節點廣播一次HELLO-1包， HELL0-1包中含有節點u的ID序列號和節點u的位置信息；
[0043] 網絡中的每個節點u接收一跳鄰節點以最大發射功率Pmax廣播的HELL0-1包。
[0044] 步驟2,根據上述步驟1中的HELL0-1包，網絡中每個節點u發送自己的HELL0-2 包，並接收一跳鄰節點發送的ffiLLO-2包。
[0045] 節點u在兩跳以內（包括兩跳）可以到達的所有節點，組成節點u的兩跳鄰節點 集mu2: 1^2=1^1^2￡叩5_)|^以&&〇^2)€五(Gmax)}，U表示兩個集合的並，&& 表示並且，其中次用戶^和次用戶u的距離為2跳；
[0046] 網絡中的每個節點u接收完所有一跳鄰節點發送的HELL0-1包後，以最大發射功 率P_向u的一跳鄰節點廣播一次HELL0-2包，HELL0-2包中含有u的所有一跳鄰節點的 ID序列號和位置信息；
[0047] 網絡中的每個節點u接收一跳鄰節點以最大發射功率Pmax廣播的HELL0-2包。
[0048] 步驟3,網絡中每個節點u構建自己的局部兩跳拓撲子圖紀。
[0049] (3a)網絡中的每個節點u根據接收到的一跳鄰節點發送的HELL0-1和HELL0-2包 信息，獲取並記錄自己所有兩跳鄰節點v12的ID序列號和位置信息，其中v12eIWU2;
[0050] (3b)每個節點u根據自己的位置信息以及兩跳鄰節點的位置信息，計算任意兩個 節點x，y之間直接傳輸所需要的最小發射功率Px，y:
[005i]m
[0052] 其中，x,_yeIWu2,運為接收信噪比門限值，根據接收機的靈敏度和誤碼率要求確 定，當信號接收信噪比SNR大於門限值3時該信號可被正確接收，a為路徑損耗因子，dx，y 是節點X，y之間的歐式距離；
[0053] (3c)根據計算的最小發射功率，判斷兩跳鄰節點之間的連接關係，若Px，y小於節 點的最大發射功率Pmax，則確定節點X，y之間存在連接關係；否則，節點X，y之間不存在連接 關係；
[0054] (3d)每個節點u根據兩跳鄰節點之間的連接關係，建立局部兩 跳拓撲子圖戌=(以(又),邱5,,))，其中局部兩跳拓撲子圖戌的節點集合為 K((?〗）=KiVu2U{4, {u}表示節點u組成的集合，局部兩跳拓撲子圖戌的邊集合 為：五即對於F(G"2)中的任意兩個節點x，y，當Px，y<PmaxW，&(x，y)GE(Gu);
[0055] (3e)根據局部兩跳拓撲子圖，每個節點u計算任意兩個有連接關係的節點x，y之 間的鏈路能耗權重wp (X，y):
[0056] wp(x,y) = Px；y
[0057] 其中，WeK(g)，Pxy為任意兩個有連接關係的節點x，y之間直接傳輸所需要 的最小發送功率；
[0058] (3f)根據上述歐式距離和節點ID序列號，節點u計算任意兩個有連接關係的節點 x，y之間的距離權重wd(x，y):
[0059]wd(x,y) =dx；y,
[0060] 其中，dx，y是任意兩個有連接關係的節點x，y之間的歐氏距離。
[0061] 步驟4,網絡中每個節點u構建局部生成子圖Su= (V(Su)，E(SU))，並確定自己的 邏輯鄰節點。
[0062] 具體流程如圖4所示：
[0063] (4a)網絡中的每個節點u將局部生成子圖Su的節點集合V(SU)初始化成局部兩 跳拓撲子圖中的所有節點，即^乂）=)，將邊集合E(Su)初始化成空集；
[0064] (4b)基於局部兩跳拓撲子圖6^，以鏈路能耗權重wp(X，y)為鏈路權重，節點u通 過使用Dijkstra算法或Bellman-Ford算法，構建以u為根，遍及7(0',;)中所有節點的最短 路徑樹Tu= (V(TU)，E(TU))，其中為局部兩跳拓撲子圖中所有節點，E(TU)為 構成最短路徑樹的所有邊，從而在局部範圍內獲得到達局部兩跳拓撲子圖中任意節點的最 短路徑，並將這些邊記錄到局部連通子圖Su中，S卩ECS,,)e￡(7：)U￡(5'")，^表示賦值； [0065] (4c)節點u根據最短路徑樹Tu找到與自己衝突的節點構成衝突節點集CNu，並構 建衝突子圖CSU，其中V(CSU) =CNU，E(C6'" ) = {(.r,.y) |.Y,.vee 突節點集定義為：沿最短路徑樹Tu兩跳可達的所有節點構成的集合，S卩，其中M = {v I (?，v)e攻7!)}，氣2 = {v I w E & &(w，v) e五(1)};
[0066] (4d)每個節點u檢測各自的衝突連通子圖CSU是否連通，如果連通，節點u則在 CSU上構建局部生成子圖T/ ;如果不連通，節點u則在上構建斯坦納生成樹T/ ;如 果上述兩個步驟均無法執行，節點u則獲取h跳鄰節點信息，構建局部h跳拓撲子圖6^，並 在上構建斯坦納生成樹T/ ;
[0067] (4dl)節點u通過使用Kruskal算法或Prim算法檢測衝突子圖CSU是否連通；
[0068] (4d2)如果CSU是連通的，節點u則在CSU上構建局部生成子圖T/。首先，節點 u將生成子圖T/中的節點集初始化為CSU中的所有節點，即V(Tu' ) =V(CSU)，將邊集初 始化為E〇V) = {(X，y)|X，yGV(Tu' )，（x，y)GE(TU)};然後，節點u將CSU中的所有 邊，按距離權重wd (x，y)為鏈路權重，從小到大進行排序；最後，節點u按順序依次判斷CSU 中每一條邊的兩個端點在Tu'中是否連通，如果不連通則加入到邊集ECV)中，反之，則 不加入。上述過程一直進行，直到判斷完所有的邊為止，並生成最終的生成子圖IV。
[0069] (4d3)如果CSU不連通，節點u利用文獻V.J.Rayward-SmithandA.Clare,"On findingsteinervertices, "NETW0RKS,vol. 16,no. 3,pp. 283 - 294, 1986?中的TMR算法 在戌\?上構建斯坦納（steiner)生成樹Tu'。其中，紀W表示在局部兩跳子圖g中刪掉 節點u及其關聯的邊所得到的子圖；在構造斯坦納生成樹T/時，V(CSU)中的所有節點構 成基本節點集，而\〃)-r(CS")中的節點構成斯坦納節點集；
[0070] (4d4)如果步驟（4c2)和（4c3)均無法執行時，節點u通過信息交互獲取h跳鄰 節點信息，構建局部h跳拓撲子圖0，並在0上構建斯坦納生成樹Tu'。首先，節點u利 用步驟一和步驟二的方法通過發送Hello包獲知h跳鄰節點的信息，然後，節點u利用步 驟三的方法構建局部h跳拓撲子圖GUA，最後，節點u利用步驟（4c3)的方法在g上構建 斯坦納生成樹Tu'，在構造斯坦納生成樹Tu'時，V(CSU)中的所有節點構成了基本節點集， )/(C3")中的節點構成斯坦納節點集；
[0071] (4e)節點u將邊集E0V)記錄到局部生成子圖的邊集E(Su)中，即 ￡(S")仁￡\7；,')U￡(5；,)，將節點VCC)記錄到局部生成子圖的節點集V(SU)中，即 ;/(S")eref)U丨AS:,)，將節點V(V)記錄到邏輯衝突鄰居集LCNu中，S卩LCNu=V0V);然後，節點u通過洪泛的方式把LCNU和E(SU)的拓撲信息發送給Su中的所有節 佔.
[0072] (4f)每個節點u接收其他節點發送來的拓撲信息，並根據這些拓撲信息更新自己 的局部生成子圖Su和邏輯衝突鄰居集LCNU，如果接收到的任意一個節點v的生成子圖Sv 中，有關聯到自己的邊就將這條邊加入到Su中，如果LCNv中包含了自己，節點u就將v記錄 到自己的LCNU中；最後，節點u將局部生成子圖Su上的一跳鄰節點v作為邏輯鄰節點，並構 成邏輯鄰節點集：LNU={vGV(SU) | (u,v)GE(SU)};
[0073] 參照圖5,其中圖（a)表示節點u通過互換Hello-1和Hello-2包構建的局部兩 跳拓撲子圖圖（b)表示節點u利用能耗權重構建的最短路徑樹Tu;圖（c)表示節點u 在Tu中找到的衝突鄰居節點集CNU;圖（d)表示節點u構建的衝突子圖CSU;通過判斷可知CSU是連通的，所以節點u直接執行步驟（4d2)，在CSU上構建局部生成子圖Tu'，如圖（e) 所示；節點u最終構建的生成子圖Su如圖（f)所示。
[0074] 步驟5,每個節點u根據上述確定的邏輯鄰節點，將自己的發射功率調整為能夠覆 蓋到最遠的邏輯鄰節點所需要的最小功率^"，即=max{AM. 。
[0075] 步驟6,根據上述拓撲控制過程，網絡中的每個節點獨立確定與自己的邏輯 鄰節點的連接關係，將網絡中的所有節點以及每個節點與自己的邏輯鄰節點間的鏈路 組合起來，構成最終的全網拓撲，即G= (V(G)，E(G))，其中V(G) =V(Gmax)，E(G)= {(u，V)IuGv(G)，VGLNJ。
[0076] 步驟7,拓撲構建完成後，網絡中的每個節點u選擇發送信道。
[0077] (7a)節點u用最大發送功率Pmax在公共控制信道上廣播請求分配信道包RAC，其 他節點在收到這個包時需要再次中轉該包，直到邏輯衝突鄰居集LCNU中的所有節點都接收 到RAC包為止；
[0078] (7b)LCNU中的所有節點在收到RAC包後，查看自己已經分配的信道，並回饋信道分 配包AC給節點u，其中信道分配包AC中包含了該節點已經分配的信道，如果該節點還未分 配信道就將包AC記為空包。
[0079] (7c)節點u收集所有LCNU中的節點回饋的AC包，從還未被佔用的信道中選擇主 用戶佔用概率最小的信道，作為自己的可用信道；
[0080] (7d)每個節點獨立執行上述過程，直到所有節點都分配完信道為止。
[0081] 本發明的效果可通過仿真進一步說明：
[0082] (1)仿真條件
[0083] 在仿真場景中，網絡節點隨機均勻分布在一個1000X1000m2的二維平面區域中。 接收信噪比SNR的門限值3設為-80dBm，路徑損耗因子a取值為4。網絡中所有節點採 用相同的最大發射功率，其中最大發射功率Pmax= 256mW，對應的最大傳輸半徑Rmax= 400m。 假設主用戶會影響到所有的次用戶節點。
[0084] ⑵仿真內容和結果
[0085] 仿真1，在20節點的場景中驗證本發明方法生成的拓撲可以保證次用戶的連通 性。
[0086] 圖6表明：圖a為最大功率拓撲，圖b為本發明方法生成的拓撲，其中的數字表示 節點分配的信道，圖c為圖b對應的衝突圖，圖d、e、f為主用戶分別佔用信道4、5、6時次用 戶網絡的拓撲。通過該仿真可以看出，本發明方法生成的拓撲在主用戶任意佔用一個信道 時，次用戶的網絡仍然是連通的。
[0087]仿真 2,用本發明方法與文獻H.Liu,Y.Zhou,X.Chu,Y. -W.Leung,andZ.Hao,"Gen eralized-bi-connectivityforfaulttolerantcognitiveradionetwork,，'inProc. IEEEICCCN,Munich,Germany,Aug. 2012,pp. 1 - 8?中的GBC、GBC+DC算法以及最大功率拓 撲MaxPower對節點平均傳輸半徑進行仿真，結果如圖7所示。
[0088] 圖7表明：隨節點數的增多，最大功率拓撲MaxPower的平均傳輸半徑保持不變，均 為400m，而其他算法的平均傳輸半徑不斷減小，其中本發明方法的平均傳輸半徑最小，加之 本發明方法可以維持了節點端到端的能耗最短路徑，因此本發明方法可以很好的減小節點 的能耗，增大網絡的生存期。
[0089] 仿真3,用本發明方法與GBC、GBC+DC算法以及最大功率拓撲MaxPower對所平均 所需信道數進行仿真，結果如圖8所示。
[0090] 圖8表明：隨著節點數的增多，最大功率拓撲MaxPower的平均信道數呈線性增長， 而其他算法基本保持不變，本發明方法所需平均信道數最少，相比GBC算法減少了 40 %多， 相比GBC+DC算法減少了 17%多。
[0091] 仿真4,用本發明方法與GBC、GBC+DC算法以及最大功率拓撲MaxPower對所最大 所需信道數進行仿真，結果如圖9所示。
[0092] 圖9表明：隨著節點數的增多，最大功率拓撲MaxPower的最大信道數呈線性增長， GBC和GBC+DC的較大，而本發明方法所需最大信道數最小，相比GBC算法較少了 60 %多，相 比GBC+DC算法減少了 45%多。網絡所需的最大信道數越少，說明算法的魯棒性越好，而GBC 和GBC+DC算法在信道總數較小時可能無法正常執行，所以本發明方法魯棒性較好。
【權利要求】
1. 一種認知AdHoc網絡的分布式拓撲控制方法，包括如下步驟： (1)網絡中每個節點u發送自己的HELLO-I包，並接收一跳鄰節點發送的HELLO-I包， 該HELL0-1包中包括u節點的ID序列號和位置信息； ⑵網絡中每個節點u發送自己的HELL0-2包，並接收一跳鄰節點發送的HELL0-2包， 該HELL0-2包中包括u節點的一跳鄰節點的ID序列號和位置信息。 (3) 網絡中每個節點u構建局部兩跳拓撲子圖 (3a)網絡中的每個節點u根據接收到的HELLO-1和HELLO-2包信息，確定自己與兩跳 鄰節點的連接關係，以及這些鄰節點之間的連接關係，建立局部兩跳拓撲子圖Ga2; (3b)根據上述局部兩跳拓撲子圖，每個節點u計算局部兩跳拓撲子圖中任意兩個有連 接關係的節點X，y之間的鏈路能耗權重wp(x,y)和鏈路距離權重wd(x,y) ,wp(x,y)通過如下 公式計算：wp(x,y) =Px，y，其中，Px，y是最小發射功率；wd(x,y)通過如下公式計算：wd(x,y) =dx，y，其中dx，y為節點間的歐式距離； (4) 根據上述局部兩跳拓撲子圖，網絡中每個節點u構建局部生成子圖Su= (V(Su)，E(Su)): (4a)網絡中的每個節點u將局部生成子圖Su的節點集合V(Su)初始化成局部兩跳拓 撲子圖中的所有節點，將邊集合E(Su)初始化成空集； (4b)基於局部兩跳拓撲子圖Gf，每個節點u根據鏈路能耗權重Wp(x，y)，構建以u為根， 遍及局部兩跳拓撲子圖中所有節點的最短路徑樹Tu= (V(TU)，E(Tu)),其中以7;,) = (/(($)為 局部兩跳拓撲子圖中的所有節點，E(Tu)為構成最短路徑樹的所有邊，並將這些邊記錄到局 部連通子圖Su中，即)e￡(7：)U卩叉）； (4c)網絡中的每個節點u根據最短路徑樹Tu找到與自己衝突的節 點，構成衝突節點集CNU，並初始化衝突子圖為CSU，其中V(CSu) =CNU， E (C5，-)=}(-v' >')I-vecv?' (v' -v)e￡ (gI)}; (4d)每個節點u檢測各自的衝突連通子圖CSu是否連通，如果連通，節點u則在CSu上 構建局部生成子圖V;如果不連通，節點u則在gw/上構建斯坦納生成樹Tu';如果上 述兩個步驟均無法執行，節點u則獲取h跳鄰節點信息，構建局部h跳拓撲子圖G=，並在 上構建斯坦納生成樹Tu'; (4e)節點u將邊集ECC)記錄到局部生成子圖的邊集E(Su)中，即 ￡〇S")e￡(〇U￡X5；,)，將節點VOV)記錄到局部生成子圖的節點集V(Su)中，即 K(SJeFK)UrOS;)，將節點V(V)記錄到邏輯衝突鄰居集LCNu中，即LCNu= V(V)，然後節點u通過洪泛的方式把LCNu和E(Su)的拓撲信息發送給Su中的所有節點； (4f)每個節點u根據其他節點發來的拓撲信息更新自己的局部生成子圖Su和邏輯衝 突鄰居集LCNu,將局部生成子圖Su上的一跳鄰節點V作為邏輯鄰節點，並構成邏輯鄰節點 集：LNu={vGV(Su)I(u，V)GE(Su)}; (5) 網絡中每個節點u確定自己的發射功率，即將發射功率調整為能夠覆蓋到所有邏 輯鄰節點所需要的最小功率：7U=max_!凡」.卜'e 丨_; (6) 將網絡中的所有節點以及每個節點與自己的邏輯鄰節點間的鏈路組合起來， 構成最終的全網拓撲，即G= (V(G)，E(G))，其中V(G)為網絡中所有節點，E(G)= {(u,v)IuGV(G),VGLNJ； (7) 根據上述拓撲，網絡中的每個節點u選擇發送信道： (7a)節點u向邏輯衝突鄰居集LCNu中的所有節點在公共控制信道上發送請求分配信 道包RAC(RequireAssignmentChannel)； (7b)LCNu中的所有節點在收到RAC包後，回饋信道分配包AC(AssignmentChannel)給 節點u，告知已經選擇的信道； (7c)節點u收集所有LCNu中的節點回饋的AC包，從還未被佔用的信道中選擇主用戶 佔用概率最小的信道，作為自己的可用信道； (7d)每個節點獨立執行上述過程，直到所有節點都分配完信道為止。
2. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（1)和步 驟（2)所述的網絡中每個節點u發送自己的HELLO-I和HELL0-2包，是指網絡中的每個節點 u，以最大發射功率Pmax向位於距離自己傳輸半徑範圍內的所有節點分別廣播一次HELL0-1 和HELL0-2 包。
3. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（1)和步 驟（2)所述的接收初始鄰節點發送的HELL0-1和HELL0-2包，是指網絡中的每個節點u接 收其鄰節點以最大發射功率Pmax廣播的JELLO-I和HELL0-2包。
4. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（3a)所 述的確定自己與兩跳鄰節點的連接關係，以及這些兩跳鄰節點之間的連接關係，建立局部 兩跳拓撲子圖Gf，按如下步驟進行： (3al)每個節點u根據接收到的一跳鄰節點的HELL0-1和HELL0-2包信息，獲取並記錄HELL0-1和HELL0-2包中節點的ID序列號和位置信息，這些鄰節點構成兩跳鄰節點集JWu2; (3a2)每個節點u根據自己的位置信息以及兩跳鄰節點的位置信息，計算任意兩個節 點x，y之間直接傳輸所需要的最小發射功率Px，y: K 其中，0為接收信噪比門限值，根據接收機的靈敏度和誤碼率要求確定，a 為路徑損耗因子，{u}表示節點u組成的集合，dx，y是節點x，y之間的歐式距離，若P"小於 節點的最大發射功率Pmax，則確定節點X，y之間存在連接關係；否則,節點X，y之間不存在連 接關係； (3a3)每個節點u根據兩跳鄰節點之間的連接關係，建立局部兩跳拓撲子圖G=(嚇無),￡(句))，其中局部拓撲子圖^的節點集合為八戌）=UM，局部拓撲子 圖Gu2 的邊集合為：AG,::) = .!(以)I三k)，L< /^、}。
5. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中所述步驟（4b) 中的最短路徑樹通過使用Dijkstra算法或Bellman-Ford算法構建。
6. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中所述步驟（4d) 中的斯坦納生成樹通過TMR算法構建。
7. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（4e)所 述的把LCNu和E(Su)的拓撲信息發送給Su中的所有節點，是網絡中的節點用最大發送功率 採用洪泛方式傳播拓撲信息。
8. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（7a)所 述的節點u向邏輯衝突鄰居集LCNu中的所有節點發送請求分配信道包RAC，是節點用最大 發送功率通過洪泛的方式傳播RAC包。
9. 根據權利要求1所述的認知AdHoc網絡的分布式拓撲控制方法，其中步驟（7b)所 述的LCNu中的所有節點在收到RAC包後，回饋信道分配包AC給節點u，是LCNu中的所有節 點用最大發送功率通過單播的方式把包AC發送給節點u。
【文檔編號】H04W84/18GK104507168SQ201410829689
【公開日】2015年4月8日 申請日期:2014年12月27日 優先權日:2014年12月27日
【發明者】王璽鈞, 盛敏, 翟道森, 張琰, 李建東, 郭彥濤 申請人:西安電子科技大學, 中國電子科技集團公司第五十四研究所