WSN中基于改進樽海鞘群算法的分簇路由協議

顏 清，劉 瑛，王國仕，張應斌

(1.海南電網有限責任公司 信息通信分公司，海口 570000；2.海南電網有限責任公司，海口 570000)

0 引言

隨著智能化時代的到來，無線傳感器網絡(WSN，wireless sensor network)在越來越多的領域得到應用，例如無人駕駛、醫療領域、軍事戰場、智能倉儲、環境監測等[1]。WSN包含成百上千個傳感器節點，它們分布在指定區域中感知、評估和接受數據。這些傳感器節點價格低廉，在感知、處理和傳輸數據信息方面具有較高的能力。傳感器使用模擬數字轉換器收集數據，并對數據進行處理，然后傳輸至基站。基站會對收集到的數據進行分析，為各種應用做出相應的決定。然而，WSN中傳感器節點的能量有限且無法進行能量補充，因此提高能量利用率，延長網絡生存期是WSN中亟待解決的問題[2-3]。在現有的路由協議中，基于分簇的層次路由被證明是平衡網絡負載、延長網絡生存期的有效技術[4-5]。層次路由通過將傳感器節點分組，有效減少網絡能量的消耗，提高網絡的可擴展性，從而實現更長的網絡壽命，提高WSN的性能。網絡中的每個簇都有一個簇首，負責與網絡中的其他簇通信。由于直接將傳感數據傳輸到基站需要消耗較高的能量，因此在基于簇的WSN中使用路由協議來確定簇首與基站之間的最佳傳輸路線以減少能量消耗。路由協議的特點包括容錯性、可靠性、信息積累、可擴展性等[6]。

經典的分簇路由協議LEACH[7]將網絡節點進行分簇，并周期性輪換簇首，從而均衡網絡能耗，延長網絡生存期。但LEACH協議在選舉簇首時沒有考慮節點的剩余能量和位置信息，每個節點以相同的概率當選簇首。若剩余能量不足、地理位置不合理的節點當選簇首，將加速這部分節點的能量耗損，縮短網絡生存期。此外，簇間通信階段沒有使用任何路由算法，降低了網絡性能。為解決LEACH協議中存在的問題，研究人員采用群體智能算法解決最優簇首選舉問題，并獲得了理想的結果。文獻[8]提出一種基于改進人工蜂群算法的分簇路由協議。首先對人工蜂群算法進行改進，提高了其全局搜索能力。然后使用改進的人工蜂群算法選擇最優簇首，改善簇首質量。簇間通信階段，構建了基于蟻群優化的路由算法，均衡了簇首節點的網絡負載。文獻[9]使用由遺傳算法優化的K-Medoids聚類對網絡節點分簇，并考慮節點的能量因素和地理位置選擇最優簇首。仿真結果表明，所提協議有效延長了網絡生存期。但該協議沒有使用任何簇間路由，距離基站較遠的簇首將產生大量的能耗而過早死亡。文獻[10]首先使用粒子群算法優化模糊C均值聚類，以改善聚類效果。其次，使用改進的聚類算法對傳感器網絡分區，形成網絡分簇。在每個簇內，考慮節點的剩余能量和位置因素動態更新簇首。數據傳輸階段，提出一種基于貓群優化算法的路由技術，為簇首構建最優傳輸路徑。對所提協議進行仿真，實驗結果表明該協議優于LEACH協議和改進的LEACH協議。但所提協議在簇內通信階段采用TDMA機制，容易導致時隙浪費，降低能量效率。文獻[11]采用灰狼優化算法選擇最優簇首集合，有效提高了網絡了效率，延長了網絡生存周期。但所提協議沒有采用任何路由算法，簇首節點直接向基站發送數據將會產生大量的能量開銷，使其過早死亡。文獻[12]使用人工蜂群算法設計高效的分簇路由協議。在成簇階段，首先考慮傳感器節點當前剩余的能量、所處地理位置、成簇緊湊程度3種因素設計適應度函數，然后使用人工蜂群算法求解適應度函數，從而選出最優簇首集合。在穩定傳輸階段，為降低節點的能量消耗，構建了基于轉發代價的路由算法，確定節點到基站之間的傳輸路線，簇頭按照規劃好的路線以多跳方式將數據傳送至基站。仿真實驗證明，所提路由協議能夠延長WSN的網絡壽命，提高網絡吞吐量。但基本人工蜂群算法易陷入局部最優，可能導致選出的簇首集合并非最優解，從而降低WSN性能。

