本站小編為你精心準(zhǔn)備了戰(zhàn)術(shù)網(wǎng)絡(luò)拓?fù)錁?gòu)建研究參考范文，愿這些范文能點燃您思維的火花，激發(fā)您的寫作靈感。歡迎深入閱讀并收藏。

戰(zhàn)術(shù)網(wǎng)絡(luò)在復(fù)雜、惡劣環(huán)境下要求網(wǎng)絡(luò)要具備動態(tài)拓?fù)渥兓蛣討B(tài)路由功能，以便支持移動用戶進(jìn)行多跳可靠的通信。在戰(zhàn)術(shù)通信場景中，常用的通信模式是廣播和多播消息，比如群組PTT(Push－To－Talk)、公告消息和態(tài)勢感知信息等。連通支配集(connecteddominatingset，CDS)是一種在戰(zhàn)術(shù)網(wǎng)絡(luò)中被利用來構(gòu)建虛擬骨干子網(wǎng)的有效方法。與簇結(jié)構(gòu)類似，支配集中的節(jié)點在路由分發(fā)和中繼轉(zhuǎn)發(fā)中起著重要作用，意味著路由信息的維護(hù)在連通支配集中就可以完成。連通支配集在實現(xiàn)MANET的虛擬骨干網(wǎng)絡(luò)方面有著很多優(yōu)勢［2］:在網(wǎng)絡(luò)拓?fù)?/a>變化情況下路由過程得到簡化、路由表的計算減少，同時分組中繼只用在連通支配集內(nèi)完成，而且可以避免在網(wǎng)絡(luò)廣播時可能產(chǎn)生的網(wǎng)絡(luò)風(fēng)暴。在戰(zhàn)術(shù)網(wǎng)絡(luò)環(huán)境中，很多CDS算法都已經(jīng)被提出并應(yīng)用于相關(guān)場景。利用冗余傳輸可以提高分組轉(zhuǎn)發(fā)效率，比如多次傳送分組或者在CDS中選擇更多的中繼節(jié)點來傳輸。前者是在很少的時間約束中獲得可靠點對點數(shù)據(jù)傳輸，而后者則是采用多徑策略以滿足實時廣播/多播業(yè)務(wù)的需求?？紤]到在戰(zhàn)術(shù)網(wǎng)絡(luò)中實時廣播/多播業(yè)務(wù)和節(jié)點移動導(dǎo)致拓?fù)渥兓那闆r，利用Yang提出的UCDS(UnifyingConnectedDominatingSet)算法在戰(zhàn)術(shù)網(wǎng)絡(luò)環(huán)境中來提高分組轉(zhuǎn)發(fā)效率，減少節(jié)點移動帶來的拓?fù)渥兓绊憽?/p>

1相關(guān)研究

在最近幾年，關(guān)于CDS的觀點、算法及實驗大量涌現(xiàn)。在CDS算法構(gòu)建拓?fù)渲?，CDS的大小、錯誤容忍度、能量節(jié)省和移動管理等方面都有很深入的研究。CDS算法的核心是尋找最小的連通支配集，這個已經(jīng)被證明是一個NP完全問題，即對于給定問題域的輸入規(guī)模，目前尚無足夠的手段證明該問題能夠被判定在多項式時間內(nèi)求解。CDS算法目前的應(yīng)用研究主要有:CDS能夠創(chuàng)建一個虛擬骨干網(wǎng)絡(luò)用來實現(xiàn)分組路由和控制。消息能夠通過CDS中的虛擬骨干路徑來選擇從源節(jié)點發(fā)送到目的節(jié)點的最近路由，這種方式可以簡稱為基于支配集的路由或者基于虛擬骨干的路由。通過CDS來優(yōu)化路由可以使得在路由信息更新時能夠大大的減少信息開銷。另外支配集在層級網(wǎng)絡(luò)中的應(yīng)用能夠減少控制信令的開銷。CDS能夠提高多播/廣播路由的效率。在多播/廣播路由中存在一個比較嚴(yán)重的問題就是很多中繼的節(jié)點不需要用來中繼轉(zhuǎn)發(fā)信息，即存在冗余節(jié)點。這樣會導(dǎo)致目的節(jié)點收到很多重復(fù)的信息，這是廣播風(fēng)暴產(chǎn)生的問題。如果消息能夠利用CDS來路由優(yōu)化，那么絕大多數(shù)冗余節(jié)點的廣播就可以消除。CDS能夠改進(jìn)功率控制，減少能量消耗。在無線網(wǎng)絡(luò)中每個節(jié)點電池能量都是有限的。利用CDS可以確保更多的節(jié)點進(jìn)入休眠模式，只保留中繼轉(zhuǎn)發(fā)消息的能力。另外CDS能夠平衡網(wǎng)絡(luò)管理的需求以便可以使得在節(jié)點中的能量能夠相對平衡的消耗。此外，由支配集形成的虛擬骨干能夠為多媒體業(yè)務(wù)在路由選擇的時候提供鏈路信道的質(zhì)量信息，或者可以當(dāng)作數(shù)據(jù)庫服務(wù)等［23］。

