任 智,周佳琦

(重慶郵電大學 通信與信息工程學院,重慶 400065)

0 引 言

近年來,無人機(Unmanned Aerial Vehicle,UAV) 自組網(wǎng)成為無人機網(wǎng)絡領域的研究熱點。無人機自組網(wǎng)通常采用分布式架構,這種架構為網(wǎng)絡帶來了一定的安全性,提高了網(wǎng)絡的工作效率。然而,不斷增長的網(wǎng)絡流量要求采用集中控制架構,這種集中控制方式可以帶來許多的好處。軟件定義網(wǎng)絡(Software-defined Netowrk,SDN)作為近年的研究熱點,可以很好地管理和部署無人機節(jié)點以應對上述挑戰(zhàn)[1]。然而SDN的集中控制方式、OpenFlow的異步性[2]以及無人機節(jié)點的快速移動等特性,對SDN的一致性更新提出了更高的要求。

針對SDN一致性更新的問題,Reitblatt等人[3]首次分析了在SDN中進行網(wǎng)絡更新的問題,提出了一種兩階段更新方法,并指出在流更新期間,數(shù)據(jù)包只能按照初始規(guī)則或最終規(guī)則轉發(fā),不能同時按照混合規(guī)則轉發(fā);文獻[4]通過時間同步,將數(shù)據(jù)包中的時間戳作為標簽,相比于兩階段方法減少了OpenFlow交換機中三態(tài)內容尋址存儲器(Ternary Content Addressable Memory,TCAM)存儲空間的占用[5];文獻[6]提出了一種添加和替換規(guī)則的混合規(guī)則方法FLIP以保留任意的策略和一致性,實驗結果表明FLIP相比于兩階段方法減少了90%的額外規(guī)則。針對軟件定義航空集群機載網(wǎng)絡鏈路擁塞問題,文獻[7]基于FLIP提出了擁塞避免算法,提高了更新成功率。對于無人機節(jié)點移動速度快導致網(wǎng)絡拓撲變化快,更新輪次問題同樣需要關注,更少的更新輪次可以提高網(wǎng)絡控制的靈活性,還可以對故障或更改工作負載做出更快反應[8]。文獻[9]分析了強無環(huán)路(Strong Loop-Freedom,SLF)更新方法存在的問題,并提出了弱無環(huán)路(Relax Loop-Freedom,RLF)更新方法,同時提出了Peacock算法,證明該算法最壞情況下以對數(shù)級輪次完成更新。文獻[10]在Peacock算法的基礎上提出了MRCU算法,改變奇數(shù)輪的更新節(jié)點選取操作,減少了更新輪次。以上研究雖然減少了更新輪次,但是忽略了轉發(fā)黑洞的問題。文獻[11]對SDN網(wǎng)絡中的轉發(fā)黑洞進行分析,研究發(fā)現(xiàn)Flow-mod消息的異步性可能導致三類轉發(fā)黑洞。

通過以上研究發(fā)現(xiàn),兩階段更新方法需要占用TCAM內存,因此不適合流數(shù)量較多的無人機場景。將數(shù)據(jù)包時間戳作為標簽的方法,雖然減少了TCAM內存占用,但是對時間同步要求較高。FLIP方法雖然顯著減少了TCAM存儲空間的占用,但是更新輪次較多。Peacock算法相比于SLF減少了更新輪次,但是沒有對轉發(fā)黑洞問題進行分析和處理。MRCU算法的平均更新輪次相比于Peacock算法減少了10%到20%,但是在只存在兩規(guī)則節(jié)點場景下,更新需要至少在3輪完成。因此,目前的SDN網(wǎng)絡更新方法在速度和一致性上對于無人機自組網(wǎng)場景的適用性還不足。

1 網(wǎng)絡場景和問題描述

1.1 網(wǎng)絡場景

軟件定義無人機自組網(wǎng)(Software-defined Unmanned Aerial Vehicle Ad Hoc Network,SDUANET)流更新如圖1所示,UAV節(jié)點與控制器之間通過OpenFlow協(xié)議通信,在控制器中的全網(wǎng)拓撲信息更新前,源節(jié)點UAV1以舊規(guī)則將數(shù)據(jù)包發(fā)送到目的節(jié)點UAV6。在數(shù)據(jù)平面,UAV節(jié)點周期性發(fā)送鄰居收集消息收集鄰居信息,然后通過OpenFlow消息將每個UAV節(jié)點的鄰居信息上傳到SDN控制器;SDN控制器計算得到新的全網(wǎng)拓撲,并向每個UAV節(jié)點分別下發(fā)添加新規(guī)則和刪除舊規(guī)則的指令。UAV節(jié)點在收到指令后完成操作并向控制器發(fā)送回復消息,控制器等待接收到所有的回復消息后完成更新。

