一種面向軟件定義移動(dòng)自組網(wǎng)的拓?fù)浒l(fā)現(xiàn)方法

　　摘要:移動(dòng)自組網(wǎng)在傳統(tǒng)的分布式組網(wǎng)方式下難以滿足復(fù)雜的業(yè)務(wù)需求對(duì)網(wǎng)絡(luò)QoS及安全性的高要求，基于SDN的移動(dòng)自組網(wǎng)架構(gòu)(SD-MANET)的提出為解決該問(wèn)題提供了有效的解決思路。在SD-MANET中，拓?fù)浒l(fā)現(xiàn)是控制器進(jìn)行流量調(diào)度與安全性控制的前提。

　　本文提出一種面向SD-MANET的拓?fù)浒l(fā)現(xiàn)方法，其主要思想是:利用連通支配集算法生成骨干網(wǎng)絡(luò)，由骨干節(jié)點(diǎn)將局部拓?fù)湫畔⑼ㄟ^(guò)上行通路上報(bào)給SDN控制器，控制器根據(jù)收集到的鄰接信息計(jì)算出全網(wǎng)拓?fù)�。本文方法通過(guò)限制向控制器上報(bào)局部拓?fù)湫畔⒌墓?jié)點(diǎn)數(shù)量來(lái)降低拓?fù)湫畔⑹占�過(guò)程中產(chǎn)生的額外開(kāi)銷。仿真結(jié)果表明，該方法能夠準(zhǔn)確地生成并維護(hù)網(wǎng)絡(luò)拓?fù)�，且具有較小的控制開(kāi)銷。

　　關(guān)鍵詞:移動(dòng)自組網(wǎng),軟件定義網(wǎng)絡(luò),拓?fù)浒l(fā)現(xiàn),骨干網(wǎng)

　　0引言

　　移動(dòng)自組網(wǎng)(MobileAdHocNetworks，MANET)因其獨(dú)立性、靈活性和適應(yīng)性被廣泛應(yīng)用于戰(zhàn)術(shù)通信、傳感網(wǎng)、社交網(wǎng)絡(luò)以及災(zāi)難恢復(fù)等場(chǎng)景[1]。近年來(lái)，越來(lái)越復(fù)雜的業(yè)務(wù)需求對(duì)MANET的安全性及QoS保證提出了更高的要求[2]。傳統(tǒng)MANET采用分布式組網(wǎng)方式，難以在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間根據(jù)網(wǎng)絡(luò)資源信息(端到端延遲、帶寬、丟包率)選擇最佳路由[3]，在提高安全性及QoS保證上遇到了瓶頸。軟件定義網(wǎng)絡(luò)技術(shù)(SoftwareDefinedNetwork，SDN)將網(wǎng)絡(luò)的控制平面和轉(zhuǎn)發(fā)平面解耦合，采用集中式控制替代原有的分布式控制[4]。

　　基于SDN的移動(dòng)自組網(wǎng)網(wǎng)絡(luò)架構(gòu)SD-MANET[5]為上述問(wèn)題提供了新的解決思路。控制器通過(guò)南向接口協(xié)議與網(wǎng)絡(luò)設(shè)備進(jìn)行通信，OpenFlow是目前主流的南向接口協(xié)議。區(qū)別于傳統(tǒng)MANET的分布式組網(wǎng)方式，一般來(lái)說(shuō)，SD-MANET中由控制器負(fù)責(zé)收集拓?fù)湫畔⒉⑦M(jìn)行全網(wǎng)拓?fù)鋵W(xué)習(xí)，進(jìn)而基于學(xué)習(xí)到的全網(wǎng)拓?fù)鋵?shí)現(xiàn)網(wǎng)絡(luò)流量調(diào)度和安全性控制[6]。拓?fù)浒l(fā)現(xiàn)是控制器管理整個(gè)SD-MANET的基礎(chǔ)。