2算法描述

2．1概述UCDS是一個簡單而有效的分布、啟發(fā)式算法，通過其1跳的鄰節(jié)點信息(比如鄰居度數(shù)及節(jié)點ID)來確定CDS。在每個節(jié)點的鏈路層有一個分布式的狀態(tài)機(jī)，用來定義該節(jié)點在拓?fù)浣Y(jié)構(gòu)的收斂中的作用。在UCDS中，一個圖G的連通支配集(CDS)由一組連通節(jié)點組成。G圖中每個節(jié)點要么是CDS的成員，要么就是與某個成員相距1跳。UCDS定義了一組連接節(jié)點，其連接不相交集中的支配節(jié)點。通過UCDS構(gòu)建拓?fù)溥^程如圖1所示:UCDS使用連接集(ConnectingSet，CS)和支配集(DominatingSet，DS)的規(guī)則來分別構(gòu)建CS和DS，然后合并形成一個CDS。利用鄰居度數(shù)及節(jié)點ID來對節(jié)點等級進(jìn)行判定。具體有兩個步驟:支配集構(gòu)造和支配集連通。其中支配集連通中有三個規(guī)則:首先使用非CS規(guī)則，然后到CS規(guī)則，最后才用CS例外規(guī)則。

2．2符號說明i，j，k，l，m，n是指網(wǎng)絡(luò)中的節(jié)點標(biāo)識號;N是指網(wǎng)絡(luò)中所有的節(jié)點標(biāo)識號集合;DS是指節(jié)點i的鄰居節(jié)點標(biāo)識號集合;Nj是指節(jié)點j的鄰居節(jié)點標(biāo)識號集合;Nk是指節(jié)點k的鄰居節(jié)點標(biāo)識號集合;d是指節(jié)點的鄰居度數(shù)，即節(jié)點的鄰居節(jié)點個數(shù);DS是指支配集;CS是指連通集;CS'是指候選連通集;DSNj是指節(jié)點j的DS鄰居節(jié)點標(biāo)識號集合;DSNk是指節(jié)點k的DS鄰居節(jié)點標(biāo)識號集合。

2．3支配集構(gòu)造支配集構(gòu)造算法過程如下:算法1:構(gòu)造支配集(DS)//構(gòu)建DS規(guī)則過程

2．4支配集連通支配集連通的構(gòu)造算法過程如下:

3算法分析

UCDS算法分析主要包括兩方面:一是算法本身性能分析;另一個是與其他相關(guān)研究的對比分析。

3．1性能分析UCDS性能分析主要包括計算復(fù)雜度和消息復(fù)雜度，Δ表示鄰居度數(shù)。計算復(fù)雜度:在算法第一階段，節(jié)點與鄰居節(jié)點比較支配因子d及節(jié)點ID大小的計算復(fù)雜度為O(Δ)，主要是循環(huán)遍歷所有節(jié)點對比所需要的計算開銷;在算法第二階段中，非CS規(guī)則的計算復(fù)雜度為O(Δ2)，CS例外規(guī)則的計算復(fù)雜度為O(Δ3)，CS規(guī)則的計算復(fù)雜度為O(Δ3)，主要是循環(huán)遍歷節(jié)點i所有鄰居節(jié)點的非相交和遍歷循環(huán)候選CS成員對比支配因子d及節(jié)點ID大小所需要的計算開銷，即外循環(huán)遍歷、內(nèi)循環(huán)遍歷和非相交計算三個部分。算法的計算復(fù)雜度取決于最慢規(guī)則的計算復(fù)雜度，故UCDS算法的計算復(fù)雜度為O(Δ3)。消息復(fù)雜度:在整個算法過程中，每個節(jié)點均向鄰居節(jié)點發(fā)送鄰居列表消息，因此鄰居列表信息的共享是其主要的信息開銷，為O(Δ)。