圖1 SDUANET流更新示意

1.2 問題描述

1)轉發(fā)黑洞:由于UAV節(jié)點接收到Flow-mod消息的順序不確定導致轉發(fā)黑洞,以圖1為例,如果在UAV1到UAV7的舊規(guī)則上有數(shù)據(jù)包正在轉發(fā),此時UAV2和UAV5接收到Flow-mod(remove)并刪除舊規(guī)則,這種情況可能會導致正在轉發(fā)的數(shù)據(jù)包沒有對應表項進行匹配,雖然流表中存在Table-miss的表項用于處理未匹配數(shù)據(jù)包,但是Table-miss處理方式為向控制器發(fā)送請求消息或直接丟棄數(shù)據(jù)包[12],向控制器發(fā)送請求消息增大了網(wǎng)絡控制開銷和控制器的負載,直接丟棄數(shù)據(jù)包降低了更新期間數(shù)據(jù)包的傳輸成功率,因此需要找到一種約束Flow-mod發(fā)送順序的方法才能從根源上減少轉發(fā)黑洞所帶來的影響。

2)轉發(fā)環(huán)路:以圖1為例,UAV7節(jié)點表項已經(jīng)添加了新規(guī)則并刪除了舊規(guī)則,而UAV4節(jié)點未更新到新規(guī)則,還以舊規(guī)則轉發(fā),那么在UAV4和UAV7之間形成了一個暫時的環(huán)路,該環(huán)路導致了數(shù)據(jù)包端到端時延上升,甚至會到達生存時間(Time To Live,TTL),從而造成傳輸成功率降低和控制開銷增大。

2 概念解釋

如圖2所示,虛線表示新規(guī)則,實線表示舊規(guī)則,源節(jié)點為S,目的節(jié)點為D,括號中的數(shù)字代表的節(jié)點編號,左邊代表舊規(guī)則編號,右邊代表新規(guī)則編號。

圖2 流拓撲示意

正向與反向節(jié)點:正向節(jié)點的新規(guī)則所指向的下一跳節(jié)點為舊規(guī)則中正向節(jié)點的后序節(jié)點。例如,S、A和G節(jié)點為正向節(jié)點;與之相反的為反向節(jié)點,如B和F節(jié)點。

節(jié)點編號:S到D轉發(fā),按照遍歷節(jié)點的順序為節(jié)點編號。例如,節(jié)點A對于舊規(guī)則編號為2,對于新規(guī)則編號為5。

出度:節(jié)點的出邊條數(shù)。例如,節(jié)點A的舊規(guī)則出邊為1條,因此舊規(guī)則出度為1。

3 SDUANET快速一致性更新

針對SDUANET場景對網(wǎng)絡更新速度要求高,同時需要保證更新一致性的問題,本文提出了一種SDUANET快速一致性更新方法。該方法分為基于節(jié)點分類降低轉發(fā)黑洞概率策略和基于混合規(guī)則的兩輪更新策略:基于節(jié)點分類降低轉發(fā)黑洞概率策略對節(jié)點進行分類操作,對可能會導致轉發(fā)黑洞的發(fā)送操作進行約束;基于混合規(guī)則的兩輪更新策略用于計算存在新舊規(guī)則節(jié)點的Flow-mod下發(fā)順序,同時提出的兩輪次下發(fā)方法在保證避免轉發(fā)環(huán)路的同時減少了更新輪次。

3.1 基于節(jié)點分類降低轉發(fā)黑洞概率策略

本文提出了基于節(jié)點分類降低轉發(fā)黑洞概率策略,該策略根據(jù)節(jié)點出度對節(jié)點進行分類,將不同類型的單規(guī)則節(jié)點發(fā)送操作分別放入不同的操作集合中,并對部分節(jié)點添加發(fā)送約束。由于單規(guī)則節(jié)點的任意更新順序不會導致轉發(fā)環(huán)路,因此解決轉發(fā)環(huán)路的處理放在3.2節(jié)。

3.1.1 節(jié)點類型

如圖1所示,SDN中存在三種轉發(fā)黑洞情況[11]:

1)ADD:只存在新規(guī)則的節(jié)點,例如UAV3節(jié)點,這類節(jié)點在接收到數(shù)據(jù)包時還未收到Flow-mod(add)消息導致暫時轉發(fā)黑洞。

2)REMOVE:只存在舊規(guī)則的節(jié)點,例如UAV2和UAV5節(jié)點,這類節(jié)點提前接收到Flow-mod(remove)消息并刪除了流表項導致了永久轉發(fā)黑洞。

