智慧機(jī)坪網(wǎng)格結(jié)構(gòu)下的負(fù)載均衡控制對策

費(fèi)春國，孟美含

（中國民航大學(xué)電子信息與自動化學(xué)院，天津300300）

近年來，智慧機(jī)場已成為中國民航業(yè)發(fā)展的重要切入點(diǎn)，而機(jī)坪作為智慧機(jī)場的一個重要子集，是機(jī)場運(yùn)行保障中最為復(fù)雜的場所，匯集了航空器、特種車輛和設(shè)備、旅客流、貨物行李流和大量機(jī)坪工作人員等多種要素。根據(jù)中國民用航空局《2014年機(jī)場運(yùn)行典型不安全事件匯總》統(tǒng)計(jì)顯示，當(dāng)年機(jī)場共發(fā)生典型不安全事件49 個，其中機(jī)坪運(yùn)行方面32 個，占65.3%[1]。因此，對節(jié)點(diǎn)眾多且分散、數(shù)據(jù)異構(gòu)的機(jī)坪資源進(jìn)行全面監(jiān)控是保障智慧機(jī)場安全與穩(wěn)定運(yùn)行的重點(diǎn)和難點(diǎn)。

傳統(tǒng)的無線傳感器網(wǎng)絡(luò)[2-3]（WSN，wireless sensor network）無法對機(jī)坪數(shù)據(jù)進(jìn)行實(shí)時、可靠及全面的監(jiān)測與傳輸，其在服務(wù)質(zhì)量、生存時間及能量消耗等方面還面臨挑戰(zhàn)[4]，其中能耗均衡問題是延長傳感器節(jié)點(diǎn)網(wǎng)絡(luò)生命周期的關(guān)鍵。文獻(xiàn)[5]中針對簇首負(fù)載不均衡問題，在簇首選舉中充分考慮節(jié)點(diǎn)剩余能量、與匯聚節(jié)點(diǎn)（sink）的距離和當(dāng)選簇首次數(shù)等因素，并利用模糊數(shù)學(xué)優(yōu)化簇首選舉過程和簇的結(jié)構(gòu)，實(shí)現(xiàn)非均勻分簇，但沒有考慮節(jié)點(diǎn)傳輸路徑對能耗的影響。文獻(xiàn)[6]為實(shí)現(xiàn)簇首選舉的負(fù)載均衡，對循環(huán)選取簇首的閾值進(jìn)行改進(jìn)，綜合考慮了節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)與sink 的距離和鄰居節(jié)點(diǎn)的個數(shù)，并且對每個影響因子進(jìn)行了加權(quán)。文獻(xiàn)[7]提出利用超級鏈路來執(zhí)行數(shù)據(jù)引流，進(jìn)而利用超級節(jié)點(diǎn)的硬件功能發(fā)揮其通信容量大的優(yōu)勢，實(shí)現(xiàn)數(shù)據(jù)流量再分配的負(fù)載均衡傳輸策略。

綜上，分簇路由算法雖然在一定條件下有效，但沒有考慮具體環(huán)境下的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)部署情況，節(jié)點(diǎn)能量不均衡問題仍未解決，且過多的優(yōu)選簇首條件加大了能量消耗。而機(jī)坪的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和數(shù)據(jù)處理是避免網(wǎng)絡(luò)擁塞、實(shí)現(xiàn)負(fù)載均衡的關(guān)鍵。故采用機(jī)坪網(wǎng)格規(guī)劃思想對機(jī)坪資源進(jìn)行模塊化管理，繼而通過改進(jìn)路由控制方法對每個網(wǎng)格子域進(jìn)行性能優(yōu)化，在實(shí)現(xiàn)局部良性連通和數(shù)據(jù)交互的基礎(chǔ)上，每個網(wǎng)格子域通過邊界網(wǎng)橋設(shè)備（Agent）進(jìn)行網(wǎng)格區(qū)域間信息傳輸，最終實(shí)現(xiàn)機(jī)坪資源感知網(wǎng)絡(luò)的全網(wǎng)管控。

1 機(jī)坪深度感知網(wǎng)絡(luò)架構(gòu)