　　從技術(shù)角度而言，將LLDP(LinkLayerDiscoveryProtocol)、OSPF(OpenShortestPathFirst)或者IS-IS應(yīng)用到OpenFlow中都可以用來(lái)進(jìn)行網(wǎng)絡(luò)拓?fù)錂z測(cè)[7]，但是它們并不適于SD-MANET，主要原因有:1)一般應(yīng)用在SDN交換機(jī)較少的有線網(wǎng)絡(luò)中，其協(xié)議報(bào)文及響應(yīng)機(jī)制對(duì)于無(wú)線窄帶網(wǎng)絡(luò)環(huán)境來(lái)說(shuō)，帶寬開(kāi)銷過(guò)大[8]。2)SD-MANET中因節(jié)點(diǎn)移動(dòng)、信道干擾、電量消耗等因素導(dǎo)致的拓?fù)渥兓�與有線網(wǎng)絡(luò)拓?fù)渥兓�相比頻繁且復(fù)雜得多，現(xiàn)有技術(shù)沒(méi)有針對(duì)性的解決方案[9]。

　　目前，在SD-MANET領(lǐng)域，不同的網(wǎng)絡(luò)架構(gòu)采用的拓?fù)浒l(fā)現(xiàn)方法也不盡相同。文獻(xiàn)[10]提出了一種基于SDN的戰(zhàn)術(shù)移動(dòng)自組網(wǎng)網(wǎng)絡(luò)架構(gòu)，由多個(gè)控制器分級(jí)對(duì)網(wǎng)絡(luò)進(jìn)行協(xié)同管理，控制器可以部署在指揮中心、便攜無(wú)線基礎(chǔ)設(shè)施或者移動(dòng)設(shè)備上，通過(guò)應(yīng)用層協(xié)議將節(jié)點(diǎn)本地拓?fù)湫畔�發(fā)送至控制器。例如，網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)運(yùn)行分布式組網(wǎng)協(xié)議OLSR可以得到全網(wǎng)拓?fù)鋄11]。

　　理論上來(lái)說(shuō)，控制節(jié)點(diǎn)可以利用SNMP等應(yīng)用層協(xié)議進(jìn)行拓?fù)湫畔⒌氖占�和更新。但是，該過(guò)程依賴于轉(zhuǎn)發(fā)層面的中繼廣播，控制開(kāi)銷較大，且獲取相關(guān)的設(shè)備信息及資源信息還需要進(jìn)行復(fù)雜的跨層協(xié)議設(shè)計(jì)和報(bào)文擴(kuò)展，開(kāi)發(fā)成本很高。文獻(xiàn)[12]提出了一種適用于無(wú)線傳感器網(wǎng)絡(luò)的開(kāi)源軟件定義網(wǎng)絡(luò)解決方案SDN-WISE，實(shí)現(xiàn)了基于狀態(tài)的OpenFlow流表處理機(jī)制，能夠降低傳感節(jié)點(diǎn)與控制器之間的信息傳遞代價(jià)。

　　文獻(xiàn)[13]基于SDN-WISE提出了拓?fù)浒l(fā)現(xiàn)協(xié)議FTDP，協(xié)議基于模糊理論綜合考慮節(jié)點(diǎn)的鄰居數(shù)、剩余能量以及工作負(fù)載對(duì)拓?fù)浒l(fā)現(xiàn)及路由決策模塊進(jìn)行了優(yōu)化，但計(jì)算量大，對(duì)拓?fù)渥兓�的適應(yīng)性較差。文獻(xiàn)[14]提出一種將異構(gòu)戰(zhàn)術(shù)網(wǎng)與SDN相結(jié)合的架構(gòu)SDBN，通過(guò)異構(gòu)子網(wǎng)內(nèi)固定的網(wǎng)關(guān)節(jié)點(diǎn)向控制器上報(bào)子網(wǎng)拓?fù)洹?/p>