針對上述協議數據傳輸過程中節點能量消耗大、對基站傳輸的總數據包數量小等問題，本文提出一種基于聚類的WSN節能路由協議。由于群體智能優化算法的搜索能力強、魯棒性和較好的自適應性，本研究中主要使用群體智能優化算法解決最優聚類問題。首先對基本樽海鞘群算法進行改進，提出一種精英反向學習樽海鞘群算法，提高算法的全局搜索能力；其次根據節點的剩余能量和地理位置設計高效的適應度函數，并使用改進的樽海鞘群算法優化節點適應度函數，選出最優簇首集合。簇內通信階段，設計一種基于最小生成樹的路由算法，為簇首節點構建最優傳輸路徑，在緩解簇首負載的同時最小化中繼節點的能量消耗。最后，使用輪詢控制機制為簇內成員節點構建數據傳輸調度，避免時隙浪費，進一步提高能量效率。

1 系統模型

1.1 網絡模型

為方便后續工作的進行，本文考慮以下要素構建WSN模型[13]：

1)傳感器節點具備全網唯一的ID號碼，且隨機分布在目標監測區域內。部署完成后節點的位置不再變動。

2)在WSN中，所有傳感器節點同構。即所有傳感器節點的初始能量和數據處理能力均相同。

3)傳感器節點之間的距離根據歐氏距離公式進行計算。

4)基站接收關于傳感器節點的剩余能量和距離信息。根據這些信息，通過使用既定的簇首選擇算法為節點選擇相應的簇首。路由算法則被用于規劃簇首到基站之間的傳輸路徑。

1.2 能耗模型

本文采用一階無線電能耗模型來計算發射機和接受機的能量損耗[14]。WSN的能耗主要來自于傳感器節點收發數據信息，節點發送kbit數據到距離自身為d的接收端所消耗的能量為：

(1)

ERx(m，d)=kEelec

(2)

ERx(k，d)=kEda

(3)

其中：Eda為節點融合每bit數據所需要的能量。

2 精英反向學習樽海鞘群算法

2.1 基本樽海鞘群算法

樽海鞘群算法(SSA，salp swarm algorithm)是Mirjalili等人受海洋生物樽海鞘的覓食和導航行為啟發所提出的新型群體智能算法[15]。該算法具有控制參數少、易于實現、優化能力強等特點，已被成功應用于求解多個學科領域的優化問題[16]。

SSA中，位于樽海鞘鏈最前面的個體被定義為領導者，其余個體為跟隨者。領導者的位置更新公式為：

(4)

其中：Fj為食物源在第j維搜索空間的位置；c2和c3為隨機值，取值[0，1]之間；c1是控制領導者移動的重要參數，按照下式進行計算：

c1=2e-(4t/T)2

(5)

其中：t為當前迭代次數，T為最大迭代次數。

跟隨者的位置更新方程為：

(6)

2.2 精英反向學習樽海鞘群算法

基本SSA算法具有較好的性能，能夠有效解決全局優化問題。然而，基本SSA算法與其他群體智能算法類似，在搜索過程中存在全局勘探與局部開發不平衡、易收斂至局部最優的缺陷[17-18]。為解決基本SSA中存在的缺陷，本文提出一種精英反向學習的樽海鞘群算法(OSSA，opposition-based)。

2.2.1 反向學習

(7)

其中：aj和bj分別為搜索空間的上下限。

2.2.2 動態學習策略

基本SSA中，跟隨者根據式(6)更新自身位置，該位置更新機制較為單一，缺少參數控制其移動方向和移動速度[16]。為解決這一問題，將領導者位置更新公式中的參數c1引入跟隨者位置更新公式中，幫助控制跟隨者的位置更新。改進的跟隨者位置更新公式為：

(8)