機(jī)坪面積廣闊，涉及航班流、旅客流、貨物流、保障資源流等眾多要素。機(jī)坪資源可抽象為一個覆蓋機(jī)坪范圍的設(shè)備、設(shè)施、接口、人員等的異構(gòu)集合體，分為異構(gòu)節(jié)點(diǎn)和異構(gòu)數(shù)據(jù)集合，無法通過傳統(tǒng)WSN 進(jìn)行全局感知。

以航班流為驅(qū)動，將機(jī)坪資源進(jìn)行分塊整合處理，每個資源模塊部署相應(yīng)的現(xiàn)場資源監(jiān)控子網(wǎng)，監(jiān)控子網(wǎng)可隨著機(jī)坪資源模塊的增減而調(diào)整，網(wǎng)格子域之間通過邊界網(wǎng)橋設(shè)備進(jìn)行交互，機(jī)坪深度感知網(wǎng)絡(luò)架構(gòu)如圖1所示。

圖1 機(jī)坪深度感知網(wǎng)絡(luò)架構(gòu)Fig.1 Apron deep sense network architecture

2 機(jī)坪感知網(wǎng)絡(luò)應(yīng)用問題分析及對策

2.1 機(jī)坪網(wǎng)絡(luò)特性及其拓?fù)浞治?/h3>

在地域廣闊、節(jié)點(diǎn)眾多且異構(gòu)的網(wǎng)絡(luò)場景下，WSN存在很大缺陷[8-9]，在深刻分析機(jī)坪運(yùn)行特征基礎(chǔ)上，認(rèn)為機(jī)坪運(yùn)行受航班流驅(qū)動，并據(jù)此提出了航班流驅(qū)動的網(wǎng)格劃分方案。將機(jī)坪網(wǎng)絡(luò)劃分為n 個非均勻網(wǎng)格，表示為D=（D1，D2，…，Dn）；此外，考慮到機(jī)坪部分區(qū)域資源的硬件特性較強(qiáng)，在網(wǎng)格子域之間通過Agent 進(jìn)行數(shù)據(jù)交互連通，從而實(shí)現(xiàn)全機(jī)坪網(wǎng)絡(luò)拓?fù)洌鐖D2所示。

圖2 機(jī)坪網(wǎng)格結(jié)構(gòu)邏輯圖Fig.2 Logic diagram of apron grid structure

至此，可根據(jù)WSN 思想針對單網(wǎng)格內(nèi)拓?fù)浣Y(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計(jì)。

2.2 網(wǎng)格子域拓?fù)湓O(shè)計(jì)

針對單個網(wǎng)格子域進(jìn)行拓?fù)浼奥酚稍O(shè)計(jì)，首先進(jìn)行網(wǎng)格內(nèi)拓?fù)湓O(shè)計(jì)，引進(jìn)網(wǎng)絡(luò)模型：設(shè)每個網(wǎng)格子域內(nèi)是一個環(huán)形網(wǎng)域且具備sink 節(jié)點(diǎn)，從區(qū)域中心向外依次是（cor1,cor2,…,cori），cori表示第i 個圓環(huán)（根據(jù)機(jī)坪資源的部署特性，在每個子域內(nèi)選取地理位置布置高性能硬件資源作為固定sink 節(jié)點(diǎn)是可行的），位于cori個圓環(huán)內(nèi)的某一節(jié)點(diǎn)Nij負(fù)責(zé)將該環(huán)內(nèi)感知數(shù)據(jù)以多跳的方式傳送至sink 節(jié)點(diǎn)，設(shè)節(jié)點(diǎn)感知半徑為Rs，拓?fù)浣Y(jié)構(gòu)如圖3所示。

圖3 網(wǎng)格子域拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)圖Fig.3 Structural design diagram of grid subdomain topology

為使能耗利用率最大且達(dá)到負(fù)載均衡，在保證網(wǎng)絡(luò)覆蓋率的前提下，設(shè)節(jié)點(diǎn)分布密度為ρi，使整個區(qū)域重復(fù)覆蓋程度最小，并讓網(wǎng)絡(luò)能耗達(dá)到最優(yōu)，則此時的節(jié)點(diǎn)感知半徑[6]為等效感知半徑，即

而完全覆蓋區(qū)域的最小節(jié)點(diǎn)部署密度為

其中：F（i）為被節(jié)點(diǎn)Ni覆蓋的區(qū)域。

