基于生物地理學優化的分簇算法

黨夢麗，張書奎

(蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006)

0 引 言

隨著5G移動通信技術、軟件定義網絡、移動邊緣計算等新興技術的發展和深入研究，當今生活中，大多數應用都需要傳感設備從環境中收集數據，這使得移動傳感器網絡(mobile sensor networks，MSNs)的應用提升到一個新的高度[1-4]。傳感器被嵌入到各種設備和物體中，如手機、手環、衣物[5]、自行車、汽車等，用于收集應用所需的有關信息。MWSN在自動駕駛、水下導航、健康檢測、疫情追蹤與防控等應用中起著重要作用。但各種各樣的用戶設備會產生大量高可變的數據[6]。同時，節點故障和移動等因素會使網絡拓撲發生改變，如何有效組織網絡中傳感器節點間的通信，在保證數據傳輸穩定性的同時延長網絡生命周期是MSNs的關鍵問題。

負載均衡技術可以通過均衡節點間的能量消耗，以避免節點過早死亡，從而達到延長網絡生命周期的作用。考慮到網絡中設備的多樣性，文獻[7]提出了SEP算法，該算法引入了異構網絡的思想，根據節點的初始能量不同劃分節點類型，該方法有效延長了網絡的穩定周期。隨著群體智能優化算法的發展，近年來有研究學者利用群智能優化算法來解決簇頭選擇問題。比如PSO[5,8,13]、生物地理學算法(BBO)[9,10,12]、GA[11]等通過對網絡中的多個指標的綜合優化，提高簇結構的合理性，達到均衡節點能量消耗和延長網絡生命周期的目的。為更好優化簇結構，文獻[12]提出了一個基于K-means和BBO的異構無線傳感器網絡下的混合分簇算法，為獲得具有較高質量的棲息地，將K-means用于BBO種群初始化階段，然后利用BBO進行分簇，該方法減少了節點能量消耗。Morteza等[13]提出了一個混合PSO與和聲搜索算法(HAS)的能量高效分簇路由算法，其在提升網絡覆蓋、數據包傳輸和延長網絡生命周期方面表現出良好性能。

基于以上分析，本文提出基于BBO來優化MSN分簇的集中式分簇算法。該算法通過選擇具有較好特性的節點初始棲息地，提高算法的收斂速度。并采用余弦遷移模型來進一步提升算法的探索效率。最后，通過重新定義目標函數，來優化簇結構。其有效減少節點能量消耗，平衡了網絡負載，從而延長了網絡生命周期。

1 系統模型

1.1 網絡模型

假設網絡中有N個節點隨機分布在檢測區域內，基站位于區域中心。如圖1所示，節點之間動態成簇，簇內和簇間以單跳方式通信。同時，本文基于3層異構網絡，網絡中的節點根據初始能量不同，分為3類節點，即普通節點、中級節點和高級節點。

圖1 不同時刻網絡動態聚簇

1.2 能量模型

本文采用與文獻[7,9]相同的能量消耗模型，對于相距為d的兩節點間傳輸L比特數據，發送端的能量消耗見式(1)

(1)

其中，Eelec為射頻能耗系數，表示每發送或接收1比特數據所消耗的能量，εfs、εmp分別為自由空間傳播模型和多路衰減模型中放大功率所需要的能量，d0為自由空間模型和多路徑衰減模型的臨界距離，即

(2)

相應地，傳感器節點接收同樣大小的數據包需要消耗的能量由式(3)所示

Erx=k*Eelec

(3)

2 基于BBO算法求解MWSN分簇問題

在應用BBO算法求解MSN分簇問題的過程中，由基站通過CABBO算法以集中的方式控制選擇簇頭節點。該協議主要分為3個階段，如圖2所示，在信息收集階段，基站發送信息請求數據包，網絡中的所有節點把自身到基站的距離、剩余能量和鄰居節點個數信息發送到基站；然后，基站計算網絡當前平均剩余能量、平均鄰居個數、節點到基站的最大距離；在簇建立階段，基站執行CABBO算法，將相關參數輸入到算法中，獲取最優簇頭集并廣播簇頭信息。節點根據簇頭狀態信息確定自己的角色，普通節點發送請求信息，選擇最近簇頭。簇形成后進入數據傳輸階段，簇成員節點發送數據信息到簇頭，簇頭節點將數據匯聚后發送到基站。

圖2 本協議整體流程

2.1 BBO算法

Dan Simon[14]受生物地理學啟發提出了生物地理學優化算法(biogeography-based optimization，BBO)，該模型根據現實世界中物種的產生與滅絕，以及在棲息地間的遷移，最終達到平衡狀態的自然規律，所形成的一種新型的智能優化算法。其中，BBO算法包含初始化、遷移和突變3個步驟。