3)ALL:存在新舊兩種規(guī)則的節(jié)點,例如UAV1、UAV4和UAV7節(jié)點,這類節(jié)點在接收到Flow-mod(add)之前接收到了Flow-mod(remove)導致暫時轉發(fā)黑洞。

分類方法:根據(jù)每個節(jié)點的新規(guī)則和舊規(guī)則的出度進行判斷,如果新規(guī)則出度為1,舊規(guī)則的出度為0,節(jié)點為ADD節(jié)點;如果新規(guī)則出度為0,舊規(guī)則的出度為1,節(jié)點為REMOVE節(jié)點;如果新規(guī)則和舊規(guī)則的出度都為1,當前節(jié)點為ALL節(jié)點。

3.1.2 分類操作

降低轉發(fā)黑洞概率節(jié)點分類操作流程如圖3所示,具體步驟如下:

Step1 若所有參與更新的節(jié)點都已被處理則輸出OP1、OP2和OP4操作集合,若還有剩余節(jié)點未被處理則執(zhí)行Step 2。

Step2 根據(jù)節(jié)點的出度判斷其類型,如果為ADD節(jié)點則執(zhí)行Step 3,如果為REMOVE節(jié)點則執(zhí)行Step 4,如果為ALL節(jié)點則執(zhí)行Step 5。

Step3 比較當前節(jié)點的舊規(guī)則編號與新規(guī)則下一跳ALL節(jié)點的舊規(guī)則編號的大小關系,如果新規(guī)則下一跳ALL節(jié)點的舊規(guī)則編號大于當前節(jié)點的舊規(guī)則編號,當前節(jié)點為正向的ADD節(jié)點,執(zhí)行Step 6,否則執(zhí)行Step 7。

Step4 將REMOVE節(jié)點的更新操作以舊規(guī)則編號從小到大放入OP4中,并為每個節(jié)點加上約束關系:在收到了該節(jié)點在舊規(guī)則的上一個ALL節(jié)點發(fā)來的回復消息時,SDN控制器才為該節(jié)點發(fā)送Flow-mod(remove)。

Step5 將節(jié)點放在ALL節(jié)點集合中,然后執(zhí)行Step 1。

Step6 將正向ADD節(jié)點操作放入到OP1,然后執(zhí)行Step 1。

Step7 將反向ADD節(jié)點操作放入到OP2中,然后執(zhí)行Step 1。

圖3 降低轉發(fā)黑洞概率節(jié)點分類操作流程

3.2 基于混合規(guī)則的兩輪更新策略

本文提出了基于混合規(guī)則的兩輪更新策略,由于只有ALL節(jié)點在不合理下發(fā)順序情況下才會導致轉發(fā)環(huán)路,因此本小節(jié)對ALL節(jié)點導致的轉發(fā)環(huán)路問題進行處理。該策略包含ALL節(jié)點無環(huán)路發(fā)送順序和兩輪下發(fā)兩部分內容:第一輪,更新所有正向節(jié)點,同時下發(fā)關鍵節(jié)點的標簽操作和匹配操作規(guī)則,標簽和匹配規(guī)則設置生存時間為更新輪次的最大時間;第二輪,更新所有反向節(jié)點,標簽和匹配規(guī)則在生存時間到達后刪除,然后UAV節(jié)點切換到新的轉發(fā)規(guī)則。

3.2.1 ALL節(jié)點無環(huán)路發(fā)送順序

環(huán)路隔離節(jié)點:使數(shù)據(jù)包不會轉發(fā)到暫時形成的環(huán)路區(qū)域,其包括了MATCH節(jié)點和TAG節(jié)點,這兩類節(jié)點需要以環(huán)路區(qū)域為一組成對的發(fā)送:對MATCH節(jié)點下發(fā)匹配操作,其操作為匹配帶有TAG節(jié)點所標記的數(shù)據(jù)包,將該數(shù)據(jù)包以舊規(guī)則轉發(fā);對TAG節(jié)點下發(fā)標簽操作,對所有來自于MATCH節(jié)點的數(shù)據(jù)包打上標簽。

ALL節(jié)點Flow-mod發(fā)送順序的計算過程如圖4所示,具體步驟如下:

Step1 對所有ALL節(jié)點的類型進行判斷,并將其加入到更新操作,如果所有節(jié)點已完成處理則執(zhí)行Step 6,否則執(zhí)行Step 2。