3．2對比分析文獻(xiàn)［24］提出了一種改進(jìn)的Wu和Li規(guī)則［25］，其CDS的創(chuàng)建是通過采用擴(kuò)展規(guī)則來對比鄰居節(jié)點的鄰居度數(shù)和電池能量等級來完成這個過程，具體是采用標(biāo)記法來選擇每個可能的DS和CS成員，然后再剔除無用的成員，而在UCDS中，首先通過DS規(guī)則選擇準(zhǔn)確的DS成員，然后利用CS的兩個擴(kuò)展規(guī)則把不是和無用的CS成員排除掉，最后才利用CS規(guī)則來選擇準(zhǔn)確的CS成員，其計算復(fù)雜度最高是O(Δ3)，低于文獻(xiàn)［24］算法的計算復(fù)雜度。文獻(xiàn)［26］也是一種改進(jìn)的Wu和Li規(guī)則，其主要是提高在移動環(huán)境下利用開啟和關(guān)閉節(jié)點來減少能量消耗的效率，在這個過程中，要利用不同的規(guī)則來處理開啟和關(guān)閉之間的切換、移動管理、更新虛擬骨干，最后更新CDS。而在UCDS中，處理與該文獻(xiàn)相同的情況時不再需要定制任何其他規(guī)則就能夠?qū)崿F(xiàn)，其實現(xiàn)比較簡單。文獻(xiàn)［27］描述了一種與UCDS的過程比較類似的算法，其標(biāo)記階段與DS規(guī)則類似，連接階段與CS類似，但是其標(biāo)記階段的結(jié)果還沒真正起作用。在該文獻(xiàn)中，在標(biāo)記階段所構(gòu)建的DS，其互相之間還不能連接，而UCDS在這個階段即使用DS規(guī)則后所構(gòu)建的DS已經(jīng)能夠用于尋找最短路由的應(yīng)用了。在連接階段，該文獻(xiàn)增加了無用節(jié)點{5、9、14}，這些無用節(jié)點還要增加刪減階段才能去掉;與此相反的是，UCDS在該階段用CS例外規(guī)則就可以排除所有的節(jié)點從而獲得了最終CDS解{2、4、7、10、11、12}。文獻(xiàn)［28］描述了一種使用混合因子(鄰居度數(shù)和局域協(xié)作)的思想來構(gòu)建CDS，其后擴(kuò)展為鄰居度數(shù)、局域協(xié)作和節(jié)點能量等級。該文獻(xiàn)與前面改進(jìn)的Wu和Li規(guī)則不一樣的是，混合因子是在排除階段使用，而改進(jìn)的Wu和Li則在初始標(biāo)記階段就使用。這樣會使得在初始階段就失去使用混合因子來判斷的機(jī)會，僅僅只是根據(jù)網(wǎng)絡(luò)拓?fù)涠鴽]有考慮其他因子的影響。文獻(xiàn)［29］在構(gòu)建基于MPR(mul-tipointrelaying，多點中繼)的CDS時，也只是僅僅使用剩余能量等級因子來決定覆蓋的節(jié)點數(shù)量，而忽略了其他重要因子對CDS節(jié)點選擇的影響。UCDS采取了靈活的可配置支配因子，在初始的DS規(guī)則階段該方法對于前面的算法來說更為有效，其計算復(fù)雜度是，實際情況下，有可能在初始的DS規(guī)則階段就能夠選定了所有或者絕大部分的CDS成員，僅僅在DS規(guī)則不能滿足全連通的要求時才使用計算復(fù)雜度更高的CS規(guī)則。因此UCDS不僅在求出CDS解的方面比文中所提到的算法更高效，而且在創(chuàng)建CDS時調(diào)整最佳的支配因子方面也比其他算法更靈活。文獻(xiàn)［30］和［31］提出一種計算復(fù)雜度和時間復(fù)雜度比較低的算法，其中計算復(fù)雜度為O(N)，時間復(fù)雜度為O(N2)，但是這兩種算法的計算效率是在花費更多的消息復(fù)雜度情況下獲得，該算法需要的消息有局域鄰居節(jié)點發(fā)現(xiàn)信息和其他拓?fù)渥兓瘯r所產(chǎn)生一系列泛洪信息。文獻(xiàn)［32］也是采用類似的算法，但在移動應(yīng)用受到帶寬限制，而且算法缺乏健壯性，很難得到推廣。在文獻(xiàn)［33］中所提出的算法過程與UCDS基本上一樣，但是其是集中式，因此也很難在移動戰(zhàn)術(shù)網(wǎng)絡(luò)中得到應(yīng)用。文獻(xiàn)［34］對網(wǎng)絡(luò)中存在兩個支配集進(jìn)行仿真，結(jié)果表明，相對于一個支配集來說，存在兩個支配集所用到的CDS成員數(shù)量并沒有增加很多。但是該算法的消息復(fù)雜度為，比UCDS的消息復(fù)雜度高。在戰(zhàn)術(shù)網(wǎng)絡(luò)中，由于有限的帶寬，消息復(fù)雜度是一個非常重要的因素，消息復(fù)雜度越高，其收斂速度越慢。