(1)初始化：首先，將問題的每個解集看作“棲息地”(Habitat)，隨機生成N個棲息地，1個棲息地供一個種群生存，每個棲息地包含D維解向量(suitability index variable，SIV)。

(2)遷移：為避免算法陷于局部最優，通過遷移操作實現棲息地間的信息交換，增大BBO算法的尋優范圍，從而改變現有解決方案。遷移算子則是根據遷入率λ和遷出率μ隨機選擇遷移解決方案，從選定的棲息地解決方案中替換需要遷出的物種。其遷移模型為線性遷移模型，如下所示

(4)

(5)

其中，I為最大遷入率，E為最大遷出率，S代表棲息地當前物種數量，Smax代表最大物種數量。

(3)變異：變異算子通過產生的隨機值來探索比當前更好的解決方案。通過突變，可能會使其變為更好的方案。棲息地的突變概率用Ms表示，定義如下

(6)

其中，Mmax為最大突變率，Ps表示棲息地容納物種數量為S時的概率，即對于給定問題預先存在的可能性Pmax為棲息地容納最大物種數量的概率。

2.2 CABBO算法

為提高BBO在分簇算法中的適應性，以及算法的收斂速度和性能。本部分主要并從以下3個方面提高改進BBO算法在MSN分簇方面的適應性。

(1)針對基于BBO的分簇算法初始化棲息地種群，存在的探索效率低問題，本文通過考慮節點剩余能量、鄰節點個數、與基站距離等因素，選擇具有較好特性的節點來提高初始棲息地的質量，以提高算法的探索效率和收斂速度。

(2)為保證網絡的有效連接，適應網絡的動態變化，通過權衡節點能量消耗與負載均衡，綜合考慮簇緊湊度、簇頭分離程度、節點能量消耗和能量均衡因子，重新定義目標函數，以優化簇結構和網絡拓撲，使簇頭分布更加合理。

(3)在遷移階段，我們引入余弦遷移模型來進一步提升算法的探索效率。

2.2.1 簇頭概率函數

簇頭節點承擔著數據匯聚與傳輸工作，為提高網絡動態連接的穩定性，需要選擇具有較好特性的節點來充當簇頭。簇頭節點需要消耗較多能量，因此，能量因素起著重要作用，通過提高剩余能量高的節點成為簇頭的概率，可以增強簇結構的穩定性。同時，節點的鄰居節點個數(節點度)是評定節點匯聚和轉發能力的有效指標，而節點與基站的距離則影響著數據傳輸的成本。因此，通過綜合這3個因素來確定節點成為簇頭的概率，用psi表示節點si成為簇頭的可能性，定義如下

(7)

其中，p為初始設定的節點成為簇頭的概率，Esi、Nsi、Dsi分別為節點si的當前剩余能量、鄰居個數、到基站的距離；Eave、Nave、MaxD分別為網絡當前平均剩余能量、平均鄰居個數、節點到基站的最大距離。α1、α2、α3為權重因子，α1+α2+α3=1。 通過實驗仿真，當α1=0.5、α2=0.25、α3=0.25時，選出的候選節點具有較好的特性。

2.2.2 目標函數

為使得優化后的網絡拓撲可以提高節點能量利用率與數據傳輸率，保證簇結構的合理性。本文綜合考慮簇緊湊度Comp、 簇分離程度Sep、 總能量消耗和能量均衡因素來定義目標函數。簇緊密度反映了簇內距離，即簇內成員節點到簇頭節點的距離

(8)

其中，CHs表示簇個數，sj表示在第i個簇Ci中的第i個成員節點，CHi表示第i個簇Ci的簇頭節點。簇分離程度則反映了簇頭之間的距離，其定義如下

(9)

其中，CHi、CHj分別表示簇Ci、Cj的簇頭節點。總能量消耗反映了簇頭節點的總能量消耗和非簇頭節點的總能量消耗。其中，簇頭節點能量消耗包含接收來自簇成員節點數據的能量消耗，融合數據的能量消耗，以及將數據傳輸到基站的能量消耗。非簇頭節點的能量消耗包含將數據發送到簇頭的能量消耗

TotalE=Energynon-CHs+EnergyCHs

(10)

另外，保持節點間的能量均衡也是設計路由協議需要考慮的關鍵因素，它直接影響網路的有效工作時間。因此，在目標函數中加入能量平衡因子，可以有效評估棲息地的適宜值，使劃分的簇更加合理，其定義如下

(11)

其中，Eave為網絡當前平均剩余能量，Nalive為網絡當前存活節點個數，Esi為節點si當前的剩余能量。目標函數定義如下

F=β1*Comp/Sep+β2*TotalE+β3*EB

(12)

