一種無線網絡分布式網同步退避參數優化方法
2023-05-24 17:18:51
專利名稱：一種無線網絡分布式網同步退避參數優化方法
一種無線網絡分布式網同步退避參數優化方法技術領域
本發明屬於無線網絡領域，特別涉及無線網絡分布式網同步退避參數優化方法。
技術背景
在分布式無線網絡環境中，節點採用分布式競爭廣播同步信標幀的方式實現網絡節點間的時間同步。分布式網同步過程由節點自發完成，不依賴於網絡中心節點的控制，因而具有組網快速靈活、可靠性高和抗毀性強的優勢。近年來，該方法已廣泛應用於各類分布式無線網絡，為時分多址信道接入控制、分布式節點休眠、分布式數據融合等應用提供網同步支持，例如美軍和北約組織廣泛應用的Linkl6數據鏈，IEEE802. 11無線區域網能量節省模式(Power Saving Model, PSM),物聯網信息採集與融合等。
附圖1給出了分布式網同步過程的流程圖，其具體步驟如下
步驟1:網絡中的每個節點在區間
內隨機選擇一個整數作為同步退避計數器的初始值，其中W為分布式網同步退避參數。
步驟2 :若節點檢測到信道持續空閒一個退避時隙長度的時間，則將同步退避計數器的值遞減I ;若節點檢測到信道變忙，則將當前退避計數器的值掛起；當節點同步退避計數器的值遞減至O後，則廣播攜帶本地時間信息的同步信標幀。
步驟3 :節點廣播同步信標幀結束後，在W個時隙長度的時間內繼續監聽信道，若在上述偵聽時間內節點偵聽到信道變忙，則判定自身同步信標幀廣播失敗，並嘗試接收其他節點廣播的同步信標幀。
步驟4 :若節點成功收到其他節點廣播的同步信標幀，則將自身的時間設置為同步信標幀中保存的時間，並在W個時隙長度內偵聽信道；若節點接收同步信標幀失敗，則恢復同步退避計數器的掛起值，並按照步驟2中的法則廣播自身的同步信標幀。
步驟5 :若所有節點在W個時隙長度內偵聽信道保持空閒，則分布式網同步過程結束。
由上述分析可知，退避參數W的取值對分布式網同步的性能有重要影響。在參與同步的網絡節點數量一定的條件下，如果W的取值過大，則會延長節點在網同步過程中的等待時間，導致網同步完成時間過長；反之，如果W的取值過小，則會使得節點在競爭廣播同步信標幀過程中的衝突加劇，同樣也會降低分布式網同步過程的效率。為了獲得最佳的分布式網同步效率，本發明採用離散馬爾可夫鏈對上述分布式網同步過程進行建模，得到網同步過程完成時間數學期望的表達式，並通過數值搜索法得到網同步退避參數的最優取值。發明內容
本發明的目的是針對無線網絡分布式網同步算法，提出一種退避參數優化方法， 從而獲得最佳的分布式網同步效率。為了實現該目的，本發明所採用的 步驟是
步驟1:採用二維離散馬爾可夫鏈對分布式網同步過程進行建模，節點在離散馬爾可夫鏈中的狀態用二維隨機變量{s(t)，b(t)}表示；其中，s(t)表示節點在同步過程中所處的階段，當S(t) = O時,表示節點處在廣播同步信標巾貞之前的退避階段；當s(t) = i時，表示節點與其他i個節點同時完成退避過程並同時廣播同步信標幀後，處在第i類偵聽階段；b(t)表示節點當前退避計數器的剩餘值；根據節點狀態之間的轉移關係得出離散馬爾可夫鏈非空一步狀態轉移概率。步驟2 :根據離散馬爾可夫鏈非空一步狀態轉移概率，得出退避階段和偵聽階段的穩態概率分布，並利用穩態概率分布的歸一化條件求出節點在單位時隙內廣播同步信標幀的概率。步驟3 :將節點分布式網同步過程完成時間分為兩部分，即節點首次廣播同步信標幀之前經歷的時間和節點首次廣播同步信標幀之後經歷的時間；根據節點在單位時隙內廣播同步信標幀的概率，採用迭代法分別確定上述兩部分時間長度的數學期望；將兩部分時間長度的期望相加即可得到分布式網同步過程完成時間的期望。步驟4:根據分布式網同步過程完成時間期望的表達式，通過數值搜索法確定給定網絡規模條件下分布式網同步退避參數的最優取值。本發明提出的無線網絡分布式網同步退避參數優化方法已經在EXata網絡仿真環境中實現。網絡節點在單跳傳輸範圍之內；考慮不同網絡規模條件，網絡節點總數量分別為20，30，40和50 ;物理層採用DSSS模型，信道傳輸速率為2Mbit/s ;網絡層採用靜態路由，傳輸層採用Μ)Ρ協議；節點晶振偏差為IOppm ;網同步周期為ls，仿真時間為300s。附圖3給出了在不同網絡規模條件下，通過改變分布式網同步退避參數W得到的分布式網同步過程完成時間的仿真值與本發明得到的計算值的對比。仿真值與計算值的一致性說明了本發明在不同退避參數W的取值條件下確定分布式網同步過程完成時間方法的有效性。在同步退避參數W 變化的條件下，本發明得到的分布式網同步過程完成時間計算值為凹函數，說明了本發明採用數值搜索法確定分布式網同步退避參數最優取值的有效性。
圖1是分布式網同步過程的流程圖；圖2是本發明採用的二維馬爾可夫鏈模型狀態轉移圖；圖3是本發明的仿真和計算結果圖。
具體實施例方式下面結合附圖和實施例對本發明作進一步詳細描述。本發明提出的無線網絡分布式網同步退避參數優化方法已經在無線網絡仿真環境EXata中實現，並通過仿真結果證明了該方法的有效性。下面給出本發明的具體實施步驟步驟1:採用離散馬爾可夫鏈對分布式網同步過程進行建模。針對分布式網同步過程，構建如附圖2所示的二維離散馬爾可夫鏈模型。任一節點的狀態用二維隨機變量{s(t)，b(t)}表示。其中，s(t)表示節點在同步過程中所處的階段,當s(t) = O時,表示節點處在廣播同步信標巾貞之前的退避階段,當S (t) =i時,表示節點與其他i個節點同時完成退避過程並同時廣播信標幀後，處在第i類偵聽階段；b(t)表示節點當前退避計數器的剩餘值。附圖2中其餘各變量的含義如下η:網絡中節點的數量；W 分布式網同步退避參數；q :節點在廣播同步信標幀之前的退避過程中，成功收到其他節點廣播的同步信標幀的概率；P1:節點與網絡中其他i個節點同時完成廣播同步信標幀之前的退避過程，並同時廣播同步信標幀的概率；P (Si):節點在第i類偵聽階段成功收到其他節點廣播的同步信標幀的概率；P (Ci):節點在第i類偵聽階段接收其他節點廣播的同步信標幀失敗的概率。用P(i I j)表示狀態j到i的一步狀態轉移概率，則附圖2所示的離散馬爾可夫鏈非空一步狀態轉移概率可以表示為
權利要求
1.一種無線網絡分布式網同步退避參數優化方法，所採用的步驟是步驟1:採用二維離散馬爾可夫鏈對分布式網同步過程進行建模，節點在離散馬爾可夫鏈中的狀態用二維隨機變量{s(t)，b(t)}表示；其中，s(t)表示節點在同步過程中所處的階段，當S(t) = O時,表示節點處在廣播同步信標巾貞之前的退避階段；當s(t) = i時, 表示節點與其他i個節點同時完成退避過程並同時廣播同步信標幀後，處在第i類偵聽階段；b(t)表示節點當前退避計數器的剩餘值；根據節點狀態之間的轉移關係得出離散馬爾可夫鏈非空一步狀態轉移概率；步驟2 :根據離散馬爾可夫鏈非空一步狀態轉移概率，得出退避階段和偵聽階段的穩態概率分布，並利用穩態概率分布的歸一化條件求出節點在單位時隙內廣播同步信標幀的概率；步驟3 :將節點分布式網同步過程完成時間分為兩部分，即節點首次廣播同步信標幀之前經歷的時間和節點首次廣播同步信標幀之後經歷的時間；根據節點在單位時隙內廣播同步信標幀的概率，採用迭代法分別確定上述兩部分時間長度的數學期望；將兩部分時間長度的期望相加即可得到分布式網同步過程完成時間的期望；步驟4 :根據分布式網同步過程完成時間期望的表達式，通過數值搜索法確定給定網絡規模條件下分布式網同步退避參數的最優取值。
2.根據權利要求1所述的一種無線網絡分布式網同步退避參數優化方法，其特徵在於二維離散馬爾可夫鏈非空一步狀態轉移概率的具體確定方法為定義以下變量 η :網絡中節點的數量；W :分布式網同步退避參數；q 節點在廣播同步信標幀之前的退避過程中，成功收到其他節點廣播的同步信標幀的概率；P1:節點與網絡中其他i個節點同時完成廣播同步信標幀之前的退避過程，並同時廣播同步信標幀的概率；P (Si):節點在第i類偵聽階段成功收到其他節點廣播的同步信標幀的概率；P(Ci):節點在第i類偵聽階段接收其他節點廣播的同步信標幀失敗的概率；P(i I j):狀態j到i的一步狀態轉移概率；離散馬爾可夫鏈非空一步狀態轉移概率可以表示為
3.根據權利要求1所述的一種無線網絡分布式網同步退避參數優化方法，其特徵在於節點在單位時隙內廣播同步信標幀概率的具體確定方法為用τ表示節點在單位時隙內廣播同步信標幀的概率，用Pm表示馬爾可夫鏈的穩態概率分布，即 Pi, j = Iimt ^00Pis (t) = i,b(t) = j}，i e [O, ff], j e
,則退避階段和偵聽階段的穩態概率分布可分別用式(2)和式(3)表示，SP
4.根據權利要求1所述的一種無線網絡分布式網同步退避參數優化方法，其特徵在於分布式網同步過程完成時間數學期望的具體確定方法為用T表示分布式網同步過程完成時間；分別用δ和ε表示空閒退避時隙長度和同步信標幀的傳輸時間；用Pidle表示節點在退避階段的退避過程中監聽信道空閒的概率，其值可通過節點在單位時隙內廣播同步信標幀概率確定，即 Pidle=Q-T)1"1 (11)則退避階段時隙長度σ的期望值可表示為
全文摘要
本發明公開了一種無線網絡分布式網同步退避參數優化方法。該方法採用二維離散馬爾可夫鏈對分布式網同步過程進行建模，根據非空一步狀態轉移概率得出分布式網同步過程退避階段和偵聽階段的穩態概率分布，並利用穩態概率歸一化條件求出節點在單位時隙內廣播同步信標幀的概率。然後將節點分布式網同步過程完成時間分為兩部分，即節點首次廣播同步信標幀之前經歷的時間和節點首次廣播同步信標幀之後經歷的時間，並採用迭代法確定分布式網同步過程完成時間的數學期望。最後根據時間期望表達式，通過數值搜索法確定給定網絡規模條件下分布式網同步退避參數的最優取值。無線網絡仿真環境EXata中的仿真實驗證明了該方法的有效性。
文檔編號H04W24/06GK103068033SQ20131003297
公開日2013年4月24日 申請日期2013年1月29日 優先權日2013年1月29日
發明者雷磊, 戚龍飛, 蔡聖所, 張雅靜, 羅誠, 張婷, 李科豔, 陳曉明 申請人:南京航空航天大學