　　在文獻(xiàn)[15]提出的網(wǎng)絡(luò)模型SD-TAODV中，控制器周期性地向鄰居節(jié)點(diǎn)廣播拓?fù)湔?qǐng)求報(bào)文，報(bào)文在節(jié)點(diǎn)間逐層向外擴(kuò)散，報(bào)文每到達(dá)一個(gè)節(jié)點(diǎn)，就將當(dāng)前節(jié)點(diǎn)加入到所攜帶的拓?fù)淞斜碇�，并將�?bào)文返回給控制器。該方法通用性較強(qiáng)，但報(bào)文處理復(fù)雜，控制開(kāi)銷很大。本文提出一種新的拓?fù)浒l(fā)現(xiàn)方法。該方法基于連通支配集的思想減少網(wǎng)絡(luò)中直接與控制器交互鄰接信息的節(jié)點(diǎn)數(shù)量，從而減少拓?fù)浒l(fā)現(xiàn)過(guò)程中的帶寬開(kāi)銷，且在理論上具備一定的通用性。實(shí)驗(yàn)表明，本文方法具有較小的控制開(kāi)銷，且能夠及時(shí)感知拓?fù)渥兓��?/p>

　　1拓?fù)浒l(fā)現(xiàn)方法的基本思想

　　在SD-MANET中，選擇網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)來(lái)部署控制器，這個(gè)節(jié)點(diǎn)作為網(wǎng)絡(luò)中的控制節(jié)點(diǎn)(CN)與其他轉(zhuǎn)發(fā)節(jié)點(diǎn)一樣具有移動(dòng)性。拓?fù)浒l(fā)現(xiàn)需要考慮以下2個(gè)問(wèn)題:1)不同于有線網(wǎng)絡(luò)中有專門(mén)的轉(zhuǎn)發(fā)設(shè)備(交換機(jī)或路由器)來(lái)協(xié)調(diào)各終端設(shè)備間的通信，SD-MANET中的每個(gè)節(jié)點(diǎn)既是終端節(jié)點(diǎn)，又是轉(zhuǎn)發(fā)節(jié)點(diǎn)。如果網(wǎng)絡(luò)中的每個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)都向CN上報(bào)本地的局部拓?fù)�，產(chǎn)生的控制信息必然會(huì)帶來(lái)大量的帶寬開(kāi)銷，CN會(huì)收到大量的冗余信息。因此，應(yīng)該選取盡可能少的節(jié)點(diǎn)負(fù)責(zé)上報(bào)局部拓?fù)湫畔ⅰ?)節(jié)點(diǎn)移動(dòng)性將導(dǎo)致CN與轉(zhuǎn)發(fā)節(jié)點(diǎn)間的通信是不穩(wěn)定的，故節(jié)點(diǎn)需要及時(shí)更新并維護(hù)到CN的上行通路，以減少局部拓?fù)湫畔⑸蠄?bào)過(guò)程中的報(bào)文丟失。

　　針對(duì)上述2個(gè)問(wèn)題，本文提出:從所有節(jié)點(diǎn)中選取一部分通信能力強(qiáng)、穩(wěn)定性高的節(jié)點(diǎn)集合構(gòu)成一個(gè)骨干網(wǎng)，骨干節(jié)點(diǎn)通過(guò)到CN的上行通路向CN上報(bào)本地的局部拓?fù)湫畔�。整個(gè)拓?fù)浒l(fā)現(xiàn)過(guò)程主要包括2個(gè)階段:骨干網(wǎng)的構(gòu)造和拓?fù)湫畔⒌氖占�與維護(hù)。拓?fù)浒l(fā)現(xiàn)過(guò)程如下:1)在SD-MANET中構(gòu)造一個(gè)骨干網(wǎng)。2)各骨干節(jié)點(diǎn)獲取并維護(hù)到CN的上行通路。3)各骨干節(jié)點(diǎn)將本地鄰居信息上報(bào)給CN。4)CN分析并處理收集到的拓?fù)湫畔�，生成全網(wǎng)拓?fù)洹?/p>

　　2骨干網(wǎng)的構(gòu)造

　　上文提到需要選取一部分節(jié)點(diǎn)集合來(lái)構(gòu)造骨干網(wǎng)。這部分節(jié)點(diǎn)集合應(yīng)當(dāng)具備以下特性:特性1集合中各節(jié)點(diǎn)的通信范圍能夠覆蓋到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。特性2集合中的節(jié)點(diǎn)個(gè)數(shù)應(yīng)當(dāng)盡可能地小。特性3集合中的節(jié)點(diǎn)應(yīng)當(dāng)具有較高的通信帶寬，以保證較高的數(shù)據(jù)處理能力。為了得到滿足條件的節(jié)點(diǎn)集合，本文將SD-MANET抽象為一個(gè)無(wú)向圖模型，節(jié)點(diǎn)、各節(jié)點(diǎn)間的通信鏈路分別被抽象為圖中的點(diǎn)和邊。