其中，β1、β2、β3為權重因子，β1+β2+β3=1。 通過仿真實驗和觀察，當β1=0.3、β2=0.3、β3=0.4時，所提出算法具有更好的性能。最小化Comp可以減小簇內通信能耗，最大化Sep可以使簇頭分布更加均勻，進一步減少通信能耗；同時，EB值越小則節點負載越均衡。因此，目標函數的值越小，分簇方案越好。選擇目標函數的倒數作為棲息地的適應度函數，BBO算法通過該適應度函數評估每個棲息地的適宜性指數HSI，根據HSI保留最佳的解決方案。

2.2.3 遷移模型

BBO算法根據線性遷移模型計算遷入率和遷出率，通過將較優解中的元素替換較差解中的元素，以實現解決方案的探索。但線性遷移模型過于簡單，存在適應性不足、探索效率低的問題，有關學者根據現實世界中種群的分布情況，提出了不同的遷移模型改進算法，比如二次遷移模型、余弦遷移模型、指數遷移模型等。其中余弦遷移模型更接近自然規律，可以有效提高BBO算法的優化性能[15]。因此，本文采用該遷移模型，遷入率λ和遷出率μ的計算分別如下所示

(13)

(14)

對于每一個解決方案Hi， 在遷移過程中，根據式(13)、式(14)分別計算其節點si的遷入率λi和遷出率μi， 根據λi確定是否進行遷入操作棲息地遷移過程中，若發生遷入，則根據輪盤賭法選擇遷出的位和棲息地Hj， 在Hi要遷入的位用Hj的相應位進行替換。

2.3 基于CABBO的分簇算法

2.3.1 算法流程

(1)編碼與種群初始化

BBO遷移策略類似于GA和進化策略的全局重組方法，但又有所不同。在進化方法中通過重組多個父代以形成一個后代，全局重組用于創造新的解，而BBO遷移用于改變現有解，其遷移過程如圖3所示。進化策略中的全局重組是一個再生的過程，而BBO中的遷移是一個適應性的過程，它用來改變已存在的棲息地。

圖3 棲息地的遷移過程

在初始化階段，一個棲息地代表分簇問題的一個解決方案，其由一組傳感器節點組成，包括簇頭節點、普通節點和死亡節點。也就是說，一個棲息地的大小等于網絡中節點個數。對每個棲息地的解向量進行二進制編碼，我們用0代表普通節點，用1表示簇頭節點，而死亡節點則用-1表示。圖3舉例展示了棲息地種群初始化情況，在圖4中考慮了11個節點，其中節點1，3，7，8，10為簇頭節點，其它節點為普通節點。

圖4 種群初始化示例

為提高解決方案的質量，同時增強算法的探索能力，通過選擇具有較好特性的節點來初始化棲息地編碼。根據式(7)計算節點si成為簇頭的概率pi。 如果節點si的狀態不是-1，則隨機產生一個 (0,1) 間的值randi。 若其小于pi， 則該節點初始狀態為1，否則初始化為0。棲息地種群具體初始化過程如算法1所示。

算法1：基于BBO的棲息地種群初始化

(1)輸出：M×N的矩陣(M為解決方案個數，N為節點總數)

(2) For each solution in population do

(3) For each feature in solution do

(4) %根據式(7)計算每個節點的pi

(5) Ifrandi

(6) feature=1;

(7) Else

(8) feature=0;

(9) end if

(10) end for

(11) end for

(2)遷移操作

對于每一個解決方案Hi， 在遷移過程中，根據式(13)、式(14)分別計算其節點si的遷入率λi和遷出率μi， 根據λi確定是否進行遷入操作，若發生遷入，則根據輪盤賭法選擇遷出的位和棲息地Hj， 在Hi要遷入的位用Hj的相應位進行替換。

(3)突變操作

通過突變來提升解決方案(棲息地)的多樣性，以求得比目前更好的解決方案。該過程與遷移操作相似，對于每一個解決方案Hi中的節點si， 通過生成一個隨機數r∈(0,1)， 如果r的值小于最大突變概率，則執行突變。然后在棲息地中選擇隨機位置并改變其值，即如果所選位置的值為0，則將其替換為1，如果為1，則將其替換為0。

2.3.2 基于CABBO的分簇算法流程圖

在CABBO求解分簇問題的過程中，棲息地表示可行解，每個棲息地通過最大化其的適應度值，以得到合理的分簇方案。其中，適應度值為目標函數的倒數，目標函數值由式(12)進行計算，CABBO算法的具體流程如圖5所示。

圖5 CABBO算法流程

3 實驗仿真

3.1 參數設置

我們利用Matlab2016進行實驗仿真，仿真計算機配置為2.9 GHz Intel Core i5，8 GB內存，64位Windows 10。仿真區域設定為100×100平方米的正方形區域，基站位于區域中心，傳感器節點被隨機、均勻地分布在目標區域內。我們考慮了網絡的異構性，根據初始能量分為兩種類型節點，分別為高級節點和普通節點。其中，普通節點的初始能量為0.5 J，高級節點的初始能量為1 J，具體的實驗參數見表1。