Step2 比較當前節(jié)點的舊規(guī)則編號與新規(guī)則下一跳節(jié)點的舊規(guī)則編號的大小關系,如果新規(guī)則下一跳節(jié)點的舊規(guī)則編號大于當前節(jié)點的舊規(guī)則編號,當前節(jié)點為正向的ALL類節(jié)點,執(zhí)行Step 3,否則執(zhí)行Step 4。

Step3 將所有正向ALL類節(jié)點以從小到大的節(jié)點編號加入到OP3中,并為每個節(jié)點加上約束關系:在收到了該節(jié)點在新規(guī)則情況下到下一個ALL節(jié)點之間的路徑上的所有ADD節(jié)點的回復消息之后,控制器才向該節(jié)點發(fā)送Flow-mod(add)和Flow-mod(remove),然后執(zhí)行Step 1。

Step4 如果當前節(jié)點按照新規(guī)則的上一跳節(jié)點的舊規(guī)則編號小于當前節(jié)點的舊規(guī)則編號,同時按照新規(guī)則的下一跳節(jié)點的舊規(guī)則編號小于當前節(jié)點的舊規(guī)則編號,則選取該節(jié)點為MATCH節(jié)點,MATCH節(jié)點按照舊規(guī)則的上一跳節(jié)點選取為TAG節(jié)點,將MATCH和TAG操作加入到OP3中,然后執(zhí)行Step 1,否則執(zhí)行Step 5。

Step5 剩余反向ALL類節(jié)點添加到OP5,然后執(zhí)行Step 6。

Step6 輸出OP3和OP5操作集合。

圖4 ALL節(jié)點無環(huán)路發(fā)送順序計算流程

3.2.2 兩輪下發(fā)

兩輪下發(fā)過程如圖5所示,具體步驟如下:

Step1 控制節(jié)點按照OP1,OP2,OP3,OP4的順序向UAV節(jié)點發(fā)送Flow-mod消息,然后執(zhí)行Step 2。

Step2 控制節(jié)點等待接收所有更新回復消息,若全部收到則執(zhí)行Step 3,若沒有繼續(xù)執(zhí)行Step 2。

Step3 按照OP5向UAV節(jié)點發(fā)送Flow-mod消息,此時即使匹配和標簽節(jié)點收到了新規(guī)則仍然按照MATCH和TAG規(guī)則處理數(shù)據(jù)包,然后執(zhí)行Step 4。

Step4 MATCH和TAG節(jié)點判斷匹配和標簽規(guī)則是否到達生存時間,若到達則執(zhí)行Step 5,若沒有則繼續(xù)執(zhí)行Step 4。

Step5 刪除匹配和標簽操作,MATCH和TAG節(jié)點以新規(guī)則處理數(shù)據(jù)包。

圖5 兩輪下發(fā)流程圖

4 仿真驗證

文獻[13]對比了SDN戰(zhàn)術網(wǎng)絡場景下OPNET和Mininet的仿真性能,對比結果表明OPNET更適合對真實環(huán)境進行仿真或進行穩(wěn)定性和可靠性測試,因此本文采用OPNET14.5仿真軟件對SDUANET-FCU性能進行驗證。

4.1 仿真參數(shù)設置

主要仿真參數(shù)如表1所示。仿真場景由一個SDN控制器和多個UAV節(jié)點組成,在源UAV節(jié)點和目的UAV節(jié)點之間的UAV節(jié)點呈現(xiàn)為鏈狀的拓撲結構,路徑上的UAV節(jié)點按照規(guī)定的速度在源UAV節(jié)點和目的UAV節(jié)點之間隨機移動。

表1 主要仿真參數(shù)

4.2 性能指標

4.2.1 平均更新輪次

更新輪次定義為在保證數(shù)據(jù)包無轉發(fā)環(huán)路的情況下更新所有節(jié)點所需要的輪次。平均更新輪次的計算公式為

(1)

式中:n為總的更新流數(shù)量;ri為每個流的更新輪次。

4.2.2 轉發(fā)黑洞概率

轉發(fā)黑洞概率為數(shù)據(jù)包轉發(fā)時缺少流表項的次數(shù)占數(shù)據(jù)包轉發(fā)次數(shù)的比例,計算方法為

(2)

4.2.3 控制消息數(shù)量

由于流表項下發(fā)需要控制器向UAV節(jié)點下發(fā)Flow-mod,匹配Table-miss或TTL到達需要UAV節(jié)點向控制器節(jié)點Packet-in,以及控制器需要向UAV節(jié)點下發(fā)Packet-out指示如何對存在流表項缺失的數(shù)據(jù)包進行處理,因此本文統(tǒng)計的控制消息數(shù)量為網(wǎng)絡更新過程所產(chǎn)生的Flow-mod、Packet-in和Packet-out消息的總數(shù)量。