若利用節(jié)點(diǎn)Nij進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，根據(jù)等效感知半徑Ri與最優(yōu)節(jié)點(diǎn)部署密度ρi對節(jié)點(diǎn)進(jìn)行選擇，則當(dāng)?shù)刃Ц兄霃綕M足如下條件時，全網(wǎng)能夠達(dá)到均衡，即

其中：e1為節(jié)點(diǎn)發(fā)送1 bit 數(shù)據(jù)的能耗；e2為節(jié)點(diǎn)接受1 bit 數(shù)據(jù)的能耗。

綜上，按照所給密度部署公式對網(wǎng)格子域節(jié)點(diǎn)進(jìn)行部署，可避免密度不均造成網(wǎng)格子域的熱點(diǎn)問題，同時增加能耗的利用率。但數(shù)據(jù)傳輸路徑的隨機(jī)性是能耗不均的重要方面，因此有必要對網(wǎng)格子域內(nèi)路由傳輸進(jìn)行優(yōu)化。

3 路由問題分析與規(guī)劃

3.1 傳統(tǒng)WSN 路由算法的缺陷

傳統(tǒng)的WSN 感知方案采用LEACH（low energy adaptive clustering hierarchy）路由控制方法，但存在以下兩方面問題。

1）LEACH 協(xié)議通過循環(huán)方式不斷更換簇頭，但每個節(jié)點(diǎn)自身能耗和處理數(shù)據(jù)的性能差異較大，容易形成“死區(qū)”，根據(jù)機(jī)坪資源特性，可架設(shè)硬件資源豐富的節(jié)點(diǎn)成為優(yōu)選簇頭（甚至固定簇頭）。

2）普通節(jié)點(diǎn)傳送數(shù)據(jù)包到簇頭節(jié)點(diǎn)通過WSN 進(jìn)行自組網(wǎng)，這種傳輸方式會因?yàn)閿?shù)據(jù)傳輸?shù)谋闅v性導(dǎo)致數(shù)據(jù)擁塞以及節(jié)點(diǎn)能量消耗過快。

因此，需要基于以上問題考慮針對單個網(wǎng)格的WSN 路由控制。

蟻群優(yōu)化算法[10]（ACO, ant colony optimization）通常用于求解復(fù)雜的組合優(yōu)化問題，基于ACO 的機(jī)坪感知網(wǎng)絡(luò)主要用于網(wǎng)格子域內(nèi)的WSN 路徑搜索，與LEACH 協(xié)議不同的是機(jī)坪場景下可規(guī)定性能較好的有源設(shè)備按照能量供給程度作為固定簇頭。為達(dá)到數(shù)據(jù)的負(fù)載均衡，基于ACO 進(jìn)行路徑搜索改進(jìn)，避免數(shù)據(jù)傳輸?shù)膯我粌?yōu)化路徑造成的數(shù)據(jù)擁塞問題[11]，讓螞蟻按照信息素少的路徑優(yōu)先傳輸使得路徑具有發(fā)散性[12]，從而均衡各個路徑的能耗。

3.2 基于ACO 的A-LEACH 優(yōu)化算法

首先進(jìn)行數(shù)據(jù)的初始化，sink 節(jié)點(diǎn)獲取傳感器網(wǎng)絡(luò)拓?fù)浜湍芰砍跏记闆r，機(jī)坪網(wǎng)格子區(qū)域成簇，將能量參數(shù)引進(jìn)節(jié)點(diǎn)的閾值T（i）選取中，根據(jù)能量優(yōu)先級劃分出二級簇頭，在感知范圍內(nèi)的二級簇頭中進(jìn)行周期性的一級簇頭循環(huán)選取，即

繼而選擇路徑傳輸下一跳節(jié)點(diǎn)完成簇間路由，結(jié)合ACO 將數(shù)據(jù)發(fā)送給sink 節(jié)點(diǎn)，此時把節(jié)點(diǎn)的負(fù)載量考慮在內(nèi)，用剩余電量和消息轉(zhuǎn)發(fā)量來確定，則節(jié)點(diǎn)i 的負(fù)載量為

