吳佳楠, 吳 劍, 邸煥雙, 王玉英, 李念峰
(長春大學 網(wǎng)絡(luò)安全學院, 長春 130022)
以自主式水下航行器AUV(autonomous underwater vehicle)[1]為代表的水中機器人, 因具有良好的自主性和靈活性, 已成為一種行之有效的水下探索工具. 張晗等[2]研究了一種新的水下電場通信仿箱鲀機器魚, 其仿生對象箱鲀魚有一種特殊的電感知能力, 可通過特殊的放電器官發(fā)射一種稱為EOD(electric organ discharges)的脈沖式信號, 與同類物種交流信息, 還能主動探測周圍環(huán)境. 仿箱鲀機器魚具有體積緊湊、 能耗低、 全向性好等優(yōu)點, 可只靠0.81 W的發(fā)射功率在3~5 m的通信距離上進行約1 KB/s的數(shù)據(jù)傳輸. 實現(xiàn)多個仿生機器魚的智能集群, 協(xié)同完成復雜任務(wù)是該領(lǐng)域的研究熱點[2].
分簇思想是一種有效的群體控制方法, 目前存在的分簇協(xié)議從網(wǎng)絡(luò)拓撲角度可分為兩種: 平面路由協(xié)議和分簇路由協(xié)議[3-4]. 常見的平面路由協(xié)議有DD(directed diffusion)[5],SAR(sequential assignment routing)[6],SPIN(sensor protocols for information via negotiation)[7]和K階生成簇算法等[8]. 該類協(xié)議的主要優(yōu)點是具有良好的健壯性和強連通性, 不易產(chǎn)生瓶頸效應, 適合小規(guī)模的網(wǎng)絡(luò)集群. 但無法針對特定環(huán)境進行通信資源的優(yōu)化, 網(wǎng)絡(luò)中無管理節(jié)點, 網(wǎng)絡(luò)的動態(tài)變化反應速度較慢[9]. 分簇協(xié)議的主要優(yōu)點是簇首負責管理, 大部分簇內(nèi)成員為“待機”狀態(tài), 可節(jié)省整個網(wǎng)絡(luò)的能量[10], 不同的簇相互組合便于分布式管理, 利于擴展[11]. 常見的分簇協(xié)議包含簇首產(chǎn)生、 簇形成和數(shù)據(jù)傳輸3個階段. 針對簇首形成的算法[12-13]目前有LEACH(low-energy adaptive clustering hierarchy)[14]及其相關(guān)優(yōu)化算法LEACH-C(LEACH-centralized)[15],HEED(hybrid energy-efficient distributed clustering)[16]算法和CEFL(cluster-head election using fuzzy logic)[17]算法等, 其中LEACH將整個網(wǎng)絡(luò)的能量消耗分布到每個節(jié)點中, 從而有效延長網(wǎng)絡(luò)生命周期. 針對形成簇階段的算法有ACMWN(adaptive clustering for mobile wireless networks)[18],PEGASIS(power-efficient gathering in sensor information systems)[19]和HYENAS(hybrid energy-aware sensor network)[20]等, 其中ACMWN算法更簡單有效, 每個節(jié)點獨立運行, 廣播交換信息, 基于最小ID選舉簇頭, 形成簇. 針對數(shù)據(jù)傳輸階段的算法有PEGASIS(power-efficient gathering in sensor information systems),TEEN(threshold sensitive energy efficient sensor network protocol)[21]和APTEEN(adaptive periodic threshold sensitive energy efficient sensor network protocol)[22]等. 上述分簇算法更注重于信息傳遞過程的優(yōu)化及基于強連通性的群體節(jié)點一體化控制, 雖能有效提高群體控制效率并改善網(wǎng)絡(luò)性能, 但缺少靈活性.
水下智能集群在實現(xiàn)有效控制節(jié)點的前提下, 進一步降低群體內(nèi)耗實現(xiàn)總體能量的最大化輸出, 是其面向?qū)嵱没囊豁椫匾繕? 為在實現(xiàn)群體的有效協(xié)同及靈活控制的同時盡可能減少網(wǎng)絡(luò)整體能耗, 提升續(xù)航能力, 本文提出一種基于邏輯分區(qū)的仿箱鲀魚群負載均衡分簇控制算法. 先采用改進的ACMWN算法實現(xiàn)局部快速分簇, 減少節(jié)點間維護報文數(shù)量, 降低系統(tǒng)整體開銷; 再基于簇內(nèi)邏輯分區(qū)策略, 實現(xiàn)監(jiān)測、 保障和偵察多區(qū)域協(xié)同控制, 并結(jié)合最小響應時間整編零散魚群, 優(yōu)化網(wǎng)絡(luò)控制體系的同時提高組網(wǎng)靈活性; 最后在維護過程中采用區(qū)域節(jié)點角色轉(zhuǎn)換機制, 實現(xiàn)網(wǎng)絡(luò)負載均衡.
圖1 仿生魚體功能模塊Fig.1 Function module of bionic fish body
機器魚體主要包括初始化器、 事件生成器、 輸入/輸出模塊、 報文分類處理器、 群內(nèi)成員更新模塊、 鄰居群表更新模塊、 數(shù)據(jù)庫7個組成部分, 如圖1所示. 為提高處理效率并減輕系統(tǒng)負擔, 整體設(shè)計為單進程結(jié)構(gòu), 各模塊間的交互采用函數(shù)調(diào)用和數(shù)據(jù)傳輸?shù)姆绞? 仿生魚體各模塊功能如下.
1) 初始化器: 初始化機器魚的身份標識和能量權(quán)值, 啟動系統(tǒng).
2) 事件生成器: 生成事件, 驅(qū)動算法正常執(zhí)行; 維護報文隊列, 提供函數(shù)接口.
3) 輸入/輸出模塊: 調(diào)用服務(wù), 解析報文.
4) 報文分類處理器: 從事件生成器接收報文, 通過報文標識判斷事件類型, 事件分為更新群內(nèi)成員事件和更新鄰居群表事件.
5) 群內(nèi)成員表更新模塊: 更新群內(nèi)成員表信息, 群內(nèi)成員表中信息包括網(wǎng)絡(luò)號、 群內(nèi)成員標識、 區(qū)標識、 響應時間和能量權(quán)值.
6) 鄰居群表更新模塊: 更新鄰居群表信息, 鄰居群表信息主要包括鄰居群網(wǎng)絡(luò)號、 響應時間、 網(wǎng)絡(luò)規(guī)模等.
本文用G表示圖,V表示頂點集,E表示邊集,C表示群集, ID表示身份標識,Wn表示能量權(quán)值, CH表示簇首標識, CRA表示中心簇首標識,T表示響應時間, Msg表示信息報文.
網(wǎng)絡(luò)參數(shù)設(shè)定如下:
1) 簇內(nèi)機器魚數(shù)量區(qū)間設(shè)為[cl,cu], 其中cl為下限值,cu為上限值;
2) 機器魚的電量最低為Pmin, 簇首電量降到Pmin時與監(jiān)測區(qū)節(jié)點互換, 監(jiān)測區(qū)或偵察區(qū)節(jié)點電量降到Pmin時與保障區(qū)節(jié)點互換;
3) 每條魚的ID全網(wǎng)唯一;
4) 魚群采用水下電場通信的工作方式交互信息, 最大有效通信距離為8 m.
定義1網(wǎng)絡(luò)拓撲可視為由節(jié)點和鏈路構(gòu)成的圖, 記為G=(V,E), 其中:V表示節(jié)點集合;E表示鏈路集合. 任意節(jié)點Vi和Vj之間被稱為互相通信的一跳鄰居時, 當且僅當Vi和Vj之間存在邊E(i,j).
定義2(鄰居簇) 兩個簇通過各自偵察區(qū)可建立連接, 即兩個簇互為鄰居簇.
定義3(簇連接度) 某簇的鄰居簇個數(shù)稱為該簇的簇連接度.
定義4(能量權(quán)值) 能量權(quán)值為區(qū)域角色轉(zhuǎn)換的參考值, 記為Wn. 當簇首或偵察區(qū)節(jié)點電量降到Pmin時, 選擇Wn最大的節(jié)點更換區(qū)域角色, 表示為
Wn=e1×σP-e2×τT,
(1)
e1+e2=1,
(2)
其中:Wn表示每個節(jié)點的權(quán)值;e1,e2為(可調(diào)節(jié))權(quán)值系數(shù);σ,τ為歸一化系數(shù);P表示節(jié)點當前剩余電量;T表示與簇首的響應時間, 反應其與簇首的距離.
2.2.1 基于ACMWN的快速分簇 該過程基于ACMWN算法分簇思想, 實現(xiàn)局部快速分簇, 減少節(jié)點間維護報文數(shù)量, 降低系統(tǒng)整體開銷. 基于ACMWN的快速分簇過程如下:
步驟1) 初始化信息, 每條魚Vi具有唯一的IDi;
步驟2) 如果E(i,j)≠?, 則Vi向Vj廣播自己的ID號;
步驟3) ID號比周圍低的節(jié)點被選舉為簇首CH, CH向鄰居節(jié)點廣播當選簇首的信息MsgA, 收到MsgA的鄰居節(jié)點加入簇A, 并向簇首CH單播申請加入簇的消息MsgB;
步驟4) 簇首CH對收到消息的MsgB計數(shù), 如果數(shù)量達到cu, 則拒絕加入;
步驟5) 如果未達到cu, 則簇首CH對收到的申請節(jié)點進行回復, 收到回復的鄰居節(jié)點加入簇A, 并向附近廣播已加入簇A的消息;
步驟6) 其余未成簇的節(jié)點重復上述過程, 直至形成所有的簇.
圖2 邏輯分區(qū)示意圖Fig.2 Schematic diagram of logical partition
2.2.2 簇內(nèi)動態(tài)邏輯分區(qū) 簇內(nèi)采用邏輯分區(qū)的思想, 劃分為監(jiān)測區(qū)MA(monitoring-area)、 保障區(qū)GA(guarantee-area)和偵察區(qū)RA(reconnaissance-area), 區(qū)域間在物理上無明顯界限, 個體節(jié)點按區(qū)域功能轉(zhuǎn)換角色, 不需要物理上的移動, 實現(xiàn)簇內(nèi)能量均衡, 以提高整體續(xù)航能力. 邏輯分區(qū)方式如圖2所示, 其中: 簇首CH具有維持簇內(nèi)基本管理的作用, 發(fā)布任務(wù), 確定魚群運動方向; 監(jiān)測區(qū)MA負責實時監(jiān)控簇首狀態(tài), 如果簇首CH電量達到Pmin值, 則與監(jiān)測區(qū)內(nèi)最大能量權(quán)值節(jié)點進行角色更換; 偵查區(qū)RA負責外聯(lián), 并通過傳感器探測群體周圍環(huán)境; 保障區(qū)GA的主要功能是更換監(jiān)測區(qū)和偵察區(qū)能量到達Pmin的成員角色. 多區(qū)域協(xié)同及區(qū)域節(jié)點角色轉(zhuǎn)換機制, 實現(xiàn)了群體網(wǎng)絡(luò)的負載均衡.
簇內(nèi)動態(tài)邏輯分區(qū)過程如下:
步驟1) 在形成簇首CH過程中, 簇首CH的群內(nèi)成員表具有每個成員的ID號, 簇首CH向每個成員點名, 收到的成員進行回復, 簇首可測算出每條魚的響應時間T(CH,j);
步驟2) 簇首CH根據(jù)響應時間T(CH,j)大小, 將簇內(nèi)成員進行邏輯分區(qū), 分為監(jiān)測區(qū)MA、 保障區(qū)GA和偵察區(qū)RA, 并廣播分區(qū)信息, 收到信息后的簇內(nèi)成員Vj根據(jù)該信息修改區(qū)號標識Tagj.
2.2.3 零散簇間整編 在分簇過程中, 簇的數(shù)量區(qū)域為[cl,cu], 首次分簇后會留下數(shù)量小于cl的魚群Ci. 為進一步優(yōu)化控制體系, 結(jié)合最小響應時間對零散魚群進行整編, 優(yōu)化網(wǎng)絡(luò)控制體系的同時提高了組網(wǎng)的靈活性.
零散簇間整編過程如下:
步驟1) 魚群Ci通過偵察區(qū)向周圍廣播申請加入信息MsgC, MsgC中包含群內(nèi)節(jié)點數(shù)量;
步驟2) 附近偵察區(qū)的機器魚收到并發(fā)現(xiàn)不同于自身網(wǎng)絡(luò)號的MsgC信息時, 將請求發(fā)送給簇首, 簇首判斷MsgC中Ci內(nèi)的節(jié)點數(shù)量小于等于cl, 則批準加入;
步驟3) 魚群Ci收到多個反饋信息時, 選擇響應時間最短的魚群加入;
步驟4) 如果無法聯(lián)系到其他魚群, 則將成為孤立魚群, 自主向目標節(jié)點行進.
2.2.4 中心簇選舉 該過程用于尋找群中簇連接度最大的簇, 作為群體控制中心.
中心簇選舉過程如下:
步驟1) 每個簇通過交互信息獲得鄰居簇的數(shù)目, 得到自己的簇連接度;
步驟2) 每個簇將自己的簇連接度向鄰居簇廣播;
步驟3) 具有簇連接度最大的簇被選為中心簇CRA;
步驟4) 中心簇CRA的一跳鄰居簇成為中心簇所組織的成員;
步驟5) 重復上述過程直到所有的簇加入.
用MATLAB軟件對分簇過程進行仿真, 結(jié)果如圖3所示, 其中: 藍色圓點表示初始節(jié)點; 黑色圓點表示簇內(nèi)普通成員; 紅色節(jié)點表示簇首(CH); 藍色星形表示監(jiān)測區(qū)(MA)成員; 黑色圓圈表示保障區(qū)(GA)成員; 藍色三角形表示偵查區(qū)(RA)成員. 圖3(A)為模擬魚群入水后的初始隨機分布位置; 圖3(B)表示快速分簇結(jié)果; 圖3(C)表示簇內(nèi)分區(qū)過程: 簇首基于成員節(jié)點響應時間, 將整個簇劃分為監(jiān)測區(qū)、 保障區(qū)和偵察區(qū); 圖3(D)表示簇間整編過程.
圖3 簇的形成與整編Fig.3 Formation and integration of clusters
圖4為中心簇選舉過程示意圖, 其中中心簇首CRA所在簇為中心簇, 每個簇與自己的鄰居簇交換簇連接度信息, 簇連接度最大的簇當選為中心簇. 中心簇一跳范圍內(nèi)的簇加入該群, 其他簇通過偵察區(qū)找到自己的上級簇, 最終整個魚群建立聯(lián)系.
為驗證本文算法在延長網(wǎng)絡(luò)能量消耗、 網(wǎng)絡(luò)生命周期和能量均衡性方面的特性, 選取LEACH算法[14]和LEACH-C算法[17]進行對比實驗. 使用MATLAB進行仿真分析, 在300 m×300 m內(nèi), 隨機模擬400個節(jié)點, 每個節(jié)點的初始能量為0.5 J, 簇數(shù)量上限為20, 下限為5, 共進行1 800輪實驗, 節(jié)點每次發(fā)送4 000 bit的數(shù)據(jù).
3.2.1 網(wǎng)絡(luò)能量消耗 下面用Efs表示自由空間能量,Emp表示衰減空間能量,do表示通信半徑,Ei表示節(jié)點i的當前能量,ETX表示發(fā)射單位報文損耗能量,k表示數(shù)據(jù)包大小, disij表示節(jié)點i和節(jié)點j之間的距離,ERX表示接收單位報文損耗的能量,EDA表示多路徑衰減能量. 則通信半徑為
(3)
發(fā)送數(shù)據(jù)為
(4)
接收數(shù)據(jù)為
Ei=Ei-(ERX+EDA)×k.
(5)
圖4 中心簇選舉過程示意圖Fig.4 Schematic diagram of election process of central cluster
圖5為3種算法網(wǎng)絡(luò)總能量隨運行周期(輪數(shù))的變化曲線. 由圖5可見, LEACH和LEACH-C算法隨著輪數(shù)的增加, 能量下降趨勢明顯快于本文算法, 在約800輪時所有的節(jié)點能量為0, 而本文算法采用能量均衡措施, 能量下降趨勢更平緩, 約運行1 000輪時能量為0. 圖6為不同算法發(fā)送給簇首的報文總數(shù). 由圖6可見, 本文算法在初期階段發(fā)送給簇首的報文相對較多, 這主要是由于中心簇形成過程相對復雜, 維護報文較多; 隨著輪數(shù)的增加, 報文數(shù)量相對變少, 最終達到的峰值明顯低于其他兩種對比算法, 從而減少了網(wǎng)絡(luò)總體能耗.
圖5 不同算法的總能量變化曲線Fig.5 Total energy change curves of different algorithms
圖6 不同算法發(fā)送給簇首的報文總數(shù)Fig.6 Total number of messages send to cluster head of different algorithms
3.2.2 網(wǎng)絡(luò)生命周期 網(wǎng)絡(luò)生命周期[23]能反應執(zhí)行算法過程的節(jié)點運行時間, 是評價網(wǎng)絡(luò)性能的一個重要指標, 而負載均衡有助于延長網(wǎng)絡(luò)生命周期. 節(jié)點的初始化能量為
(6)
圖7為3種算法的死亡節(jié)點數(shù)量隨運行周期的變化曲線. 由圖7可見, LEACH和LEACH-C算法隨著程序的運行死亡節(jié)點的增幅明顯高于本文算法. 本文設(shè)網(wǎng)絡(luò)生命周期為所有節(jié)點失效的時間, 不同算法網(wǎng)絡(luò)生命周期的對比結(jié)果如圖8所示. 由圖8可見, LEACH和LEACH-C算法的生命周期均約為800輪, 而本文算法的生命周期約為1 000輪. 其他兩種算法均在100輪前出現(xiàn)首個失效節(jié)點, 而本文算法的首個失效節(jié)點出現(xiàn)在500輪后, 相比其他兩種算法延遲很多, 表明本文算法群體能耗更少, 工作時間更長, 能有效提高群體協(xié)同續(xù)航能力.
圖7 不同算法死亡節(jié)點數(shù)隨運行周期的變化曲線Fig.7 Curves of number of dead nodes of different algorithms with running cycle
圖8 不同算法的節(jié)點死亡周期Fig.8 Node death cycle of different algorithms
3.2.3 能量均衡性 本文將網(wǎng)絡(luò)的平均能量和能量方差相結(jié)合對網(wǎng)絡(luò)的能量均衡性進行評價. 能量均值函數(shù)為
(7)
能量方差函數(shù)為
(8)
其中Ei(o)為節(jié)點i的能量.ME(o)越大,DE(o)越小, 表明該時刻網(wǎng)絡(luò)的能量均衡性越好. 網(wǎng)絡(luò)能量的均衡性是對網(wǎng)絡(luò)負載的分配情況, 均衡效果越好, 越有利于實現(xiàn)最大輸出.
圖9為不同算法網(wǎng)絡(luò)均值能量隨運行周期的變化曲線; 圖10為不同算法網(wǎng)絡(luò)能量方差隨運行周期的變化曲線. 在某輪中, 均值能量越大、 方差越小, 表明該輪網(wǎng)絡(luò)能量的均衡性越好. 由圖9可見, 隨著輪數(shù)的變化, 本文算法的能量均值始終高于LELACH和LEACH-C算法. 由圖10可見: LEACH和LEACH-C算法能量方差開始階段變化較大, LEACH算法約在60輪到達最高點, LEACH-C算法約在230輪到達最高點, 這兩種算法在800輪后能量降為0, 總體上能量方差變化幅度較大; 本文算法開始階段增幅平緩, 約630輪達到最高點, 1 000輪后降為0, 總體上能量方差變化幅度更小, 表明本文算法具有良好的能量均衡性.
圖9 不同算法網(wǎng)絡(luò)均值能量隨運行周期的變化曲線Fig.9 Curves of network mean energy of different algorithms with running cycle
圖10 不同算法網(wǎng)絡(luò)能量方差隨運行周期的變化曲線Fig.10 Curves of network energy variance of different algorithms with running cycle
綜上所述, 為降低節(jié)點間負載不均衡性所導致的能量損耗, 提升仿箱鲀魚群的協(xié)同續(xù)航能力, 本文設(shè)計了一種基于邏輯分區(qū)的仿箱鲀魚群負載均衡分簇控制算法. 該算法采用分簇方式, 減少了節(jié)點間的維護報文數(shù)量, 降低了系統(tǒng)整體開銷; 基于簇內(nèi)邏輯分區(qū)策略, 實現(xiàn)監(jiān)測、 保障和偵察多區(qū)域協(xié)同控制, 并結(jié)合最小響應時間整編零散魚群, 優(yōu)化網(wǎng)絡(luò)控制體系的同時提高了組網(wǎng)靈活性; 在維護過程中采用區(qū)域節(jié)點角色轉(zhuǎn)換機制實現(xiàn)網(wǎng)絡(luò)負載均衡. 仿真實驗驗證了算法的有效性及可行性.