4.3 仿真分析

4.3.1 平均更新時間

表2為平均更新時間。更新時間與路徑節(jié)點數(shù)呈現(xiàn)一定的關系,隨著路徑節(jié)點數(shù)量的增加,平均更新輪次增加,因此平均更新時間上升。Peacock的更新輪次多于MRCU,因此在平均更新時間上Peacock高于MRCU。SDUANET-FCU在兩輪可以完成更新,因此平均更新低于前兩者。

表2 三種算法在不同路徑節(jié)點數(shù)下的平均更新時間

4.3.2 平均更新輪次

圖6為平均更新輪次。隨著路徑節(jié)點數(shù)量的增多,平均更新輪次也越來越大。這是因為路徑節(jié)點數(shù)的增多導致了拓撲更為復雜,在保證一致性情況下,需要進行多輪的更新。其中,MRCU相較于Peacock平均更新輪次更少,是因為Peacock在奇數(shù)輪更新時選取最大不相交節(jié)點更新,而MRCU選擇的是不相交最大和的節(jié)點進行更新,因此在奇數(shù)輪MRCU可以更新更多的節(jié)點;SDUANET-FCU平均更新輪次一直保持在兩輪,是因為SDUANET-FCU基于混合規(guī)則,這種混合規(guī)則使得第一輪可以更新所有前向節(jié)點,在第二輪更新所有反向節(jié)點和環(huán)路隔離節(jié)點,在保證了一致性更新的同時只需要兩輪。

圖6 平均更新輪次

4.3.3 轉發(fā)黑洞概率

圖7為轉發(fā)黑洞概率。隨著無人機移動速度的加快,轉發(fā)黑洞的概率也增加。這是因為網(wǎng)絡拓撲變化快,導致部分UAV節(jié)點的轉發(fā)規(guī)則與實際的網(wǎng)絡拓撲不符,即UAV節(jié)點內的轉發(fā)規(guī)則已經(jīng)過期。隨著無人機移動速度加快,MRCU和Peacock之間的轉發(fā)黑洞概率差距也越來越大。這是因為MRCU的平均更新輪次更快,MRCU具有更好的更新實時性。SDUANET-FCU轉發(fā)黑洞概率低于MRCU和Peacock,這是因為SDUANET-FCU在發(fā)送前對不同種類的Flow-mod進行了排序和約束等操作,從而降低了轉發(fā)黑洞概率。

圖7 轉發(fā)黑洞概率

4.3.4 控制消息數(shù)量

圖8為控制消息的數(shù)量。在路徑節(jié)點數(shù)較少時,MRCU和Peacock控制消息數(shù)量上相差不大,隨著節(jié)點數(shù)的增多,MRCU和Peacock在控制消息的數(shù)量上逐漸拉開差距。這是因為MRCU更新輪次更少,由于無人機的移動,輪次更少的更新方法整體上降低了轉發(fā)黑洞的次數(shù),因此降低了因匹配Table-miss表項而發(fā)送的Packet-in、Packet-out和Flow-mod的數(shù)量。SDUANET-FCU需要發(fā)送標簽和匹配規(guī)則以保證更新一致性,雖然增加了額外的控制消息數(shù)量,但是相較于前兩個方法,整體的控制消息數(shù)量更少,主要有如下的兩個原因:一是無人機的快速移動和更少的更新輪次,可以減輕拓撲變化所導致的更新一致性問題;二是SDUANET-FCU主動對轉發(fā)黑洞問題進行處理,減少了數(shù)據(jù)包匹配Table-miss表項的次數(shù),從而減少了流表項缺失處理過程所帶來的控制消息的數(shù)量。

圖8 控制消息數(shù)量

5 結束語

本文針對軟件定義無人機自組網(wǎng)中的轉發(fā)黑洞和更新輪次的問題,提出了SDUANET-FCU機制。新機制對更新節(jié)點根據(jù)節(jié)點出度進行分類操作:對部分單個規(guī)則的更新節(jié)點添加發(fā)送約束,降低轉發(fā)黑洞概率;針對兩規(guī)則節(jié)點,采用基于混合規(guī)則的兩輪更新策略,在保證無轉發(fā)環(huán)路情況下減少平均更新輪次。仿真結果表明,在軟件定義無人機自組網(wǎng)場景下,SDUANET-FCU機制在平均更新輪次、轉發(fā)黑洞率和控制消息數(shù)量等方面優(yōu)于MRCU和Peacock。未來的工作將對軟件定義無人機自組網(wǎng)場景下的一致性更新進行更深入的研究。