4拓?fù)錁?gòu)建實例

基于UCDS算法實現(xiàn)拓?fù)錁?gòu)建過程實例分析如圖3所示:通過圖3的實例圖展開如下分析:1．利用DS規(guī)則選擇出DS。首先根據(jù)DS規(guī)則第一個條件:根據(jù)表1自選最大鄰居度數(shù)，圖中節(jié)點10確定是DS成員，然后根據(jù)DS規(guī)則第二個條件:根據(jù)表1推選最大鄰居度數(shù)，圖中節(jié)點6、7、8、9、11、13、16確定是DS成員，因此，最終的DS成員是6、7、8、9、10、11、13、16，如圖3中黑色節(jié)點表示。2．利用非CS規(guī)則排除非CS成員節(jié)點。根據(jù)非CS規(guī)則，從剩余的節(jié)點中選擇出非CS成員:5，在圖3中用白色節(jié)點表示。3．利用CS規(guī)則選擇出CS。根據(jù)CS規(guī)則從剩余的節(jié)點中選擇成員:4和12，因為節(jié)點1、2、3、14、15都具有相交的DSN，比如節(jié)點1，其DSN(備注:節(jié)點中只存儲2跳以內(nèi)的節(jié)點信息)有兩個{2、3、7}和{7、8、9}，存在相交的節(jié)點7，故排除節(jié)點1，同理2、3、14、15都是一樣。故CS節(jié)點為{4、12}。4．利用CS例外規(guī)則去掉冗余的CS節(jié)點。根據(jù)CS例外規(guī)則，從上面分析后CS節(jié)點中去掉冗余CS成員:4，在圖3中用白色節(jié)點表示。最后所得的CS成員為{12}。從上面4個規(guī)則執(zhí)行后所得的DS和CS的并集就是UCDS，即{6、7、8、9、10、11、12、13、16}。

5應(yīng)用分析

5．1路由優(yōu)化在戰(zhàn)術(shù)網(wǎng)絡(luò)中，反應(yīng)式路由比如AODV等用來發(fā)現(xiàn)源節(jié)點與目的節(jié)點之間的路由路徑。通常路由發(fā)現(xiàn)過程都是廣播一個路由請求分組(routere-quest，RREQ)給鄰居節(jié)點，接收到該信息的節(jié)點繼續(xù)轉(zhuǎn)發(fā)RREQ分組，這個過程持續(xù)到RREQ分組到達(dá)目的節(jié)點為止，然后目的節(jié)點把路由中繼消息(routereply，RREP)發(fā)送至源節(jié)點［35］－［36］。這種路由發(fā)現(xiàn)過程容易產(chǎn)生廣播風(fēng)暴。在路由發(fā)現(xiàn)過程中，可以結(jié)合UCDS算法來對路由路徑進(jìn)行優(yōu)化，簡化了路由過程，從而避免廣播風(fēng)暴的問題產(chǎn)生。對于戰(zhàn)術(shù)網(wǎng)絡(luò)中任意一對節(jié)點，其最短路徑之間的中繼節(jié)點都應(yīng)包含在UCDS中。這樣將分組轉(zhuǎn)發(fā)任務(wù)限定于連通支配集內(nèi)部，當(dāng)CDS節(jié)點接收到一個RREQ分組時廣播該數(shù)據(jù)包，非CDS節(jié)點則只用接收該分組而不用轉(zhuǎn)發(fā)該分組。這樣RREQ分組傳輸?shù)臄?shù)次會大大的減少，提高分組轉(zhuǎn)發(fā)效率，從而避免了網(wǎng)絡(luò)的擁塞。另外，在轉(zhuǎn)發(fā)路由路徑選擇時，其所耗費的時間更加少。具體的路由優(yōu)化實例如圖4從圖4可看出，利用UCDS算法時最多需要8次分組轉(zhuǎn)發(fā)傳送，而普通廣播則至少需要13次才能夠完成全網(wǎng)廣播過程。