其中：q（i）為節(jié)點(diǎn)i 的空閑隊(duì)列（轉(zhuǎn)發(fā)量）長度；Q（i）為節(jié)點(diǎn)總隊(duì)列長度；eremain（i）為節(jié)點(diǎn)i 的剩余能量；Etotal（i）為節(jié)點(diǎn)i 的總能量；λe和λq分別為能量和隊(duì)列的權(quán)重。消息在隊(duì)列中會產(chǎn)生排隊(duì)延時，所以權(quán)重由實(shí)際應(yīng)用對實(shí)時性的要求確定。

由于網(wǎng)絡(luò)模型設(shè)計(jì)為網(wǎng)格子域內(nèi)的環(huán)形區(qū)域，作用于層次網(wǎng)絡(luò)，所以節(jié)點(diǎn)i 到下一跳節(jié)點(diǎn)距離相等。定義啟發(fā)因子ηij表示螞蟻從節(jié)點(diǎn)i 轉(zhuǎn)移到節(jié)點(diǎn)j 的期望程度，使得螞蟻趨向于走負(fù)載低的路徑，更加體現(xiàn)負(fù)載均衡的思想，啟發(fā)因子計(jì)算方式如下

為進(jìn)一步實(shí)現(xiàn)負(fù)載均衡，將標(biāo)準(zhǔn)ACO 轉(zhuǎn)移概率的信息素參數(shù)進(jìn)行負(fù)相關(guān)變換，從而讓螞蟻按照信息素少的路徑搜索，使傳輸路徑由收斂性變?yōu)榘l(fā)散性，達(dá)到負(fù)載均衡的目的，則t 時刻螞蟻k 由節(jié)點(diǎn)i 到節(jié)點(diǎn)j的概率為

其中：τij為邊（i，j）上的重要信息素量；α 和β 分別為信息素濃度和啟發(fā)因子的重要度；f（i）為螞蟻k 下一步允許走過的節(jié)點(diǎn)集合。在完成第一次搜索之后，路徑上的信息素濃度更新規(guī)則如下

其中：Δτki（jN）為本次循環(huán)中路徑上信息素增量；Q 為信息素強(qiáng)度，表示在一定強(qiáng)度上影響算法的收斂速度；Lk為第k 只螞蟻在本次循環(huán)中所走的總長度。隨著信息素的不斷積累，路徑越短，其上的信息素越多，路徑上信息素增加總量為

隨著時間流逝，信息素會不斷揮發(fā)，所以螞蟻需對環(huán)境信息素更新，局部更新公式如下

其中：σ 為環(huán)境對信息素?fù)]發(fā)系數(shù)，1-σ 表示信息衰減程度，為了防止信息的無限積累，令σ∈[0，1)。

當(dāng)節(jié)點(diǎn)確定多條路徑到一級簇頭節(jié)點(diǎn)時，會從其二級簇頭節(jié)點(diǎn)和其他從屬節(jié)點(diǎn)聚合數(shù)據(jù)，繼而使用單跳通信將數(shù)據(jù)發(fā)送到一級簇頭（CHs1）。為使傳感器網(wǎng)絡(luò)的生命周期最大化并節(jié)約節(jié)點(diǎn)能量，在完成數(shù)據(jù)聚合后，數(shù)據(jù)將被分層發(fā)送到基站。最后，網(wǎng)格邊界通過Agent 交互信息，從而實(shí)現(xiàn)機(jī)坪的全局監(jiān)控。

A-LEACH 算法流程圖如圖4所示。

圖4 A-LEACH 算法流程圖Fig.4 Flow chart of A-LEACH algorithm

4 仿真與驗(yàn)證

在Matlab 的仿真環(huán)境中，根據(jù)機(jī)坪的實(shí)際情況設(shè)置100 個節(jié)點(diǎn)，將監(jiān)測區(qū)域劃分成圓環(huán)，假設(shè)傳輸環(huán)境完全安全，且不受其他干擾因素影響，進(jìn)而遵循密度分布公式在200×200 單位區(qū)域中進(jìn)行仿真實(shí)驗(yàn)，MAC 層采用802.15.4 協(xié)議，網(wǎng)絡(luò)參數(shù)如表1所示。

表1 機(jī)坪設(shè)備監(jiān)控網(wǎng)絡(luò)參數(shù)Tab.1 Monitoring parameters of apron equipment