　　2.1連通支配集算法

　　求任意圖的最小連通支配集是NP-難問(wèn)題[16]，因此，目前在實(shí)際應(yīng)用中，通常用近似解來(lái)代替最優(yōu)解。(n表示節(jié)點(diǎn)數(shù)量;Δ表示最大鄰居數(shù))。文獻(xiàn)[17]提出的基于多點(diǎn)中繼(MultipointRelays，MPR)計(jì)算連通支配集的算法MPR-CDS允許節(jié)點(diǎn)根據(jù)其被選為MPR的次數(shù)和選擇其作為MPR的節(jié)點(diǎn)(MPRSelector)個(gè)數(shù)或者其他業(yè)務(wù)條件約束來(lái)調(diào)節(jié)自身意愿度(willingness)。與其他算法相比，該算法能夠保證選出的骨干節(jié)點(diǎn)與普通節(jié)點(diǎn)之間的鏈路雙向?qū)ΨQ。

　　本文使用該算法來(lái)生成骨干網(wǎng)絡(luò)，網(wǎng)絡(luò)運(yùn)行過(guò)程中可通過(guò)調(diào)節(jié)某目標(biāo)節(jié)點(diǎn)的willingness對(duì)骨干網(wǎng)進(jìn)行管理。該算法的核心思想是采用貪心算法為每個(gè)節(jié)點(diǎn)v根據(jù)其二跳鄰居信息N2(v)從一跳鄰居信息N1(v)中選擇一組中繼節(jié)點(diǎn)MPR，網(wǎng)絡(luò)中所有的MPR節(jié)點(diǎn)可以構(gòu)成一個(gè)連通支配集，然后執(zhí)行CDS強(qiáng)化規(guī)則減小這個(gè)基于局部信息計(jì)算出的CDS規(guī)模[18]。2條規(guī)則如下，對(duì)于節(jié)點(diǎn)v，若滿足以下規(guī)則中的任意一條，便將其加入CDS。

　　3拓?fù)湫畔⒌氖占�與維護(hù)

　　3.1上行通路的計(jì)算策略

　　骨干網(wǎng)構(gòu)造完成之后，所有的骨干節(jié)點(diǎn)需要及時(shí)建立并維護(hù)到CN的上行通路。已知對(duì)于任一個(gè)普通節(jié)點(diǎn)，它至少是一個(gè)骨干節(jié)點(diǎn)的一跳鄰居，故本文旨在構(gòu)造一棵以CN為根節(jié)點(diǎn)的生成樹(shù)，這棵樹(shù)上，所有骨干節(jié)點(diǎn)均為CN的子孫，每個(gè)骨干節(jié)點(diǎn)到其父節(jié)點(diǎn)的鏈路即為到CN的上行通路。每個(gè)節(jié)點(diǎn)維護(hù)一張DV表(Distance-VectorTable)，用于存儲(chǔ)節(jié)點(diǎn)到CN的可達(dá)信息。表項(xiàng)中，next_hop表示本節(jié)點(diǎn)到CN的下一跳，cost表示經(jīng)過(guò)當(dāng)前下一跳到達(dá)CN的鏈路代價(jià)，SN是表示當(dāng)前可達(dá)信息新舊程度的序列號(hào)[22]。

　　節(jié)點(diǎn)周期性地發(fā)送控制鏈路消息CL_MSG，該消息類似于HELLO消息，即只在一跳范圍內(nèi)廣播，不能被轉(zhuǎn)發(fā)，報(bào)文字段主要有該節(jié)點(diǎn)到CN的鏈路代價(jià)cost和序列號(hào)SN。節(jié)點(diǎn)之間通過(guò)交互CL_MSG消息來(lái)更新并維護(hù)DV表。每個(gè)節(jié)點(diǎn)在到達(dá)下一個(gè)CL_MSG廣播周期或者DV表發(fā)生變化時(shí)執(zhí)行DV表更新過(guò)程DV_Updating，該過(guò)程的具體描述如下:Step1節(jié)點(diǎn)生成一條CL_MSG，并廣播。