5．2節(jié)點移動自適應(yīng)戰(zhàn)術(shù)網(wǎng)絡(luò)的拓?fù)湟驗楣?jié)點的持續(xù)移動而不斷變化。在戰(zhàn)術(shù)網(wǎng)絡(luò)中，UCDS算法支持低速率下節(jié)點移動自適應(yīng)，具體從下面三個不同的移動實例，以圖3作為圖例進(jìn)行說明。(1)非CDS節(jié)點離開網(wǎng)絡(luò)如果一個非CDS節(jié)點離開網(wǎng)絡(luò)，UCDS算法將會檢查是否因為網(wǎng)絡(luò)拓?fù)涞母淖兌鴮?dǎo)致CDS節(jié)點成員改變。在圖3中，除了節(jié)點3、4、5、14、15離開網(wǎng)絡(luò)不會導(dǎo)致CDS成員發(fā)生改變之外，其他非CDS節(jié)點離開都會使得CDS成員發(fā)生改變，原因是由于節(jié)點4和5共同推舉了DS節(jié)點11，故節(jié)點4和5離開網(wǎng)絡(luò)均不會造成CDS成員改變;而節(jié)點3、14和15的離開導(dǎo)致了節(jié)點6、13和16變成了CS節(jié)點，故節(jié)點3、14和15離開網(wǎng)絡(luò)不會造成CDS成員改變。根據(jù)UCDS算法中DS規(guī)則可知，非CDS節(jié)點1、2的離開都會造成CDS成員改變，具體原因是非CDS節(jié)點推薦其鄰居節(jié)點作為DS節(jié)點，如果該節(jié)點離開網(wǎng)絡(luò)，那么所推薦的DS節(jié)點將會失效，具體如表2所。(2)CDS節(jié)點離開網(wǎng)絡(luò)如果一個CDS節(jié)點離開網(wǎng)絡(luò)，UCDS算法將會檢查是否因為網(wǎng)絡(luò)拓?fù)涞母淖兌鴮?dǎo)致CDS節(jié)點成員改變。如圖3所示，節(jié)點10離開不會增加新的CDS成員，其他節(jié)點的離開都會增加新的CDS成員，而節(jié)點7的離開導(dǎo)致CDS成員增加比較多，節(jié)點8與9和12與13的離開后其CDS成員一樣。具體情況如表3。(3)新節(jié)點加入網(wǎng)絡(luò)新節(jié)點加入網(wǎng)絡(luò)，獲取鄰居列表信息后，UCDS算法開始對新加入的節(jié)點進(jìn)行分析。利用DS規(guī)則，新節(jié)點推舉其鄰居節(jié)點中鄰居度數(shù)最大或者ID最大的節(jié)點(鄰居度數(shù)相同情況下)作為新的DS節(jié)點加入到CDS，同時分析其它的DS節(jié)點，是否滿足DS規(guī)則和CS規(guī)則，不滿足的話則從CDS中剔除并加入到普通子集。具體如圖5所示，節(jié)點17加入網(wǎng)絡(luò)后，CDS變化為{2、6、7、8、9、10、11、12、13、16}。

6結(jié)語

在戰(zhàn)術(shù)網(wǎng)絡(luò)中，節(jié)點移動導(dǎo)致了網(wǎng)絡(luò)拓?fù)涞淖兓?。以UCDS算法為基礎(chǔ)，探討了連通支配集在戰(zhàn)術(shù)網(wǎng)絡(luò)中的分布式構(gòu)建虛擬骨干過程。通過與相關(guān)構(gòu)建虛擬骨干算法進(jìn)行對比分析，UCDS在計算度復(fù)雜度和消息復(fù)雜度上都有一定的優(yōu)勢，特別是消息復(fù)雜度，其所構(gòu)建的虛擬骨干拓?fù)淠軌蛟趹?zhàn)術(shù)網(wǎng)絡(luò)環(huán)境中支持路由優(yōu)化及低速率下節(jié)點移動自適應(yīng)。下一步工作是在OSPF協(xié)議中使用UCDS節(jié)點作為中繼節(jié)點，分析其執(zhí)行效率，并能夠使用在真實的戰(zhàn)術(shù)網(wǎng)絡(luò)環(huán)境中。

作者：唐龍 王峰 單位：武漢中原電子集團(tuán)有限公司 總裝備部