根據式(8)可知，引入控制參數c1能夠幫助跟隨者實現有效跟隨，幫助算法在全局搜索和局部勘探之間獲得穩定的平衡，從而改進了基本SSA的整體性能。

2.3 OSSA算法步驟

所提OSSA算法步驟如下：

Step 1：設置算法參數：種群規模N、最大評估次數T、搜索空間上下限[ub，lb]；

Step 2：隨機初始化種群，根據個體適應值將其分為領導者和跟隨者；

Step 3：根據式(4)更新領導者位置，并執行OOBL，生成反向個體。根據適應值選擇較優個體進入后續迭代。

復方阿膠漿生產原料包括紅參、黨參、熟地黃和山楂等，經過水提取后的藥渣中除了含有較多的粗纖維外，還包括復雜多樣的蛋白質、氨基酸、微量元素及殘留的活性成分等多種物質。

Step 4：根據式(8)更新跟隨者位置；

Step 5：評價種群適應值，將最優個體指定為當前食物源；

Step 6：判斷是否達到最大評估次數，若達到，輸出食物源位置，否則返回Step 3繼續迭代。

3 基于OSSA的分簇路由協議

本節對所提出的基于OSSA的分簇路由協議進行詳細介紹。網絡運行初期，首先采用OSSA算法選擇最優簇首集合，成員節點選擇距離最近的簇首入簇，至此成簇階段結束。數據傳輸階段，構造最小生成樹，為簇首節點尋找中繼，簇首沿最優傳輸路徑以多跳方式將數據分簇發往基站。簇內通信階段，采用輪詢控制機制幫助成員節點完成數據傳輸。

3.1 成簇階段

成簇階段，使用OSSA算法選擇最優簇首集合，普通成員就近入簇，形成網絡分簇。簇首選舉時，OSSA中的每個個體代表一種聚類結果，個體適應值反映當前聚類效果，最終輸出的食物源即為最優聚類。在進化過程中，OSSA迭代的準則為最優化適應度函數。因此，設計高效的適應度函數對于選擇最優簇首具有重要意義。本文綜合考慮節點的能量因素和地理位置，設計了新穎的適應度函數，用于評價OSSA生成的解的質量。

3.1.1 能量因子

在WSN中，簇首執行多項任務，包括收集普通節點的數據、與基站通信等。簇首需要較高的能量來完成這些任務，因此，需要選擇剩余能量充足的節點擔任簇首，以此延長網絡生存期。本文將能量因子定義為當前簇首集合的總能量與網絡總能量的比值，按照下式進行計算：

(9)

其中：k和n分別表示簇首數量和網絡節點總數；Ech(i)和Ecm(j)分別表示簇首i和成員j的剩余能量。由能量因子表達式可以看出，當前簇首節點集合剩余總能量越多，f1越大，代表當前簇首集越優。

3.1.2 位置因子

選取簇首時，分散簇首在網絡中的位置能夠幫助網絡分簇更加均勻，從而均衡簇間負載。本文將簇首的位置因子定義為基站到網絡中心的距離與簇首到基站平均距離的比值，按照下式進行計算：

(10)

其中：d(center，BS)和d(CHi，BS)分別為基站到網絡中心的距離和簇首到基站的平均距離。由位置因子表達式可以看出，簇首集合到基站的平均距離越短，簇首的通信距離也越短，此時f2較大，代表當前簇首集越優。

適應度函數值是評價當前簇首集合質量的基準，本文通過加權方式將能量因子和位置因子轉換為OSSA算法的適應度函數。簇首集合的剩余能量越高，距離基站越近，適應度函數值越優。其計算方式如下：

fitness=αf1+(1-α)f2

(11)

其中：α為調節兩個因子重要程度的權重系數。隨網絡運行，節點的剩余能量越來越少，選擇簇首時節點能量因素的重要程度相應增加，因此，α應隨網絡運行動態變大。其計算方式如下：

(12)

其中：Econ和Etotal分別表示網絡節點消耗的總能量和網絡的初始總能量。根據上式可知，節點消耗的能量越多，則α越大，節點的能量因子的重要程度也就越大，最優適應度值所對應的簇首集剩余總能量越多。初始階段，α取值1/2。

