劉玉濤,張春暉
(通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點實驗室,河北 石家莊 050081)
移動自組織網(wǎng),一般稱為MANET(Mobile Ad hoc Network)[1]。由文獻(xiàn)[2-4]的論述可知,MANET是由一組帶有無線收發(fā)信裝置的移動節(jié)點組成的一個無線移動通信網(wǎng)絡(luò),它不依賴于預(yù)設(shè)的基礎(chǔ)設(shè)施而臨時組建,網(wǎng)絡(luò)中移動的節(jié)點利用自身的無線收發(fā)設(shè)備交換信息,當(dāng)相互之間不在彼此的通信范圍內(nèi)時,可以借助其他中間節(jié)點中繼來實現(xiàn)多跳通信。MANET網(wǎng)絡(luò)與傳統(tǒng)的無線通信網(wǎng)絡(luò)相比,具有以下特點:① 網(wǎng)絡(luò)的自組織與自恢復(fù)特性;② 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)變化[5];③ 靈活多跳的通信方式;④ 網(wǎng)絡(luò)的分布式管理與控制;⑤ 短暫的網(wǎng)絡(luò)生存時間[6]。MANET網(wǎng)絡(luò)由于上述特點,特別適合應(yīng)用在戰(zhàn)術(shù)分隊分組通信、反恐處突、搶險救災(zāi)和大型集會等臨時性或突發(fā)性等場合中[7-8]。
在基于簇結(jié)構(gòu)的MANET網(wǎng)絡(luò)中,分簇組網(wǎng)協(xié)議及簇間通信是大規(guī)??煽拷M網(wǎng)的前提,是一個重要的研究方向。簡單高效的分簇算法可以減少MANET網(wǎng)絡(luò)的路由和計算開銷,提高簇間通信效率?,F(xiàn)有分簇組網(wǎng)方案的設(shè)計一般是基于圖論中連通支配集相關(guān)理論進(jìn)行簇頭和跨簇節(jié)點的選擇,文獻(xiàn)[9-13]介紹了常用的典型算法包括最大連通度算法、最小ID算法等。本文采用了一種有利于提高跨測通信效率的最大連接度算法,可以有效地保障網(wǎng)絡(luò)跨簇通信的穩(wěn)定。在分簇組網(wǎng)進(jìn)行跨簇處理時,本文設(shè)計了一種多信道跨簇處理方式,與單信道跨簇相比,該方式便于實現(xiàn)網(wǎng)絡(luò)的分層管理與控制,可以實現(xiàn)上層節(jié)點同時接入多個下層網(wǎng)絡(luò)。
MANET網(wǎng)絡(luò)中的移動節(jié)點除了需要完成傳統(tǒng)無線網(wǎng)絡(luò)中的業(yè)務(wù)收發(fā)功能外,還具備信息轉(zhuǎn)發(fā)功能[14]。MANET網(wǎng)絡(luò)中節(jié)點間是完全對等的,網(wǎng)絡(luò)的正常工作并不依賴于任何特殊節(jié)點,當(dāng)一個或多個節(jié)點離開或加入網(wǎng)絡(luò)時可以實現(xiàn)網(wǎng)絡(luò)的動態(tài)調(diào)整,如圖1所示[15]。
圖1 MANET網(wǎng)絡(luò)示意
根據(jù)MANET網(wǎng)絡(luò)的組成特點,可以分為平面化與層級化2種網(wǎng)絡(luò)結(jié)構(gòu)[16]。基于平面化結(jié)構(gòu)的MANET網(wǎng)絡(luò)建立、網(wǎng)絡(luò)管理和結(jié)構(gòu)維護(hù)等簡單且易于實現(xiàn);但當(dāng)網(wǎng)絡(luò)規(guī)模變大時,受制于節(jié)點對等性限制,網(wǎng)絡(luò)計算、管理和維護(hù)開銷將指數(shù)級增長,考慮到節(jié)點的移動性引起的控制信息的傳輸需求,會顯著降低網(wǎng)絡(luò)的有效帶寬[17]。
為解決MANET平面化結(jié)構(gòu)引起的網(wǎng)絡(luò)規(guī)模限制問題,參考計算機網(wǎng)絡(luò)中子網(wǎng)劃分的思想,研究人員提出了MANET網(wǎng)絡(luò)的層級化結(jié)構(gòu)[18]。在這種架構(gòu)下,可以將MANET網(wǎng)絡(luò)劃分成多個規(guī)??煽氐淖泳W(wǎng),子網(wǎng)之間是松耦合關(guān)系,能夠?qū)崿F(xiàn)相對獨立的管理與控制,在降低網(wǎng)絡(luò)管理與維護(hù)開銷的同時有效解決了平面化網(wǎng)絡(luò)擴展性差的問題,極大地擴展了MANET網(wǎng)絡(luò)的應(yīng)用場景。文獻(xiàn)[19-22]的研究表明,在MANET網(wǎng)絡(luò)分層技術(shù)中,分簇作為一種簡便易行的層級化組網(wǎng)方法,可以有效地提高網(wǎng)絡(luò)的性能和效率。
在基于簇的MANET網(wǎng)絡(luò)層級化結(jié)構(gòu)中,地理上相近的多個節(jié)點按照一定的邏輯規(guī)則構(gòu)成不同的簇,并通過網(wǎng)關(guān)節(jié)點(亦稱跨簇節(jié)點)連接不同的簇,進(jìn)而實現(xiàn)全網(wǎng)的連通。一般而言,每一個簇形成一個子網(wǎng),通常由簇頭、普通節(jié)點與網(wǎng)關(guān)節(jié)點組成,其中簇頭亦可以用作網(wǎng)關(guān)節(jié)點,具體與分簇算法有關(guān)。
簇頭是每個簇的管理者,一般用作網(wǎng)絡(luò)的管理與調(diào)度。簇頭可以通過分布式算法由預(yù)先設(shè)定的標(biāo)準(zhǔn)產(chǎn)生,也可以根據(jù)預(yù)設(shè)的優(yōu)先級自動產(chǎn)生,自動產(chǎn)生時面臨網(wǎng)絡(luò)融合問題。簇內(nèi)的普通節(jié)點可能同時處于多個簇頭的覆蓋范圍內(nèi),但某一時刻最多只能屬于一個簇,與一個簇頭建立從屬關(guān)系。網(wǎng)關(guān)節(jié)點在不同時刻可以隸屬于不同的簇,這樣一來,即可以實現(xiàn)相鄰簇之間的通信,進(jìn)而達(dá)到擴展網(wǎng)絡(luò)規(guī)模的目的。
MANET簇內(nèi)組網(wǎng)協(xié)議主要解決2個方面的問題:① 如何實現(xiàn)節(jié)點間同步、網(wǎng)絡(luò)建立、節(jié)點入網(wǎng)和退網(wǎng);② 如何實現(xiàn)網(wǎng)絡(luò)資源的管理和控制[21]?;诟偁幍慕M網(wǎng)協(xié)議隨著網(wǎng)絡(luò)規(guī)模的增加碰撞概率會急劇增高,因此,在規(guī)模較大的網(wǎng)絡(luò)中一般采用基于分配的組網(wǎng)協(xié)議[23]。
分布式TDMA協(xié)議是一種常用的基于分配的組網(wǎng)協(xié)議,將時間劃分成互不重疊的幀,然后將幀劃分為互不重疊的時隙,將不同時隙與不同的節(jié)點ID相對應(yīng)。每個節(jié)點在每個幀周期內(nèi)均會占有一個TDMA信令時隙,且每個信令時隙均在數(shù)據(jù)間隔內(nèi)對應(yīng)一個可用的數(shù)據(jù)發(fā)送時隙。節(jié)點將通過時隙中的信令部分去競爭自己的發(fā)送時隙,通過信令時隙申請完成數(shù)據(jù)的發(fā)送。當(dāng)新節(jié)點入網(wǎng)時,其會在本節(jié)點選擇的時隙發(fā)送信令,并在其他時隙進(jìn)行監(jiān)聽,等待其他節(jié)點對自己的確認(rèn)ACK信息。
Beacon協(xié)議是一種基于分配的組網(wǎng)協(xié)議,采用信標(biāo)(Beacon)幀的信道訪問機制,主節(jié)點周期性地發(fā)送信標(biāo)幀,網(wǎng)絡(luò)中的其他節(jié)點必須遵循主節(jié)點分配的時隙進(jìn)行信道訪問。網(wǎng)絡(luò)中包含3種信標(biāo):主信標(biāo)、代理信標(biāo)和發(fā)現(xiàn)信標(biāo)。主信標(biāo)由主節(jié)點生成,主信標(biāo)中包含當(dāng)前網(wǎng)絡(luò)的基準(zhǔn)時間和時隙分配結(jié)果,時隙分配結(jié)果決定了網(wǎng)絡(luò)中節(jié)點訪問信道的方式和時隙;代理信標(biāo)由代理站點發(fā)送,代理信標(biāo)中包含主信標(biāo)的全部時隙分配結(jié)構(gòu),且攜帶代理節(jié)點的基本屬性;發(fā)現(xiàn)信標(biāo)用于發(fā)現(xiàn)周圍可能的隱藏節(jié)點,發(fā)現(xiàn)信標(biāo)中包含用于隱藏節(jié)點加入網(wǎng)絡(luò)的競爭時隙安排,當(dāng)未入網(wǎng)節(jié)點接收到發(fā)現(xiàn)信標(biāo)后,可以根據(jù)發(fā)現(xiàn)信標(biāo)中的時隙安排發(fā)起加入網(wǎng)絡(luò)的請求。
建立危險、劇毒、有害、放射性、可傳染性物品的全程監(jiān)控體系,不斷列出和修訂上述物品清單,通過統(tǒng)一或申報購置,財務(wù)報銷警示,使用者提供購置、使用、銷毀方案等方式對其實行自購置到銷毀的一條龍?zhí)幹梅桨?,?jīng)校院兩級審批,嚴(yán)格把好使用和監(jiān)控關(guān)。
分簇和簇間通信需求使得網(wǎng)絡(luò)中的資源管理或通信過多地集中到簇頭和網(wǎng)關(guān)節(jié)點,不利于事項負(fù)載均衡,也不利于平衡節(jié)點間的能耗。因此,分簇組網(wǎng)與分簇算法需要重點解決如何減少分簇及跨簇通信中控制信息的開銷、如何實現(xiàn)網(wǎng)絡(luò)拓?fù)渥兓瘯r簇內(nèi)與簇間通信的延續(xù)性以及如何實現(xiàn)網(wǎng)絡(luò)負(fù)載的有效均衡等問題。常用的分簇算法有隨機算法、最大連接度優(yōu)先算法、最小標(biāo)識符優(yōu)先算法以及鏈路穩(wěn)定性優(yōu)先算法等。
2.2.1 隨機算法
隨機算法依據(jù)發(fā)現(xiàn)其他簇中節(jié)點的先后順序選擇網(wǎng)關(guān)節(jié)點,最先接收到其他簇中節(jié)點的信息且經(jīng)過簇頭確定后即可以成為該簇的網(wǎng)關(guān)節(jié)點。網(wǎng)關(guān)節(jié)點失效后,剩余節(jié)點仍舊按照該原則選擇新的網(wǎng)關(guān)節(jié)點。隨機算法復(fù)雜度低,但不利于降低簇間通信時延,傳輸效率不高。
2.2.2 最大連接度優(yōu)先算法
最大連接度優(yōu)先算法根據(jù)節(jié)點通過一跳連接的其他簇中節(jié)點的個數(shù)選擇網(wǎng)關(guān)節(jié)點,顧名思義,跨簇一跳鄰居數(shù)最多的節(jié)點將被定義為網(wǎng)關(guān)節(jié)點。當(dāng)多個節(jié)點的跨簇一跳鄰居數(shù)相同時,選擇簇內(nèi)鄰居數(shù)較少的節(jié)點作為網(wǎng)關(guān)節(jié)點;當(dāng)簇內(nèi)鄰居數(shù)亦相同時,選擇ID最小的節(jié)點作為網(wǎng)關(guān)節(jié)點。最大連接度優(yōu)先算法簇間通信時延較短,但由于連接度隨著節(jié)點的移動而變化,會導(dǎo)致網(wǎng)關(guān)節(jié)點的頻繁切換。
2.2.3 最小ID優(yōu)先算法
最小ID優(yōu)先算法根據(jù)能夠連接到其他簇的節(jié)點的ID選擇網(wǎng)關(guān)節(jié)點,ID最小的被確定為該簇的網(wǎng)關(guān)節(jié)點。最小ID優(yōu)先算法收斂較快,但新節(jié)點尤其是ID較小節(jié)點的加入會導(dǎo)致網(wǎng)關(guān)的切換,同時,亦不利于降低簇間通信時延和提高簇間傳輸效率。
2.2.4 鏈路穩(wěn)定性優(yōu)先算法
(1)
式中,Pr與Pt分別表示接收功率和發(fā)射功率;Gr與Gt為收、發(fā)兩端的天線增益;d表示收發(fā)節(jié)點間的距離;L為系統(tǒng)損耗率。發(fā)端的平均信號強度大的節(jié)點被定義為網(wǎng)關(guān)節(jié)點。鏈路穩(wěn)定性優(yōu)先算法在節(jié)點移動的情況下仍舊能最大限度地保障簇間通信的時延,但同樣難以避免節(jié)點移動引起的網(wǎng)關(guān)節(jié)點頻繁切換。
分簇組網(wǎng)中簇間通信通過網(wǎng)關(guān)節(jié)點連接,可以采用單信道方式或雙信道方式實現(xiàn),區(qū)別在于簇間連接方式不同。單信道方式網(wǎng)關(guān)節(jié)點采用單模塊,業(yè)務(wù)跨簇時類似“半雙工”,跨簇節(jié)點分時工作在2個子網(wǎng)的頻率上;雙信道方式網(wǎng)關(guān)節(jié)點采用雙模塊(可稱之為“雙卡雙待”),業(yè)務(wù)跨簇時類似“全雙工”,網(wǎng)關(guān)節(jié)點同時工作在2個子網(wǎng)的頻率上。
通過單信道方式連接多個簇時網(wǎng)關(guān)節(jié)點配置單模塊即可,但只能通過時分方式分別接入不同的網(wǎng)絡(luò),網(wǎng)絡(luò)之間是“橫連”關(guān)系,不存在分層、分級概念,如圖2所示。
圖2 單信道方式跨簇通信結(jié)構(gòu)示意
通過雙信道方式連接多個簇時需要網(wǎng)關(guān)節(jié)點配置雙模塊,可以同時接入上、下兩層子網(wǎng),實現(xiàn)網(wǎng)絡(luò)的分層管理與控制,如圖3所示。
圖3 雙信道方式跨簇通信結(jié)構(gòu)示意
單信道方式網(wǎng)關(guān)節(jié)點與普通節(jié)點采用同樣的配置,尺寸和功耗等便于控制。雙信道方式便于實現(xiàn)網(wǎng)絡(luò)分層,組成與實際層級關(guān)系一致的網(wǎng)絡(luò),按照分層關(guān)系組網(wǎng)使用效率更高,如圖4所示。雙信道方式便于簇間串聯(lián),易于擴展網(wǎng)絡(luò)規(guī)模和節(jié)點數(shù),且簇間相對獨立、互不影響,網(wǎng)絡(luò)整體更穩(wěn)定。
圖4 雙信道方式網(wǎng)絡(luò)分層管理示意
下面簡要介紹雙信道跨簇時簇間通信數(shù)據(jù)傳輸?shù)膶崿F(xiàn)途徑,考慮準(zhǔn)靜態(tài)應(yīng)用場景網(wǎng)關(guān)節(jié)點選擇主要依據(jù)最大連接度優(yōu)先算法。
網(wǎng)絡(luò)應(yīng)用視圖如圖5所示,3個不同的簇通過網(wǎng)關(guān)節(jié)點相連后形成一個分簇多級網(wǎng)。節(jié)點連接的業(yè)務(wù)終端(筆記本電腦等)需要將節(jié)點IP設(shè)置成默認(rèn)網(wǎng)關(guān),業(yè)務(wù)終端的IP地址需要和默認(rèn)網(wǎng)關(guān)保持相同的網(wǎng)段。由圖5可知,節(jié)點2和節(jié)點4為簇間通信的網(wǎng)關(guān)節(jié)點,當(dāng)PC1發(fā)送數(shù)據(jù)包到PC2時,PC1默認(rèn)網(wǎng)關(guān)設(shè)置為192.168.1.11,PC2默認(rèn)網(wǎng)關(guān)設(shè)置為192.168.2.10,具體流程如下:
① PC1發(fā)現(xiàn)PC2的IP地址不在同一個簇內(nèi),則將數(shù)據(jù)發(fā)送至默認(rèn)網(wǎng)關(guān),即節(jié)點1。鏈路A中數(shù)據(jù)包的目的MAC為節(jié)點1的MAC,目的IP為PC2的IP。
② 節(jié)點1網(wǎng)絡(luò)層收到數(shù)據(jù)包,判斷IP地址為簇外,查找轉(zhuǎn)發(fā)表,找到下一跳IP為192.168.1.14,進(jìn)而查找IP-MAC表,替換源MAC和目的MAC,將數(shù)據(jù)發(fā)送至該節(jié)點,鏈路B中數(shù)據(jù)包的目的MAC為節(jié)點4的MAC。
③ 節(jié)點4收到數(shù)據(jù),判斷其類型為簇間通信數(shù)據(jù)包,根據(jù)網(wǎng)絡(luò)號192.168.2.0,將其轉(zhuǎn)發(fā)至192.168.2.14。
④ 節(jié)點4中IP地址為192.168.2.14的模塊判斷IP地址為簇內(nèi)數(shù)據(jù)包,填寫目的MAC為PC2的MAC,源MAC為本地MAC,并將數(shù)據(jù)包發(fā)送至MAC層。然后將數(shù)據(jù)按照簇內(nèi)路由發(fā)送至節(jié)點5。
⑤ 節(jié)點5的MAC層直接將數(shù)據(jù)發(fā)送至以太網(wǎng)口。
圖5 雙信道方式簇間通信實現(xiàn)流程
MANET網(wǎng)絡(luò)通過分簇和簇間通信可以實現(xiàn)大規(guī)模組網(wǎng)。網(wǎng)關(guān)節(jié)點是實現(xiàn)簇間通信的關(guān)鍵節(jié)點,網(wǎng)關(guān)節(jié)點的選擇影響跨簇通信時延、傳輸效率及簇間通信的穩(wěn)定性與可靠性。不同的跨簇方式適應(yīng)不同的應(yīng)用場景,在準(zhǔn)靜態(tài)效率優(yōu)先場景下,采用了最大連接度優(yōu)先算法選擇網(wǎng)關(guān)節(jié)點與雙信道跨簇方式。最后,本文以3個自組織網(wǎng)簇為例對分簇組網(wǎng)簇間通信流程進(jìn)行了詳細(xì)的分析與介紹。分析可知,本文提出的分簇組網(wǎng)簇間通信采用了最大連接度優(yōu)先算法和雙信道跨簇方法,在充分考慮簇間通信時延的前提下便于工程實現(xiàn),具有較高的應(yīng)用價值。
[1] SHARMAA K,TRIVEDI M C.Performance Comparison of AODV,ZRP and AODVDR Routing Protocols in MANET[C]∥2016 Second International Conference on Computational Intelligence & Communication Technology (CICT),2016:231-236.
[2] 霍金海,王鉞,徐贊新,等.基于負(fù)載和優(yōu)先級的MANET優(yōu)化策略[J].清華大學(xué)學(xué)報(自然科學(xué)版),2012,52(9):1270-1274.
[3] ISTIKMAL,KURNIAWAN A,HENDRAWAN.Throughput Performance of Routing Protocols Based on SNR in Wireless Mobile Ad Hoc Networks[C]∥2015 1st International Conference on Wireless and Telematics (ICWT),2015:1-6.
[4] KUMARJ.802.11 DCF in Dynamic MANET On-demand Routing[J].International Journal of Informatics and Communication Technology (IJ-ICT),2013,2(2):85-92.
[5] KIM,DAEHYEOK,SUH,et al.Multi-Rate Combination of Opportunistic Routing and Network Coding:An Optimization Perspective[C]∥IEEE Wireless Communications and Networking Conference:Mobile and Wireless Networks,2012:1947-1952.
[6] 李勇,匡坤高,王平,等.分布式自組織網(wǎng)絡(luò)動態(tài)功率控制機制的研究與實現(xiàn)[J].東南大學(xué)學(xué)報(自然科學(xué)版),2011,41(2):296-300.
[7] 盧山,宋志群,賈倩.基于車隊行進(jìn)場景的MANET移動模型研究[J].無線電通信技術(shù),2016,42(1):9-11.
[8] 陳藝蝦,孫權(quán)森,徐煥宇,等.SURF算法和RANSAC算法相結(jié)合的遙感圖像匹配方法[J].計算機科學(xué)與探索,2012,6(9):822-828.
[9] 代家銘,宋玉龍,尚亞黎,等.高動態(tài)環(huán)境下航空自組網(wǎng)分簇算法設(shè)計[J].計算機應(yīng)用研究,2015,32(4):1193-1198.
[10] WANG S H,LIU C C,WANG C Y.Link Stability-based Based Routing and Clustering in Ad Hoc Wireless Networks Using Fuzzy Set Theory[J].International Journal of Wireless Information Networks,2002,9(3):201-212.
[11] 徐丹丹,章勇.一種基于最大連通度的雙簇頭分簇算法[J].傳感技術(shù)學(xué)報,2008,21(11):1909-1912.
[12] 杜勝永,柴喬林,王華.基于節(jié)點聚合度的生成簇算法[J].計算機應(yīng)用,2006,26(4):948-950.
[13] 沙毅,黃燁,黃麗,等.基于小波神經(jīng)網(wǎng)絡(luò)預(yù)測的Ad Hoc網(wǎng)絡(luò)分簇算法[J].東北大學(xué)學(xué)報(自然科學(xué)版),2011,32(9):1233-1236.
[14] 李秀朋,李少輝.一種Ad Hoc自組織網(wǎng)絡(luò)系統(tǒng)的設(shè)計與實現(xiàn)[J].無線電工程,2014,44(8):8-10.
[15] 齊法制,張紅梅,張瀚文,等.MANET網(wǎng)絡(luò)中基于隊列長度的逐跳AC自適應(yīng)調(diào)整機制[J].計算機科學(xué),2016,43(3):84-88.
[16] 劉春旭,劉元安,高錦春,等.大規(guī)模MANET中基于分層架構(gòu)的分簇式發(fā)布-訂閱路由協(xié)議[J].吉林大學(xué)學(xué)報(工學(xué)版),2013,43(2):451-458.
[17] YONEKIE, BACONJ.An Adaptive Approach to Content-based Subscription in Mobile Ad Hoc Networks[C]∥Proceedings of the Second IEEE Annual Conference on Pervasive Computing and Communications Workshops,2004:92-97.
[18] BAKERD,EPHREMIDES A.The Architectural Organization of a Mobile Radio Network via A Distributed Algorithm[J].IEEE Transactions on Communications,1981,29(11):1694-1701.
[19] 何鵬,閻保平,李志,等.CM-MAC:一種基于分簇的多信道車載網(wǎng)MAC協(xié)議[J].計算機研究與發(fā)展,2014,51(3):502-510.
[20] 高鍵鑫,吳曉平,吳旭升.采用信任度量的MANET網(wǎng)絡(luò)分簇模型[J].北京郵電大學(xué)學(xué)報,2014,37(S1):125-130.
[21] 馮文江,吳迪.鏈路可用性的MANET網(wǎng)絡(luò)分簇算法[J].重慶大學(xué)學(xué)報,2010,33(12):109-113.
[22] 秦茜,宋志群,劉玉濤.一種固定分配與動態(tài)競爭結(jié)合的MAC層協(xié)議算法[J].無線電工程,2017,47(2):11-14.
[23] MILES J,MUKNAHALLIPATNA S,KUBICHEK R F,et al.Use of Radio Propagation Maps in a Single Moving Beacon Assisted Localization in MANETs[C]∥2014 International Conference on Computing,Networking and Communications (ICNC),2014:871-877.