表1 仿真參數設置

3.2 仿真結果分析

本文將CABBO算法與SEP算法[8]、BEECP[11]以及EEWC[11]進行比較，并從5個方面進行分析，以驗證所提出算法的有效性。

不同算法的死亡節點變化情況如圖6所示，可以看到CABBO算法推遲了第一個節點死亡時間。表2列舉了不同算法下死亡節點對應的輪數信息。CABBO算法在第1398輪出現第一個死亡節點，當網絡出現10%的死亡節點，所提出算法發生在第1591輪，SEP、BEECP和EEWC分別發生在第1162輪、第1193輪和1261輪。CABBO在第2475輪網絡所提出算法有90%的節點死亡，相對于其它算法，其有效地推遲了節點死亡時間。

圖6 每輪死亡節點個數

表2 對比死亡節點

從圖7我們可以更加直觀地觀察到不同算法下節點死亡時間的變化幅度。可以看到CABBO算法在推遲50%～70%節點死亡時間上效果顯著。同時，表3展示了相對于其它3個算法，CABBO算法在網絡穩定周期和生命周期方面的性能提升率。與SEP、BEECP和EEWC相比，CABBO在穩定周期方面分別提升了50.48%、25.38%和21.24%，在90%節點死亡時間上分別推遲了69.86%、26.08%和12.14%。

圖7 死亡時間統計

表3 對比穩定周期和網絡生命周期

該結果也表明所提出算法在提升網絡穩定周期和生命周期方面表現優異。這是因為CABBO算法考慮了節點剩余能量、鄰居節點個數以及到基站距離對成簇的影響，優化簇頭選擇，降低了能量較小的節點成為簇頭的可能性，增強了網絡的連通性。同時，通過考慮了利用適應值函數評估分簇方案，使得簇頭在網絡中的分布更加合理，從而減緩了節點死亡時間。

網絡剩余能量是分析協議好壞的重要性能指標之一[15]。從圖8中我們可以看到，所提出算法的曲線相對平滑，這意味著節點之間的負載更加均衡。同時，通過表4我們可以更加清晰地觀察到，4個算法的網絡剩余能量隨時間變化情況。在第一輪后，SEP、BEECP、EEWC、CABBO算法中網絡總剩余能量均為54.96 J，200輪后，4個算法網絡剩余總能量為46.59 J，47.74 J，48.27 J和49.78 J。可以看到CABBO算法的總剩余能量高于其它算法。這是因為LEACH和SEP是通過閾值公式隨機選擇簇頭節點，簇結構不合理使節點能量消耗過大。BEECP算法在選擇簇頭時考慮了簇內緊湊度和簇分離程度，有效降低了節點傳輸數據的能量消耗，從而減少了網絡能量消耗。EEWC算法不僅考慮了這兩個因素，同時考慮了簇頭數目對分簇的影響，進一步減少了節點能量消耗。而本文提出的CABBO算法在選擇簇頭時考慮了節點剩余能量、節點鄰居個數以及到基站的距離。同時，通過加入能量均衡因子，使節點負載更加均衡，提高了網絡能量利用率。

圖8 網絡剩余能量

圖9展示了4個算法下的網絡吞吐量，即節點發送到基站的總包數。因為CABBO算法有效延長了網絡的生命周

表4 對比剩余能量

圖9 吞吐量對比

期，通過考慮節點能量、鄰居節點個數因素，增強了網絡的連通性和匯聚能力，從而極大提高了網絡吞吐量，這意味著網絡具有更好的性能。

圖10展示了不同算法的簇頭變化情況，其中，基于BBO的BEECP算法的簇頭數目變化幅度較大，而所提出算法可以保證每輪簇頭數目在一個小范圍內浮動，呈現出一種較為平穩的狀態。有效解決了基于BBO的分簇算法中簇頭數目變化較大的問題，穩定的簇頭數目使得區域內簇的規模相對均勻穩定，提高了網絡的穩定性。

圖10 每輪簇頭個數

4 結束語

本文提出了一個基于BBO優化的MSN分簇算法，首先，從優化初始化棲息地質量的角度進行考慮，選擇具有較好特性的節點生成分簇初始解。同時，采用余弦遷移模型改進傳統BBO算法，有效提高算法的探索能力和收斂速度。再者，通過定義新的適應度函數，CABBO算法形成的簇結構可以使網絡負載更加均衡。與SEP、BEECP和EEWC算法相比，CABBO算法在一定程度上提高了網絡生命周期和吞吐量。同時，CABBO算法提高了BBO在分簇算法中的適應性，有效解決了簇頭數目變化幅度較大的問題，增強了網絡的穩定性。