簇首選舉完成之后，當前簇首廣播自身成為簇首的消息，其余節點根據接收到的信號強度估算自身到每個簇首的距離，并加入最近的簇首形成分簇，完成簇的構建。

3.2 簇間路由

簇首選舉完成后，網絡進入穩定傳輸階段。在該階段，簇首將收集到的數據包發送給基站。根據能耗模型可知，節點的能耗與通信距離呈指數相關[20]。因此，縮短通信距離能夠有效降低簇首節點的能量消耗。本文提出一種基于最小生成樹的簇間路由算法，幫助簇首構建最優傳輸路徑，以此降低簇首能耗，均衡網絡節點的負載。

簇首收集簇內信息后，按照式(13)計算各鄰居簇首的轉發代價值，并選擇具有最小轉發代價的簇首作為下一跳。

(13)

3.3 基于輪詢控制的簇內通信機制

現有的分簇路由協議中，在簇構建完成后，簇首節點構建TDMA調度，成員節點根據調度表中的信息，在自己的時隙內與簇首通信，其余時間則休眠，以降低能量耗損。這種機制有效降低了節點的能量損耗。然而，根據該機制，如果節點在自己的時隙到來時沒有數據需要發送，該節點仍要被喚醒，這就給節點帶來了不必要的能耗。為解決這一問題，本文引入輪詢控制機制[21]。在選出簇首節點后，成員節點加入距離最近的簇首。簇首節點根據簇內成員節點的信息構建輪詢調度。輪詢表中記錄了節點的工作次序和對應的節點ID。其中，沒有數據需要發送的節點會被移出輪詢表，僅保留在當前輪次需要與簇首進行通信的節點。通過這種方式，節點僅在有數據需要發送的輪詢周期才會被喚醒，其余時間則處于休眠狀態，從而有效地避免了節點被不必要的喚醒，進而降低了節點的能量損耗。

4 實驗結果與分析

4.1 參數設置

為驗證本文所提協議的有效性，使用Matlab R2014b軟件對其進行仿真實驗，并與灰狼優化算法[11]和遺傳算法[14]兩種基于群體智能算法的路由協議進行對比。為測試所提協議的可擴展性，本文考慮基站位置、網絡規模和網絡節點數設置了兩種不同的場景對協議進行仿真。場景參數如表1所示，仿真參數如表2所示。OSSA算法的參數設置為：種群規模為30，最大迭代次數T為200[22]。

表1 網絡場景參數

表2 實驗參數

4.2 網絡中首個節點的死亡時間對比

無線傳感網是由多個傳感器節點通過自組網的形式組成的網絡，所有節點協同工作，負責收集監測區域內的數據信息。當所有網絡節點均能正常工作時，監測區域內的信息會被完整的采集，一旦有節點死亡，就可能出現監測盲區，使監測到的數據不全面。因此，網絡中首個節點的死亡時間是評價協議性能的重要指標。根據實驗結果，在部署100個節點的小規模應用場景下，灰狼優化算法、遺傳算法和本文協議的首個網絡節點死亡時間分別為56輪、89輪、258輪；當WSN中部署200個節點時，灰狼優化算法、遺傳算法和本文協議的首個網絡節點死亡時間分別為56輪、89輪、231輪；當WSN中部署300個節點時，灰狼優化算法、遺傳算法和本文協議的首個網絡節點死亡時間分別為73輪、129輪、285輪。為直觀反映3種協議在小規模監測區域內的首個網絡節點死亡時間對比，將穩定期繪制于圖1。從圖中可以看出，相比于其他兩種協議，本文協議能夠有效延長首個節點的死亡時間。這是因為所提出的基于OSSA的簇首選取方法能夠通過迭代優化選出最優簇首集合，從而優化聚類效果，將網絡能耗均衡給更多的節點。場景2規模較大，節點的通信距離相對較遠，通信產生的能耗也更大。在該場景中，3種協議的首個網絡節點死亡時間如圖2所示，分別為7輪、8輪、31輪。根據圖2，3種協議首個節點的死亡時間都隨著監測場景的擴展而變短。然而，與兩種對比算法相比，本文協議能夠有效延長首個網絡節點的死亡時間，這是因為該協議在通信階段使用了高效的路由算法，幫助簇首尋找合理的傳輸路徑，避免了簇首直接與基站通信，從而緩解了其能量耗損。