　　Step2收到CL_MSG的鄰居Ni判斷自身是否為骨干節(jié)點(diǎn)。Step2.1若是，執(zhí)行Step3。Step2.2否則，丟棄該消息。Step3判斷CL_MSG→SN是否大于本地當(dāng)前DV表中已經(jīng)存在的最大SN。Step3.1若大于，執(zhí)行Step4。Step3.2若等于，但cost(Ni，CL_MSG→Src)+CL_MSG→cost的值比對(duì)應(yīng)表項(xiàng)中的cost更小，執(zhí)行Step4。Step3.3否則，丟棄該消息。Step4新建或更新DV表中到CN的表項(xiàng)，執(zhí)行Step1。

　　上文中Cost(i，j)表示i和j這一對(duì)直連鄰居之間的鏈路代價(jià)，通過(guò)查找節(jié)點(diǎn)i的鄰居表即可得到。初始情況下，CN的DV表中僅存在一個(gè)條目，其他節(jié)點(diǎn)的DV表為空。DV_Updating過(guò)程從CN生成CL_MSG(CN)并向外廣播開(kāi)始起作用。在DV_Updating過(guò)程中，SN的初始化及周期性偶數(shù)遞增的操作只能由CN來(lái)完成，SN從0開(kāi)始。

　　值得注意的是，CL_MSG消息從CN自頂向下傳播的是SN為偶數(shù)的鏈路信息，當(dāng)骨干節(jié)點(diǎn)檢測(cè)到鏈路故障時(shí)，將SN加1置為奇數(shù)沿著上行通路自下而上進(jìn)行傳播，以通告鏈路故障。DV表中的每一條可達(dá)信息都包含一個(gè)SN，如果收到了來(lái)自不同節(jié)點(diǎn)的CL_MSG消息，選擇SN較大的那條對(duì)DV表進(jìn)行更新。這一消息處理機(jī)制能夠保證DV表中的可達(dá)信息都是最新的。

　　4性能仿真與分析

　　本文主要使用OPNET18.6.1仿真軟件和OpenDayLight控制器對(duì)本文方法進(jìn)行可行性驗(yàn)證與性能分析。

　　4.1仿真實(shí)驗(yàn)環(huán)境

　　仿真平臺(tái)由實(shí)物環(huán)境和OPNET仿真環(huán)境2個(gè)部分構(gòu)成。其中，OPNET通過(guò)SITL接口與OpenDayLight通信，OpenDayLight通過(guò)OpenFlow協(xié)議與OPNET中的SDN交換機(jī)通信。各節(jié)點(diǎn)以packet-in和packet-out消息的形式向控制器傳送拓?fù)湫畔�。在OpenDayLight中添加Topology-Generator模塊，負(fù)責(zé)根據(jù)收集得到的局部拓?fù)湫畔⑸�成并更新全網(wǎng)拓?fù)洹?/p>

　　由于目前OPNET中的SDN交換機(jī)模型僅支持有線鏈路通信，為了使其適應(yīng)無(wú)線環(huán)境，本文對(duì)SDN有線交換機(jī)模型做了修改。物理層使用無(wú)線收發(fā)信機(jī)代替有線收發(fā)信機(jī)，使之支持無(wú)線收發(fā);MAC層采用TDMA技術(shù)實(shí)現(xiàn)信道復(fù)用;通過(guò)OPNET將SDN交換節(jié)點(diǎn)的屬性由固定節(jié)點(diǎn)修改為移動(dòng)節(jié)點(diǎn)，使之具備移動(dòng)性，并在其節(jié)點(diǎn)模型中新增MPR-CDS模塊，用于構(gòu)造骨干網(wǎng)。

　　對(duì)OPNET18.6.1的通用仿真參數(shù)進(jìn)行設(shè)定:信道傳輸速率設(shè)定為11Mbps，傳輸層使用UDP協(xié)議，MAC層使用IEEE802.11b協(xié)議，仿真場(chǎng)景中的節(jié)點(diǎn)隨機(jī)分布于20km×20km的矩形區(qū)域中，每組仿真實(shí)驗(yàn)的結(jié)果取20次運(yùn)行的均值。