節(jié)點(diǎn)數(shù)據(jù)包傳輸量對比如圖5所示，可以看出，基于蟻群算法的A-LEACH 算法數(shù)據(jù)包的傳輸量明顯高于已有的DEEC 算法以及原LEACH 算法，這是因?yàn)镈EEC 算法根據(jù)節(jié)點(diǎn)的剩余能量水平和網(wǎng)絡(luò)的異構(gòu)性來決定簇首的選舉，在優(yōu)化簇首的同時增加了節(jié)點(diǎn)能耗，使得節(jié)點(diǎn)死亡速度過快、數(shù)據(jù)包傳輸量較低。而A-LEACH 算法利用邊界網(wǎng)橋設(shè)備與各子區(qū)域進(jìn)行數(shù)據(jù)交互并對網(wǎng)格子域進(jìn)行密度規(guī)劃，不但減小了節(jié)點(diǎn)傳輸距離，而且避免了因密度不均造成的網(wǎng)格子域內(nèi)熱點(diǎn)問題，降低了節(jié)點(diǎn)能耗。由此表明A-LEACH 算法相對DEEC 與原LEACH 算法增加了節(jié)點(diǎn)數(shù)據(jù)包的傳輸量。

圖5 節(jié)點(diǎn)數(shù)據(jù)包傳輸量對比Fig.5 Node packet transmission volume comparison

網(wǎng)絡(luò)中節(jié)點(diǎn)存活狀態(tài)情況如圖6所示，可以看出，DEEC 算法在2 300 輪就幾乎全部死亡，LEACH 算法在運(yùn)行到將近2 700 輪數(shù)的時候節(jié)點(diǎn)幾乎全部死亡，而A-LEACH 算法在3 000 輪左右節(jié)點(diǎn)能量才消耗干凈，DEEC 算法與原LEACH 算法節(jié)點(diǎn)死亡要比ALEACH 算法出現(xiàn)的早，且死亡率大大高于優(yōu)化后的算法。這是因?yàn)锳-LEACH 算法改進(jìn)了ACO 轉(zhuǎn)移概率公式，通過對信息素參數(shù)進(jìn)行負(fù)變換，讓螞蟻按照信息素少的路徑搜索，使得傳輸路徑由收斂性變?yōu)榘l(fā)散性，均衡了節(jié)點(diǎn)傳輸路徑，減少了單一路徑單個節(jié)點(diǎn)的能量消耗，提高了節(jié)點(diǎn)的存活率，由此表明A-LEACH算法能改善節(jié)點(diǎn)的能量均衡，延長網(wǎng)絡(luò)生命周期。

圖6 網(wǎng)絡(luò)生命周期對比Fig.6 Network life cycle comparison

5 結(jié)語

針對機(jī)坪實(shí)際監(jiān)控網(wǎng)絡(luò)特性，提出機(jī)坪網(wǎng)格結(jié)構(gòu)下的負(fù)載均衡控制對策，通過對機(jī)坪資源進(jìn)行網(wǎng)格劃分，局部設(shè)計(jì)優(yōu)化WSN 數(shù)據(jù)傳輸和匯集?；跈C(jī)坪實(shí)際作業(yè)情況在每個網(wǎng)格子域內(nèi)進(jìn)行拓?fù)湓O(shè)計(jì)，計(jì)算等效感知半徑。重點(diǎn)分析LEACH 協(xié)議的不足，由ACO結(jié)合LEACH 協(xié)議在多簇路由數(shù)據(jù)傳輸過程中按照低負(fù)載和低信息素的方式尋求多條傳輸路徑，避免網(wǎng)絡(luò)擁塞，從而達(dá)到均衡負(fù)載的目的。結(jié)果表明A-LEACH算法能夠更好地應(yīng)用于實(shí)際機(jī)坪感知監(jiān)控網(wǎng)絡(luò)，更好地利用有限帶寬資源，保證網(wǎng)絡(luò)監(jiān)控系統(tǒng)的可靠性。現(xiàn)有研究只是進(jìn)行網(wǎng)格內(nèi)數(shù)據(jù)傳輸優(yōu)化設(shè)計(jì)，對于靜態(tài)傳感網(wǎng)與移動節(jié)點(diǎn)Agent 的網(wǎng)格邊界數(shù)據(jù)交互是未來研究的重點(diǎn)問題。