圖1 場景1網絡穩定期對比

圖2 場景2網絡穩定期對比

4.3 網絡生存周期對比

WSN的覆蓋范圍會隨著節點的死亡不斷降低，死亡節點過多會導致網絡癱瘓，殘余節點采集到的數據也不再有價值，此時認為網絡失效。因此，本文將網絡中有75%的節點死亡的時間定義為網絡生存周期，用來評價協議的性能。在部署100個節點的小規模監測場景中，灰狼優化算法、遺傳算法和本文協議的網絡生存期分別為457輪、579輪、1 033輪；部署200個節點時，灰狼優化算法、遺傳算法和本文協議的網絡生存期分別為538輪、827輪、1 046輪；部署300節點時，灰狼優化算法、遺傳算法和本文協議的網絡生存期分別為550輪、866輪、1 133輪。為直觀反映本文協議在網絡生存周期指標上的優勢，將3種協議的網絡生存周期繪制于圖3。從圖中可以看出，本文所提協議的網絡生存周期遠長于對比協議，這得益于理想的分簇結果和高效的簇間路由。3種協議在大規模場景中的網絡生存周期分別為257輪、396輪、698輪，如圖4所示。從圖4可以看出，隨著網絡規模的增大，3種協議的網絡生存期均明顯縮短。但本文協議的網絡生存期仍遠長于其他兩種協議。這是因為在大規模場景中，簇首節點距離基站較遠，路由算法在簇間通信階段發揮著重要的作用。本文協議綜合考慮鄰居簇首的能量因素和地理位置構建了高效的簇間路由，簇首通過多跳方式將數據發往基站，有效降低了網絡能耗，使網絡能夠工作更長的時間。

圖3 場景1網絡生存期對比

圖4 場景2網絡生存期對比

4.4 基站接收到的數據包總量對比

在監測區域內部署WSN的目的是采集數據信息，以了解目標區域的情況。當區域內出現危險信號，相關人員能夠根據現場情況做出即時動作。因此，基站接收到的數據分組總數是評價協議性能的重要指標。本文將基站接收到的數據包總量定義為網絡吞吐量。圖5為3種協議在小規模場景下的網絡吞吐量對比。從圖中可以看出，本文協議在該指標上具有較大優勢，這代表著基站接收到的數據包總數更多，對監測區域的了解也更加全面。圖6為大規模場景下3種協議的網絡吞吐量對比。根據圖6，本文協議在該指標上有明顯優于對比協議，這是因為較長的網絡生存期使基站接收到了更多的數據分組。此外，簇內使用的輪詢調度能夠避免時隙浪費，進一步提高了本文協議的網絡吞吐量。

圖5 場景1網絡吞吐量對比

圖6 場景2網絡吞吐量對比

5 結束語

為提高WSN的整體性能，，本文提出一種基于改進樽海鞘群算法的層次路由協議，該協議分別在成簇階段和穩定傳輸階段進行了優化。在成簇階段，提出一種精英反向學習SSA算法，穩固基本SSA算法全局勘探與局部開發之間的平衡，增強算法的全局搜索能力，并將節點的剩余能量和地理位置引入精英反向學習SSA算法理論，使簇首剩余能量充足且分布均勻，均衡簇內負載的同時最小化通信距離。在穩定傳輸階段，構建基于最小生成樹的簇間路由，為簇首規劃最優傳輸路徑，均衡網絡負載。簇內通信階段，使用輪詢調度構建簇內通信，避免節點被不必要的喚醒，進一步提高能量效率。最后，考慮節點數量、網絡覆蓋面積和基站的位置3種因素設置不同的應用場景對所提協議進行仿真測試，并與最新的基于群體智能算法的層次路由協議進行對比。實驗結果表明，相比于對比協議，所提協議在網絡穩定期、網絡生存期和網絡吞吐量指標上均有明顯優勢。