分組無線網分群后的隱藏終端問題分析

　　 
　　一、 引言
　　現代空軍作為海陸空聯合作戰的重要組成部分，不僅要求戰機裝備多種先進電子設備，將各種功能高度綜合，提高單機戰斗和生存能力，還要求機群之間、飛機與地面部隊、艦隊以及地面指控中心在戰時能迅速建立無線戰術信息網絡，

保證各種軍事信息高度共享和互通，提高整個作戰體系的統一指揮和協同作戰能力。這對于空中飛機組網提出了嚴格的要求。飛機機動性強，高速移動，通過機載電臺聯成空中移動通信網。這是一種分組無線網［１～３］(PRN,即Packet Radio Network)，與確定性連接網絡比較，PRN網絡具有2個顯著特性：廣播媒介和動態拓撲。廣播媒介使節點能與其所有一跳節點直接通信，但為避免沖突必須限制同時發送的節點數；無線信道支持節點自由移動，但節點移動導致網絡拓撲動態變化，從而帶來很多新問題。因此，PRN網絡必須建立穩健有效的網絡管理方法，來解決沖突和動態拓撲問題。
　　對于無線網絡，隱藏終端［４～７］也是一個嚴重影響通信性能的問題。隱藏終端問題發生在相距兩跳的２個節點同時發送報文的情況下，這時２個節點的公共接收節點處將產生沖突，導致網絡吞吐量和延時性能急劇下降。文獻［４］分析了無線局域網中隱藏終端的影響，提出了單信道下無線局域網的完整解決方案；文獻［５］提出了一種新的基于FAMA (Floor AcquisitionMultiple Aclearcase/" target="_blank" >ccess)協議來分析PRN中的隱藏終端的方法。文獻［6］提出一種基于捎帶幀來解決VHF數據鏈中藏終端問題的方案；文獻［７］對于CDMA體制下分組無線網隱藏終端問題開展研究，提出了一種基于RTS/CTS調度的多址方式來解決隱藏終端問題。對于采用分群算法分群后的PRN，隱藏終端問題更加錯綜復雜，對于此類問題尚未檢索到相關研究文獻。?
　　
　　二、概述
　　1?基本定義和假設
　　為論述方便首先介紹采用的幾個定義和假設。
　　(1)假設網絡中各節點發射功率相同，不考慮功率控制，顯然各節點通信覆蓋半徑相等，記為r。
　　(2)k跳節點：考察節點i和j。若j在i的通信覆蓋范圍內，可直接接收i的報文和向i發報，則稱j為i的一跳節點。顯然i和j互為一跳節點。若i至少通過1個節點轉發報文才能和j建立通信連接，稱i和j互為兩跳節點。依此類推，如果i和j至少通過(k-1)(k=2,3…）個節點轉發報文才能建立通信連接，稱i和j互為k跳節點。定義k跳節點之間相距跳數為k跳，記為H(i,j)=k,i≠j,并定義H(i,j)=0,i=j。
　　(3)一跳鄰節點集：對于節點i，其所有一跳節點的集合稱為一跳鄰節點集，記為Ｎ１(i)，依次類推可定義i的k跳鄰節點集Nk（i）（k=2,3,…）。
　　(4)網絡狀態模型：PRN網絡拓撲動態變化，但考察足夠短的任一時間段，該時間段內各節點位移微小，這時可認為網絡拓撲基本不變，呈現靜止狀態，稱為瞬時靜態。瞬時靜態時，網絡執行分群算法，節點進行分群管理和通信。瞬時靜態會持續一段時間，直到網絡拓撲變化量增大到一定程度，瞬時靜態被完全打破，原有網絡秩序徹底失效，網絡進入短暫的混沌狀態，然后迅速達到另一瞬時靜態，網絡重新分群，重建網絡秩序。網絡狀態在瞬時靜態和混沌狀態之間不斷交替，呈現一種動態平衡。本文基于以上網絡狀態模型，重點研究當PRN網絡處于瞬時靜態時的隱藏終端問題。一些未列出的定義和假設，將在敘述時給出。
　　2．基于自組織分群算法的網絡管理方法
　　PRN的路由和管理是一個非常復雜的問題。若采用全分布算法，網絡中每個節點都需維持一張全網拓撲的路由表來維護網絡。路由表的長度隨節點數線性增長，因此路由總開銷隨節點數呈平方增長。借鑒中心控制網絡的思想，若只在少量主要節點維持路由表，這樣既可充分發揮分布式網絡的優點，又可大大減少路由總開銷。但是單純減少PRN網絡中保存路由表的節點數并不能顯著減少開銷。由于PRN拓撲頻繁變化，路由信息的更新開銷占總開銷的主要部分，因此應采取措施降低更新頻率和每次的更新開銷。
　　一種有效的方法是將網絡分成多個小區，各小區自組織管理，即由小區內所有節點對小區進行管理。這種小區稱為分群(Cluster)或群，將網絡劃分為小區的算法稱為分群算法［３，８，９］。
　　當網絡處于瞬時靜態時，采用分群算法將網絡劃分為若干群，每個群自組織管理。只有當節點的位移導致大部分群嚴重失敗時才使整個網絡分群失敗，從而導致瞬時靜態失效。因此分群算法能有效適應節點的移動特性，群的生存能力強，抗毀性高，從而能夠有效降低網絡拓撲的更新頻率。同時，當網絡拓撲變化時，若少量維護路由表的節點只更新受影響的局部路由信息，在確保網絡運行穩定的前提下又可大幅減少每次更新的開銷。
　　自組織分群算法規定分群后各群內節點通過約定方法選擇一個"主控節點"，稱為群首。群首負責群的初始化管理和路由管理等任務，群內節點在群首的協調下對群進行自組織管理。當網絡拓撲變化時，群首只處理本群內節點進出群、鏈路失敗等少量操作，更新少量局部路由變化信息。當群首失效(重新分群、群首故障等)時，群內節點探測到后快速重選群首，可立即恢復網絡秩序。因此這種化整為零式的自組織網絡管理方式具有優良的抗毀性和穩健性，充分體現了自組織的優點，還可節約大量更新開銷。本文假設所研究的PRN網絡也采用自組織分群算法進行網絡管理。
　　分群算法有多種，按群內有無群首，可分為帶群首和無群首兩類；按分群后群之間有無重疊區域，可分為重疊和不重疊兩類。本文主要研究帶群首、重疊的分群算法，并假設群內所有節點都在以群首為中心，以為半徑的圓形區域內。
　　3．隱藏終端問題
　　隱藏終端問題如圖1所示。圖中Ｒ為接收終端，Ｓ１和Ｓ２為兩個發送終端，Ｓ１和Ｓ２相距兩跳。Ｒ同時處于Ｓ１和Ｓ２的通信覆蓋范圍內，當Ｓ１和Ｓ２同時向Ｒ發送報文時，造成Ｒ無法接收任何終端的報文，發生沖突，稱Ｓ１和Ｓ２相對Ｒ互為隱藏終端。
　　圖1中Ｈ區(陰影區)稱為Ｓ１相對Ｒ的隱藏終端區，區域內任何發送終端都是Ｓ?１相對Ｒ的隱藏終端。Ｓ１向Ｒ發送報文時Ｈ區內任一終端同時發送都將產生沖突，因此隱藏終端的存在嚴重影響無線網絡的通信性能。
　　　
　　
　　三、分群后隱藏終端問題分析
　　1．群內隱藏終端問題分析
　　群首是各節點的一跳節點，群內可能存在相距兩跳的節點，因此可能存在隱藏終端問題。?
　　2．群內隱藏終端問題分析
　　分群后群首在群的邊緣節點中選擇網關(網關選擇算法見后)，網關負責路由尋址和轉發進出群的報文。群之間的通信只能由網關中轉，因此不同群的節點不會直接沖突。
　　圖2中Ｓ１和Ｓ２分群前相對Ｒ互為隱藏終端，分群后Ｓ１和Ｒ屬于群Ｃ１，Ｓ２屬于群Ｃ２。Ｓ２只能通過網關節點g１與Ｒ間接通信，因此Ｓ１與Ｓ２相對Ｒ不再互為隱藏終端。但是Ｓ１和Ｓ２可能同時向g１發報，造成g１發生沖突，故Ｓ１和Ｓ２相對g１互為隱藏終端，隱藏終端問題轉而出現在網關節點g１上。
　　　
　　
　　四、隱藏終端問題解決方案
　　對于PRN網絡，TDMA體制允許不同區域的多個節點同時發送而保證有效接收，并能大大減小沖突概率，高效復用帶寬資源。為簡化分析，本文擬在TDMA體制下開展分析。但TDMA規定必須有主控節點分配時隙，當主控節點失效時整個網絡將陷入癱瘓，這顯然不適用于空中飛機組網。
　　自組織TDMA［10，11］是一種無主控節點的TDMA體制，所有節點都自行計算計劃預約的空閑時隙，然后廣播包含預約信息(預約的時隙、目標節點等)的時隙預約廣播報。如未發生沖突則該節點預約成功，否則重新預約。以后該節點就可在預約的時隙里發報，在其他時隙里則監聽信道并準備接收。因此自組織TDMA具有抗毀性高、生存能力強、支持分布式網絡等優點。為此，下文將針對自組織TDMA體制的PRN網絡開展研究。?
　　1．群內隱藏終端問題解決方案
　　在自組織TDMA體制下，群內兩跳節點如果在同一時隙發送報文則可能發生沖突。圖3中Ｓ１和Ｓ２相距兩跳，互為隱藏終端，為避免沖突必須禁止兩者預約同一時隙。由于兩者都無法直接知道對方時隙預約情況，因此需要中間節點(網格區中節點)仲裁。由于群首一定在網格區內，因此本文提出一種基于群首干預解決群內隱藏終端問題的方案。
　　本方案規定群首接收群中所有節點的預約廣播報，一旦發現如下預約沖突：２個一跳節點預約同一時隙；兩跳節點預約同一時隙，且至少有一個接收節點位于通信覆蓋的重疊區內(圖3中網格區)，則群首立即實施干預。群首(h)根據優先級或其他準則判決一個節點(Ｓ１)為優勝者，其他節點(Ｓ２)為失敗者，然后群首給失敗者發送一個預約失敗報(RFP，即Reservation Failure Packet)，失敗者根據RFP中提示信息重新預約。因此本方案有效地消除了群內的預約沖突，從而解決了群內可能存在的隱藏終端問題。
　　　
　　2?群間隱藏終端問題解決方案
　　由第三部分分析可知，群間隱藏終端問題只發生在網關節點上。由于網關的位置特殊性，以下展開詳細分析。
　　(1)網關選擇算法和兩種網關模型
　　為簡化分析，只對2個相鄰群進行分析(多相鄰群的情況類似分析)。根據兩群是否重疊存在以下２種網關模型：
　　1)兩個群有重疊區域，且重疊區域內有節點：
　?、僦丿B區域有一個節點：該節點當然選作２個群的網關，例如圖2中節點g１；
　?、谥丿B區域有多個節點：選擇具有最多一跳節點的節點作為網關，其他節點可作為備用網關；
　?。玻矀€群沒有重疊區域或重疊區內無節點，但是２個群內必定至少各有一個節點相距一跳(否則２個群無法直接通信)，則這２個節點組成網關節點對(GNP，即Gateway Node Pair)，如圖4中(g１,g２）組成一對GNP，記為G（g１，g２）。
　?、偃糁挥幸粚NP，當然選作網關；

原文轉自：http://www.kjueaiud.com