一種基於無線有損網絡降低構建開銷的拓撲控制方法
2023-09-20 22:14:40
一種基於無線有損網絡降低構建開銷的拓撲控制方法
【專利摘要】本發明公開了一種基於無線有損網絡有效降低構建開銷的拓撲控制方法，無線有損網絡中任一網絡節點u均執行如下步驟：1）根據用戶要求設定無線有損網絡的伸展因子t；2）獲取節點u的最大發射功率鏈路數據集TABmaxu；3）更改節點u的發射功率廣播探測包；4）將節點u的鄰接鏈路數據集H和最短路徑集合PATH初始化為空；5）獲得當前發射功率鏈路數據集TABku；6）更新鄰接鏈路數據集H；7）更新最短路徑集合PATH；8）從步驟7獲得的最短路徑集合中依次為每條鏈路找到替代路徑，從而確定節點u在無線有損網絡中的發射功率；有效降低無線有損網絡環境下拓撲構建的通信開銷與時間開銷；同時有效降低網絡節點平均發射功率等級。
【專利說明】一種基於無線有損網絡降低構建開銷的拓撲控制方法
【技術領域】
[0001]本發明屬於計算機網絡應用和無線網絡拓撲控制技術，涉及一種無線有損網絡的拓撲控制技術，特別涉及一種基於無線有損網絡有效降低構建開銷的拓撲控制方法。
【背景技術】
[0002]隨著無線網絡技術的發展以及具有感知和通信能力的微電子器件成本的大幅降低，萬物互聯正在悄然形成。無線節點間的通信在「通」和「斷」之間，通常存在一個「過渡」區。在這個區域，無線節點間的通信以一定的概率連通。直觀表現在發射源對同一數據包要發送多次才能成功，這將額外消耗節點的能量。拓撲控制是試圖降低節點發射功率而同時能維持所期望的拓撲屬性的關鍵技術，簡單地說，它能為節點確定一個合適的發射功率。無線網絡中的有損鏈路普遍存在，而考慮有損鏈路的拓撲控制方法卻不多見。傳統的基於「通」與「斷」條件下的拓撲控制方法用於無線有損鏈路環境下，會使得對「通」與「斷」的定義很不統一，如連通概率多大算「通」;相反，直接使用連通概率作為鏈路權值則比較方便。
[0003]CTC算法(參見參考文獻[I])屬於典型的無線有損網絡拓撲控制方法，該算法將鏈路連通概率轉換成在鏈路上成功傳輸特定長度數據包所需要的最少傳輸次數，並將其作為鏈路權值。在此基礎上，給出了傳輸次數伸展因子DTC(Dilation of TransmissionCount)的概念，即網絡中任意一對節點在拓撲控制方法執行後形成的拓撲上的最短路徑權值與原始拓撲(即網絡中所有節點都採用最大發射功率等級時形成的拓撲)上同一對節點間的最短路徑權值之間都有一個比值，而在這些比值中，最大的那個比值即為DTC。DTC給出了該鏈路權值作為拓撲性能指標，其性能與最優值之間的最大差距。
[0004]CTC算法是一組局部搜索算法，其基本思想是，網絡中每個節點都獨立運行CTC，而運行該算法的節點以其I跳鄰域內的每個節點為參數，依次調用函數LabelSet(V)(該函數的參數V為執行節點的I跳鄰域內的一個節點)來確定其該採用的發射功率級別，最終確定的發射功率要能滿足其I跳鄰域內所有節點的要求。節點的I跳鄰域是指該節點與其鄰居節點以及這些節點間存在的通信鏈路所形成的區域。
[0005]LabelSet (v)基本思想是,調用該函數的節點,對節點V在最大發射功率級別下的每條鏈路，在其2跳鄰域內搜索DTC值不超過預先給定的DTC上界值的替代路徑，並在滿足要求的替代路徑中，選擇具有最小發射功率度量值的替代路徑以替換該鏈路，然後通過檢查自身是否在替代路徑上以及該路徑對其功率的要求是否大於當前採用功率來決定是否需要更新其發射功率，若大於，則更新其當前採用的發射功率。節點的2跳鄰域是指該節點和其所有鄰居節點的I跳鄰域所組成的區域。
[0006]CTC算法能夠通過調整DTC上界值、替代路徑長度等參數來取得替代路徑質量與搜索開銷之間的折中。然而CTC算法需要將其2跳範圍內所有功率等級下的鏈路權值作為其輸入參數之一，這顯然增大了其搜索到合適發射功率的時間開銷，而2跳範圍內所有發射功率等級下的鏈路權值的取得也需要很大的通信開銷。CTC算法存在的具體問題如下:
[0007](I )CTC算法假設存在某種算法，能為每個節點求得其2跳範圍內所有發射功率等級下的鏈路權值。但實際上，尚未發現這樣一種算法的具體描述。另外，簡單地對重傳次數進行統計可以很容易獲得鏈路(例如U — V)所採用的Rl^i (即含義是節點U採用第i級功率向節點V發送同一數據包，被節點V成功收到時所需最少傳輸次數)，而用這個指標來度量該鏈路傳輸質量並不總是合理的。例如，Ru，v，i=3，可能是前2次數據包在從u到V的傳輸過程中出錯，第3次成功；也可能是前2次數據包的確認包在從V到u的傳輸過程中出錯，第3次成功。儘管兩種情況下Rl^i的值相同，但顯然前者的鏈路質量比後者差。有些研究將鏈路正反方向的傳輸成功率乘積的倒數作為鏈路質量的度量，這顯然忽略了鏈路正反方向存在的傳輸質量差異。
[0008](2)節點的發射功率等級很多，一些產品達30餘級，估算全部發射功率等級下的鏈路質量，計算代價、消息開銷、存儲代價等過大，而且也會增大求解合適發射功率的搜索空間、增加時間開銷。
[0009](3)採用被動監聽的方式，雖然可以節省開銷，但是實際未必可行。一是難以保證及時估算動態變化的鏈路質量；二是難以得到所有發射功率等級下的鏈路質量，因為節點不太可能對其所有發射功率等級都使用一遍。
[0010]因此，急需提出一種應對上述問題的新拓撲控制方法。
【發明內容】
[0011]本發明提出的一種基於無線有損網絡有效降低構建開銷的拓撲控制方法，其目的在於克服現有技術搜索空間大、拓撲構建時間長以及通信開銷大等問題。
[0012]一種基於無線有損網絡降低構建開銷的拓撲控制方法，無線有損網絡中任一網絡節點U均執行如下步驟:
[0013]步驟1:根據用戶要求設定無線有損網絡的伸展因子t，t的取值範圍是大於I且小於6的整數；`
[0014]步驟2:獲取節點u的最大發射功率鏈路數據集TABmaxu ；
[0015]以節點u的最大發射功率Pmaxu廣播探測包，節點u接收該探測包的響應包獲得節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值，同時將節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值保存於節點u的最大發射功率鏈路數據集TABmaxu中，鄰居節點ID為鄰居節點的唯一標識符，表示節點身份；
[0016]步驟3:更改節點u的發射功率廣播探測包；
[0017]即更換節點u的發射功率，與上一次的發射功率不同；
[0018]步驟4:將節點u的鄰接鏈路數據集H和最短路徑集合PATH初始化為空；
[0019]其中，節點u的鄰接鏈路數據集H用於保存節點u的ID、節點u的鄰居節點ID以及所有保存的鄰居節點之間的鏈路權值；
[0020]即保存了任意兩個鄰居節點之間的鏈路權值；
[0021 ] 節點u的最短路徑集合PATH是指用於保存節點u到鄰接鏈路數據集H中除節點u本身之外的每個節點的最短路徑；
[0022]步驟5:獲得當前發射功率鏈路數據集TABku ；
[0023]節點u接收步驟3廣播探測包的響應包，獲得節點u的鄰居節點ID以及鄰居節點之間的鏈路權值，並保存於節點u的當前發射功率鏈路數據集TABku中，其中，k表示節點u使用第k級發射功率廣播探測包；
[0024]步驟6:更新鄰接鏈路數據集H ；
[0025]節點u與在節點u的I跳鄰域內的鄰居節點通過交換進行信息共享，將節點u所在的I跳鄰域內的所有節點之間的鏈路權值保存在鄰接鏈路數據集H中；
[0026]步驟7:更新最短路徑集合PATH ；
[0027]依據步驟6獲得的鄰接鏈路數據集H構建鏈路結構圖，利用Dijkstra算法將求得的節點u到鏈路結構圖上的其他每個節點的最短路徑保存在最短路徑集合PATH中；
[0028]步驟8:針對最大發射功率鏈路數據集TABmaxu中的每條鏈路，依次從步驟7獲得的最短路徑集合PATH中尋找路徑起始節點與該鏈路起始節點相同的路徑作為其替代路徑；
[0029]若該替代路徑上的鏈路權值之和大於當前鏈路的鏈路權值的t倍，則返回步驟3 ；
[0030]若該替代路徑上的鏈路權值之和小於或等於當前鏈路的鏈路權值的t倍，則以步驟3確定的節點發射功率作為節點u在無線有損網絡中的發射功率。
[0031]網絡中所有節點通過上述步驟可以較快地從其可選的眾多發射功率級別中確定其合適的發射功率,從而形成了整個網絡拓撲。
[0032]所述節點先廣播探測包，然後通過接收該探測包的響應包來獲得節點U的鄰居節點以及與鄰居節點之間的鏈路權值的具體步驟如下:
[0033]步驟a:設定網絡應用中所能容忍的節點數據重傳次數T，並將用於計算鏈路權值的變量R和記錄循環體執行次數的變量i初始化為0，接收數據集Su，當前發射功率鏈路數據集TABku,鄰居節點列表NEIulist分別初始化為空；
[0034]其中，R用於記錄節點u以廣播方式發送鄰居發現消息包的輪次，i表示節點u執行循環體的次數，Su用於記錄節點u成功收到的鄰居節點發送的同一個發現消息包的次數以及該鄰居節點ID, NEIulist為節點u的鄰居節點列表,用於記錄節點u已經發現的相鄰居點名稱，數據集TABku用於記錄節點u選用發射功率k廣播探測包獲得的與鄰居節點之間的鏈路權值；
[0035]步驟b:判斷計算變量i是否等於T，如果是，則結束所有操作；否則，進入步驟c ;
[0036]步驟c:節點u將變量R增大1，並使用發射功率Pku以廣播方式發送發現消息包[TYPEndm, IDu, NEIulist]，同時啟動定時器 th ；
[0037]R用於記錄節點u以廣播方式發送鄰居發現消息包的輪次即指用來計算節點u與鄰居節點之間的鏈路權值，比如，在響應包不出錯的情況下，當R=I時，若節點u成功收到鄰居節點對它探測包的響應包，則節點u認為與鄰居節點的鏈路權值是I ;然後，在變量i的值未超過T時，節點u會繼續發同樣的探測包，因此R就會增加到2，這時若又有鄰居節點的響應包被節點u成功收到，則節點u認為與這個或這些鄰居間的鏈路權值是2 ；
[0038]步驟d:判斷定時器th是否超時，若未超時，則進入步驟e，否則，將變量i的值加I後返回步驟b ；
[0039]定時器th是網絡節點從廣播發現消息包開始到正常接收相應響應包的時間，為每個節點的固有屬性；
[0040]步驟e:若節點u成功接收到來自節點V廣播的發現消息包[TYPEndm, IDv, NEIvlisJ且節點u尚不在節點V的相鄰節點列表NEIvlist中，則執行步驟f，否則，進入步驟g ；
[0041]步驟f:判斷節點V是否存在於節點u的接收數據集Su中；[0042]若節點V不存在於節點U的接收數據集Su中:
[0043]將節點u對節點V的響應次數COUv置為1，並將[IDV，COUv]加入Su中；接著節點U使用發射功率Pku向節點V發送響應消息包[TYPEmm，IDv, IDu, COUJ ；
[0044]否則，若節點V已存在接收節點u的接收數據集Su中:
[0045]將節點u對節點V的響應次數COUv增大I ;接著節點u使用發射功率Pku向節點V發送響應消息包[TYPEnrm, IDv, IDu, COUJ ；
[0046]COUv是一個記錄響應次數的變量,下標V表示被響應的對象,指節點u對節點V發送的同一個發現消息包的響應次數；
[0047]步驟g:若節點U成功收到來自節點V發送的鄰居響應消息包[TYPEnrm, IDu, IDv, COUJ，則將鏈路權值變量賦值為R_C0UU+1，並將鏈路[u，v, Ru；v；k]和節點v分別加入到數據集TABku和NEIulist中；
[0048]其中，所述發現消息包[TYPEndm, IDu, NEIulisJ中三個欄位的含義分別是包類型為發現消息包、發送節點標識、發送節點已知的相鄰節點列表；
[0049]所述響應消息包[TYPE_ IDu, IDv, COUu]中四個欄位的含義分別是包類型為響應消息包、接收節點U標識、發送節點V標識、節點V對節點U發送的同一個發現消息包的響應次數，其中被響應對象為節點U。
[0050]所述步驟3中更改節點u的發射功率廣播探測包的更改方法包括以下三種:
[0051]I)逐級更改發射功率廣播探測包:
[0052]從最低發射功率開始廣播探測包,往後每次增加一級發射功率；
[0053]2)加倍更改發射功率廣播探測包:
[0054]首先從最低發射功率開始廣播探測包，往後以前一次發射功率的兩倍廣播探測包，當發射功率到達設定的閾值時，接著逐級增加發射功率廣播探測包；
[0055]所述閾值為發射功率的中間等級發射功率；
[0056]3)折半更改發射功率廣播探測包:
[0057]首先，從節點的發射功率等級範圍的中間級別發射功率開始廣播探測包，若每條鏈路滿足預定約束條件，則尋找是否存在更小的節點發射功率，如果不存在，則以前一個滿足預定約束條件下的節點發射功率作為待確定的節點發射功率；否則，則繼續在高一半的搜索範圍內以相同的方式折半搜索；
[0058]所述預定約束是指，對每條鏈路，其替代路徑上鏈路權值之和都小於或等於該鏈路的鏈路權值的t倍，t是指伸展因子。
[0059]有益效果
[0060]本發明提出的一種基於無線有損網絡有效降低構建開銷的拓撲控制方法，不同於現有方法採用的局部窮盡搜索方式來確定合適的節點發射功率，我們採用逐級增大(或翻倍逐級增大、或折半確定)發射功率的搜索方式，若滿足約束條件，則停止搜索，因此，不必窮盡局部範圍的所有可能結果，更不必事先求得節點所有功率等級下的鏈路權值。
[0061]本發明的有益效果具體體現在以下幾個方面:
[0062]I)本發明能夠有效降低無線有損網絡環境下拓撲構建的通信開銷與時間開銷；
[0063]2)本發明能夠有效降低網絡節點平均發射功率等級；
[0064]3)本發明構建的網絡拓撲在常見使用條件下的平均剩餘能量偏差更小，因而網絡 壽命更長。
【專利附圖】
【附圖說明】
[0065]圖1為3種方法的平均發射功率隨應用要求的伸展因子改變的變化趨勢圖；
[0066]圖2為3種方法的平均端到端延時隨應用要求的伸展因子改變的變化趨勢圖；
[0067]圖3為3種方法的平均投遞成功率隨應用要求的伸展因子改變的變化趨勢圖；
[0068]圖4為3種方法的總能量消耗隨應用要求的伸展因子改變的變化趨勢圖；
[0069]圖5為3種方法的剩餘能量均方差隨應用要求的伸展因子改變的變化趨勢圖；
[0070]圖6為3種方法的平均測量的伸展因子隨應用要求的伸展因子改變的變化趨勢圖；
[0071]圖7為3種方法的平均發射功率隨節點密度改變的變化趨勢圖；
[0072]圖8為3種方法的平均端到端延時隨節點密度改變的變化趨勢圖；
[0073]圖9為3種方法的平均投遞成功率隨節點密度改變的變化趨勢圖；
[0074]圖10為3種方法的總能量消耗隨節點密度改變的變化趨勢圖；
[0075]圖11為3種方法的剩餘能量均方差隨節點密度改變的變化趨勢圖；
[0076]圖12為3種方法的平均測量的伸展因子隨節點密度改變的變化趨勢圖；
[0077]圖13為3種方法的總能量消耗隨發射源節點數量改變的變化趨勢圖；
[0078]圖14為3種方法的剩餘能量均方差隨發射源節點數量改變的變化趨勢圖；
[0079]其中，所述3種方法分別為本發明提出的LTCAL-node以及參考文獻[I]中的兩種典型方法 CTC-node-ms 與 CTC-node-mm。
【具體實施方式】
[0080]下面結合附圖和具體實施例對本發明作進一步說明。
[0081]一種基於無線有損網絡降低構建開銷的拓撲控制方法，無線有損網絡中任一網絡節點u均執行如下步驟:
[0082]步驟1:根據用戶要求設定無線有損網絡的伸展因子t，t的取值範圍是大於I且小於6的整數；
[0083]步驟2:獲取節點u的最大發射功率鏈路數據集TABmaxu ；
[0084]以節點u的最大發射功率Pmaxu廣播探測包，節點u接收該探測包的響應包獲得節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值，同時將節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值保存於節點u的最大發射功率鏈路數據集TABmaxu中，鄰居節點ID為鄰居節點的唯一標識符，表示節點身份；
[0085]步驟3:更改節點u的發射功率廣播探測包；
[0086]即更換節點u的發射功率，與上一次的發射功率不同；
[0087]步驟4:將節點u的鄰接鏈路數據集H和最短路徑集合PATH初始化為空；
[0088]其中，節點u的鄰接鏈路數據集H用於保存節點u的ID、節點u的鄰居節點ID以及所有保存的鄰居節點之間的鏈路權值；
[0089]即保存了任意兩個鄰居節點之間的鏈路權值；
[0090]節點u的最短路徑集合PATH是指用於保存節點u到鄰接鏈路數據集H中除節點U本身之外的每個節點的最短路徑；
[0091]步驟5:獲得當前發射功率鏈路數據集TABku ；
[0092]節點u接收步驟3廣播探測包的響應包，獲得節點u的鄰居節點ID以及鄰居節點之間的鏈路權值，並保存於節點u的當前發射功率鏈路數據集TABku中，其中，k表示節點u使用第k級發射功率廣播探測包；
[0093]步驟6:更新鄰接鏈路數據集H ；
[0094]節點u與在節點u的I跳鄰域內的鄰居節點通過交換進行信息共享，將節點u所在的I跳鄰域內的所有節點之間的鏈路權值保存在鄰接鏈路數據集H中；
[0095]步驟7:更新最短路徑集合PATH ；
[0096]依據步驟6獲得的鄰接鏈路數據集H構建鏈路結構圖，利用Dijkstra算法將求得的節點u到鏈路結構圖上的其他每個節點的最短路徑保存在最短路徑集合PATH中；
[0097]步驟8:針對最大發射功率鏈路數據集TABmaxu中的每條鏈路，依次從步驟7獲得的最短路徑集合PATH中尋找路徑起始節點與該鏈路起始節點相同的路徑作為其替代路徑；
[0098]若該替代路徑上的鏈路權值之和大於當前鏈路的鏈路權值的t倍，則返回步驟3 ；
[0099]若該替代路徑上的鏈路權值之和小於或等於當前鏈路的鏈路權值的t倍，則以步驟3確定的節點發射功率作為節點u在無線有損網絡中的發射功率。
[0100]網絡中所有節點通過上述步驟可以較快地從其可選的眾多發射功率級別中確定其合適的發射功率,從而形成了整個網絡拓撲。
[0101]所述節點先廣播探測包，然後通過接收該探測包的響應包來獲得節點U的鄰居節點以及與鄰居節點之間的鏈路權值的具體步驟如下:
[0102]步驟a:設定網絡應用中所能容忍的節點數據重傳次數T，並將用於計算鏈路權值的變量R和記錄循環體執行次數的變量i初始化為0，接收數據集Su，當前發射功率鏈路數據集TABku,鄰居節點列表NEIulist分別初始化為空；
[0103]其中，R用於記錄節點u以廣播方式發送鄰居發現消息包的輪次，i表示節點u執行循環體的次數，Su用於記錄節點u成功收到的鄰居節點發送的同一個發現消息包的次數以及該鄰居節點ID, NEIulist為節點u的鄰居節點列表,用於記錄節點u已經發現的相鄰居點名稱，數據集TABku用於記錄節點u選用發射功率k廣播探測包獲得的與鄰居節點之間的鏈路權值；
[0104]步驟b:判斷計算變量i是否等於T，如果是，則結束所有操作；否則，進入步驟c ;
[0105]步驟c:節點u將變量R增大1，並使用發射功率Pku以廣播方式發送發現消息包[TYPEndm, IDu, NEIulist]，同時啟動定時器 th ；
[0106]R用於記錄節點u以廣播方式發送鄰居發現消息包的輪次即指用來計算節點u與鄰居節點之間的鏈路權值，比如，在響應包不出錯的情況下，當R=I時，若節點u成功收到鄰居節點對它探測包的響應包，則節點u認為與鄰居節點的鏈路權值是I ;然後，在變量i的值未超過T時，節點u會繼續發同樣的探測包，因此R就會增加到2，這時若又有鄰居節點的響應包被節點u成功收到，則節點u認為與這個或這些鄰居間的鏈路權值是2 ；
[0107]步驟d:判斷定時器th是否超時，若未超時，則進入步驟e，否則，將變量i的值加I後返回步驟b ；
[0108]定時器th是網絡節點從廣播發現消息包開始到正常接收相應響應包的時間，為每個節點的固有屬性；
[0109]步驟e:若節點u成功接收到來自節點V廣播的發現消息包[TYPEndm, IDv, NEIvlisJ且節點u尚不在節點V的相鄰節點列表NEIvlist中，則執行步驟f，否則，進入步驟g ；
[0110]步驟f:判斷節點V是否存在於節點u的接收數據集Su中；
[0111]若節點V不存在於節點u的接收數據集Su中:
[0112]將節點u對節點V的響應次數COUv置為1，並將[IDV，COUv]加入Su中；接著節點U使用發射功率Pku向節點V發送響應消息包[TYPEmm，IDv, IDu, COUJ ；
[0113]否則,若節點V已存在接收節點u的接收數據集Su中:
[0114]將節點U對節點V的響應次數COUv增大I ;接著節點u使用發射功率Pku向節點V發送響應消息包[TYPEnrm, IDv, IDu, COUJ ；
[0115]COUv是一個記錄響應次數的變量,下標V表示被響應的對象,指節點u對節點V發送的同一個發現消息包的響應次數；
[0116]步驟g:若節點U成功收到來自節點V發送的鄰居響應消息包[TYPEnrm, IDu, IDv, COUJ，則將鏈路權值變量賦值為R_C0UU+1，並將鏈路[u，v, Ru；v；k]和節點v分別加入到數據集TABku和NEIulist中；
[0117]其中，所述發現消息包[TYPEndm, IDu, NEIulisJ中三個欄位的含義分別是包類型為發現消息包、發送節點標識、發送節點已知的相鄰節點列表；
[0118]所述響應消息包[TYPE_ IDu, IDv, COUu]中四個欄位的含義分別是包類型為響應消息包、接收節點U標識、發送節點V標識、節點V對節點U發送的同一個發現消息包的響應次數，其中被響應對象為節點U。
[0119]所述步驟3中更改節點u的發射功率廣播探測包的更改方法包括以下三種:
[0120]I)逐級更改發射功率廣播探測包:
[0121]從最低發射功率開始廣播探測包,往後每次增加一級發射功率；
[0122]2)加倍更改發射功率廣播探測包:
[0123]首先從最低發射功率開始廣播探測包，往後以前一次發射功率的兩倍廣播探測包，當發射功率到達設定的閾值時，接著逐級增加發射功率廣播探測包；
[0124]所述閾值為發射功率的中間等級發射功率；
[0125]3)折半更改發射功率廣播探測包:
[0126]首先，從節點的發射功率等級範圍的中間級別發射功率開始廣播探測包，若每條鏈路滿足預定約束條件，則尋找是否存在更小的節點發射功率，如果不存在，則以前一個滿足預定約束條件下的節點發射功率作為待確定的節點發射功率；否則，則繼續在高一半的搜索範圍內以相同的方式折半搜索；
[0127]所述預定約束是指，對每條鏈路，其替代路徑上鏈路權值之和都小於或等於該鏈路的鏈路權值的t倍，t是指伸展因子。
[0128]首先簡單介紹一下進行比較的3種基於無線有損網絡的拓撲控制方法:
[0129]l)LTCAL-node:該方法僅為每個節點維持一個能夠覆蓋其最遠鄰居且滿足應用要求的伸展因子約束的發射功率。任一節點在其I跳鄰域範圍內構建到其它所有鄰域節點的最短路徑，並將路徑上與自己相鄰的節點作為拓撲控制後的鄰居。路徑權值是路徑上所有鏈路權值的累加。該方法採取逐級增大(或翻倍逐級增大、或折半確定)發射功率的方式確定滿足伸展因子約束條件的適合發射功率。若存在不滿足應用要求的伸展因子約束的最短路徑，則增大一級發射功率，依次類推，直至滿足約束要求。具體算法描述見前述。
[0130]2) CTC-node-ms:該方法的基本思想是，運行該方法的節點在其2跳鄰域內，為其每個鄰域節點計算能替換其每條最大功率鏈路的替換路徑，要求替換路徑長度不超過d跳(在實施例中d取3)且滿足應用要求的伸展因子約束。在滿足這些要求的替換路徑中，選擇路徑上鏈路起始節點發射功率累加和最小的替換路徑。若運行該方法的節點被包括在替換路徑上，則根據該路徑對該節點的功率要求更新其發射功率。若要求的功率值大於當前功率，則更新。
[0131]3) CTC-node-mm:除了採用路徑上最大權值鏈路的權值作為路徑權值外，其它與CTC-node-ms 相同。
[0132]比較的性能參數描述如下:
[0133]I)平均發射功率:是指在拓撲控制算法執行後，網絡中所有節點確定採納的發射功率的均值。對任一節點u來說，其確定採納的發射功率記作Pu。全網均值由
【權利要求】
1.一種基於無線有損網絡降低構建開銷的拓撲控制方法，其特徵在於，無線有損網絡中任一網絡節點U均執行如下步驟: 步驟1:根據用戶要求設定無線有損網絡的伸展因子t，t的取值範圍是大於I且小於6的整數； 步驟2:獲取節點u的最大發射功率鏈路數據集TABmaxu ； 以節點u的最大發射功率Pmaxu廣播探測包，節點u接收該探測包的響應包獲得節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值，同時將節點u的鄰居節點ID以及節點u與鄰居節點之間的鏈路權值保存於節點u的最大發射功率鏈路數據集TABmaxu中，鄰居節點ID為鄰居節點的唯一標識符，表示節點身份； 步驟3:更改節點u的發射功率廣播探測包； 步驟4:將節點u的鄰接鏈路數據集H和最短路徑集合PATH初始化為空； 其中，節點u的鄰接鏈路數據集H用於保存節點u的ID、節點u的鄰居節點ID以及所有保存的鄰居節點之間的鏈路權值； 節點u的最短路徑集合PATH是指用於保存節點u到鄰接鏈路數據集H中除節點u本身之外的每個節點的最短路徑； 步驟5:獲得當前發射功率鏈路數據集TABku ； 節點u接收步驟3廣播探測包的響應包，獲得節點u的鄰居節點ID以及鄰居節點之間的鏈路權值，並保存於節點`u的當前發射功率鏈路數據集TABku中，其中，k表示節點u使用第k級發射功率廣播探測包； 步驟6:更新鄰接鏈路數據集H ； 節點u與在節點u的I跳鄰域內的鄰居節點通過交換進行信息共享，將節點u所在的I跳鄰域內的所有節點之間的鏈路權值保存在鄰接鏈路數據集H中； 步驟7:更新最短路徑集合PATH ； 依據步驟6獲得的鄰接鏈路數據集H構建鏈路結構圖，利用Dijkstra算法將求得的節點u到鏈路結構圖上的其他每個節點的最短路徑保存在最短路徑集合PATH中； 步驟8:針對最大發射功率鏈路數據集TABmaxu中的每條鏈路，依次從步驟7獲得的最短路徑集合PATH中尋找路徑起始節點與該鏈路起始節點相同的路徑作為其替代路徑； 若該替代路徑上的鏈路權值之和大於當前鏈路的鏈路權值的t倍，則返回步驟3 ；若該替代路徑上的鏈路權值之和小於或等於當前鏈路的鏈路權值的t倍，則以步驟3確定的節點發射功率作為節點u在無線有損網絡中的發射功率。
2.根據權利要求1所述的基於無線有損網絡降低構建開銷的拓撲控制方法，其特徵在於，所述節點先廣播探測包，然後通過接收該探測包的響應包來獲得節點u的鄰居節點以及與鄰居節點之間的鏈路權值的具體步驟如下: 步驟a:設定網絡應用中所能容忍的節點數據重傳次數T，並將用於計算鏈路權值的變量R和記錄循環體執行次數的變量i初始化為O，接收數據集Su，當前發射功率鏈路數據集TABku,鄰居節點列表NEIulist分別初始化為空； 其中，R用於記錄節點u以廣播方式發送鄰居發現消息包的輪次，i表示節點u執行循環體的次數，Su用於記錄節點u成功收到的鄰居節點發送的同一個發現消息包的次數以及該鄰居節點ID, NEIulist為節點u的鄰居節點列表,用於記錄節點u已經發現的相鄰居點名稱，數據集TABku用於記錄節點u選用發射功率k廣播探測包獲得的與鄰居節點之間的鏈路權值； 步驟b:判斷計算變量i是否等於T，如果是，則結束所有操作；否則，進入步驟c ； 步驟c:節點u將變量R增大1，並使用發射功率Pku以廣播方式發送發現消息包[TYPEndm, IDu, NEIulisJ，同時啟動定時器 th ； 步驟d:判斷定時器th是否超時，若未超時，則進入步驟e，否則，將變量i的值加I後返回步驟b; 步驟e:若節點u成功接收到來自節點V廣播的發現消息包[TYPEndm, IDv, NEIvlisJ且節點u尚不在節點V的相鄰節點列表NEIvlist中，則執行步驟f，否則，進入步驟g ； 步驟f:判斷節點V是否存在於節點u的接收數據集Su中； 若節點V不存在於節點u的接收數據集Su中: 將節點u對節點V的響應次數COUv置為1，並將[IDV，COUJ加入Su中；接著節點u使用發射功率Pku向節點V發送響應消息包[TYPE_ IDv, IDu, COUJ ； 否則，若節點V已存在接收節點u的接收數據集Su中: 將節點u對節點V的響應次數COUv增大I ;接著節點u使用發射功率pku向節點V發送響應消息包[TYPEnrm, IDv, IDu, COUJ ； COUv是一個記錄響應次數的變量,下標V表示被響應的對象，指節點U對節點V發送的同一個發現消息包的響應次數；` 步驟g:若節點u成功收到來自節點V發送的鄰居響應消息包[TYPEnrm, IDu, IDv, COUJ，則將鏈路權值變量賦值為R-C0UU+1，並將鏈路[U，V, Ru；v；k]和節點V分別加入到數據集TABku和 NEIulist 中； 其中，所述發現消息包[TYPEndffl, IDu, NEIulisJ中三個欄位的含義分別是包類型為發現消息包、發送節點標識、發送節點已知的相鄰節點列表； 所述響應消息包[TYPEmm，IDu, IDv, COUJ中四個欄位的含義分別是包類型為響應消息包、接收節點U標識、發送節點V標識、節點V對節點U發送的同一個發現消息包的響應次數，其中被響應對象為節點U。
3.根據權利要求1或2所述的基於無線有損網絡降低構建開銷的拓撲控制方法，其特徵在於，所述步驟3中更改節點u的發射功率廣播探測包的更改方法包括以下三種: 1)逐級更改發射功率廣播探測包: 從最低發射功率開始廣播探測包,往後每次增加一級發射功率； 2)加倍更改發射功率廣播探測包: 首先從最低發射功率開始廣播探測包，往後以前一次發射功率的兩倍廣播探測包，當發射功率到達設定的閾值時，接著逐級增加發射功率廣播探測包； 所述閾值為發射功率的中間等級發射功率； 3)折半更改發射功率廣播探測包: 首先，從節點的發射功率等級範圍的中間級別發射功率開始廣播探測包，若每條鏈路滿足預定約束條件，則尋找是否存在更小的節點發射功率，如果不存在，則以前一個滿足預定約束條件下的節點發射功率作為待確定的節點發射功率；否則，則繼續在高一半的搜索範圍內以相同的方式折半搜索；所述預定約束是指，對每條鏈路，其替代路徑上鏈路權值之和都小於或等於該鏈路的鏈路權值的t倍，t是指伸展因子。`
【文檔編號】H04W28/16GK103826266SQ201410114402
【公開日】2014年5月28日 申請日期:2014年3月25日 優先權日:2014年3月25日
【發明者】桂勁松 申請人:中南大學