　　4.2實(shí)驗(yàn)結(jié)果分析

　　4.2.1MPR-CDS算法性能

　　通過(guò)修改節(jié)點(diǎn)傳輸半徑來(lái)調(diào)節(jié)節(jié)點(diǎn)平均鄰居數(shù)。分別對(duì)節(jié)點(diǎn)平均鄰居數(shù)N為5、10、15、20時(shí)的場(chǎng)景執(zhí)行節(jié)點(diǎn)編址規(guī)則優(yōu)化后的MPR-CDS算法，并統(tǒng)計(jì)不同網(wǎng)絡(luò)規(guī)模下選出的骨干節(jié)點(diǎn)個(gè)數(shù)占比。該算法可以有效減少網(wǎng)絡(luò)中上報(bào)局部拓?fù)湫畔⒌墓?jié)點(diǎn)數(shù)量，仿真結(jié)果與原算法基本一致。相同網(wǎng)絡(luò)規(guī)模下，隨著節(jié)點(diǎn)傳輸半徑的增加，算法計(jì)算得出的連通支配集節(jié)點(diǎn)個(gè)數(shù)隨之減少;當(dāng)節(jié)點(diǎn)傳輸半徑保持不變時(shí)，連通支配集的節(jié)點(diǎn)個(gè)數(shù)隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增大而增大。

　　5結(jié)束語(yǔ)

　　本文分析了在SD-MANET中進(jìn)行拓?fù)浒l(fā)現(xiàn)需要解決的問(wèn)題，提出了一種適用于SD-MANET的拓?fù)浒l(fā)現(xiàn)方法。通過(guò)分析常用的最小連通支配集近似算法及影響骨干網(wǎng)通信能力的主要因素，對(duì)于MPR-CDS算法的節(jié)點(diǎn)編址規(guī)則進(jìn)行了優(yōu)化，在一定程度上提高了生成的骨干網(wǎng)絡(luò)的通信能力;并提出了在骨干網(wǎng)與控制節(jié)點(diǎn)之間建立有效的上行通路的策略。

　　本文使用OpenDayLight控制器以及OPNET仿真軟件進(jìn)行了仿真測(cè)試。實(shí)驗(yàn)結(jié)果表明，本文方法具有較小的控制開(kāi)銷，且能夠及時(shí)響應(yīng)拓?fù)渥兓�并更新全網(wǎng)拓?fù)�。但本文方法還存在一定的局限性，如:骨干節(jié)點(diǎn)選擇冗余、較大網(wǎng)絡(luò)規(guī)模(大于100節(jié)點(diǎn))的動(dòng)態(tài)場(chǎng)景下對(duì)網(wǎng)絡(luò)變化的適應(yīng)周期過(guò)長(zhǎng)等，故仍然需要對(duì)CDS算法及報(bào)文設(shè)計(jì)進(jìn)行優(yōu)化，并采用適當(dāng)?shù)墓收仙蠄?bào)機(jī)制來(lái)解決拓?fù)漤憫?yīng)時(shí)間長(zhǎng)的問(wèn)題。筆者將在后續(xù)工作中進(jìn)一步對(duì)當(dāng)前方法進(jìn)行改進(jìn)。

　　計(jì)算機(jī)技術(shù)論文投稿刊物：《計(jì)算機(jī)仿真雜志》(ComputerSimulation)雜志創(chuàng)刊于1984年，由中國(guó)航天科工集團(tuán)公司主管,由航天科工集團(tuán)十七所主辦。本刊組織的欄目有：仿真技術(shù)綜述、軍事領(lǐng)域仿真、人工智能與系統(tǒng)分析、航空、航天領(lǐng)域仿真、化工領(lǐng)域仿真、汽車仿真、分布交互式實(shí)時(shí)仿真、仿真應(yīng)用與研究、過(guò)程的建模與驗(yàn)證、仿真培訓(xùn)系統(tǒng)、虛擬仿真、仿真方法與算法等20多個(gè)欄目。

轉(zhuǎn)載請(qǐng)注明來(lái)自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/20825.html