能量有效的無線傳感器網絡分簇路由協議

劉偉， 杜佳鴻， 賈素玲， 蒲菊華，*

(1. 北京航空航天大學 經濟管理學院, 北京 100083； 2. 深圳北航新興產業技術研究院, 深圳 518057;3. 北京航空航天大學 計算機學院, 北京 100083)

微電子技術、無線通信技術的發展以及計算技術的提高，推動了多功能的低功耗傳感器的進步，使其在自身微小體積內能夠實現采集信息、處理數據和無線通信等多種功能。無線傳感器網絡(Wireless Sensor Networks,WSNs)是一種分布式傳感器網絡，其末梢是可以感知外部世界的廉價傳感器，目的是共同感知、采集和處理網絡覆蓋區域中感知對象的信息。

WSNs作為當今信息領域新的研究熱點，待發現和研究的關鍵技術有很多，主要包括：定位技術、路由協議、網絡安全、時間同步以及數據融合等[1]。其中核心是路由技術，由于WSNs受環境以及自身約束的影響，不同實際情況中的路由協議差別可能很大，因此對于路由協議，沒有一個通用的方法，而是根據具體的要求提出獨有的設計標準[2]。

從路由結構要素出發，可以設計為2種路由協議：平面路由協議和層次路由協議，其中層次路由協議又叫做分簇路由協議。前者設計簡單，健壯性良好，但建立、維護路由的開銷大，適合小規模網絡；后者擴展性好，適合大規模網絡，且簇首節點是整個網絡的關鍵，其失效將導致路由失敗[3]。分簇式的拓撲結構有利于實際中的分布式算法，因此國內外有許多科研人員對WSNs中的分簇路由協議進行了研究，并提出了許多算法、協議[4]。

低功耗自適應集簇分層型(Low-Energy Adaptive Clustering Hierarchy,LEACH)協議是最典型的分簇算法，網絡生命的時間被分為多個回合(rounds)，每個回合包括2個階段：簇建立階段、數據傳輸階段。然而LEACH算法在很多方面還存在的不足，簇首選擇只是隨機選擇，非簇首節點在選擇加入簇時，僅依據接收信號的強度。國內外因此已經采取了很多策略進行改進，如對DCHS[5]、LEACH-improve[6]和LEACH-CH[1，7]都提出了一些改進。之后，固定簇半徑的分簇協議(Hybrid Energy-Efficient Distributed clustering, HEED)[8]算法又被提出，HEED考慮節點剩余能量和通信代價2個指標來選舉簇首節點。然而在實際情況中，由于基站一般離整個網絡的距離很遠，頻繁多次地遠距離傳輸會加大節點的消耗能量，為了解決這些問題，國內外的學者也提出了一些改進算法，如PEGASIS[9]、TEEN[10]、EEUC[11]、OHEED[1，12]和HEED-FT[1，13]，但這些協議的一個主要弊端都是簇首節點的能量消耗過大，導致網絡生存周期變短。針對具體環境，Mini等[14]針對目標覆蓋問題，使用人工蜂群算法和粒子群優化算法，解決了節點部署問題，以使滿足覆蓋要求的最少節點處于工作狀態，延長了網絡壽命。

通用設計的目標一般需要考慮以下的設計：算法簡潔性、算法可靠性、網絡自適應性、服務質量及優化能力[15]。目前的分簇路由協議在網絡能耗均衡與降低能耗方面還有較大的提升空間，雖然部分協議能夠得到分布均勻的簇首節點，但是其在簇建立階段犧牲了較多的能耗與較大的時延，在節點通信開銷方面仍存在改進的方法。因此，針對以上問題，本文提出了一種基于節點間相關性的能量有效分簇路由協議——BCCP協議。

1 BCCP協議整體設計

在LEACH、HEED路由協議的基礎上，BCCP協議還考慮了以下相關因素：①節點間位置相關性，在WSNs中，節點間位置相距近，距離小，其通信能量消耗也小。②節點間數據相似性，傳感器節點的感知數據、感知類型與其他鄰近節點監測體現的價值相似。成簇時應獲得更多的數據相似節點，數據融合效率才會更高，數據量才會降低。③節點間協同性，WSNs中的節點不是各自獨立的，網絡需要節點間合作才能產生具有價值的數據。具有協同性的節點應在同一簇內，以降低數據傳輸能耗。

當前的大多數分簇路由協議在進行簇首節點選擇時一般的選舉因素只是剩余能量，沒有考慮節點與節點之間的其他相關性因素[16]。因此，本文提出了一種基于節點間相關性的能量有效分簇路由協議——BCCP協議，該協議主要分為2個部分：第1部分為能耗均衡分簇算法BCCP-EBA，該算法是BCCP協議的主要支撐，考慮了節點自身的剩余能量、節點能耗以及節點位置相關性來選擇簇首節點和剩余節點入簇，使得簇首節點選舉階段時間短、開銷小。第2部分為降低能耗分簇算法BCCP-ESA，該算法是對BCCP-EBA能耗均衡分簇算法的完善，考慮了節點間位置相關性，能耗協同性作為節點入簇的依據，以及數據相似性和節點能耗作為簇內通信的依據，以此降低簇內通信以及網絡整體的能耗。圖1展示了BCCP協議的整體設計。

與LEACH、HEED等路由協議相比，BCCP協議使用一種基于節點間相關性的新穎的簇建立方式與數據傳輸方式，可以達到降低網絡能耗以及延長節點生存時間的目的。

圖1 BCCP協議整體設計Fig.1 Integrated design for BCCP

2 能耗均衡分簇算法BCCP-EBA

為了實現能耗均衡的WSNs，本文提出了一種基于節點間位置相關性與節點剩余能量的WSNs能耗均衡分簇算法BCCP-EBA。基于該算法的分簇路由協議按照輪次進行工作，簇建立階段分為多個迭代處理進行，一個迭代代表著一個節點接聽全部鄰居節點信息的過程。該分簇算法將節點間的位置相關性加入至分簇路由協議中，選取分布均勻的簇首節點，選取通信能耗低的簇內成員節點加入簇。

節點間的位置相關性體現于節點間的通信能耗之中，位置遠的節點間通信能耗大。因此，可以將節點與周圍鄰居節點間的通信層次作為能耗判斷參數。任意節點擁有多個通信能級，該節點通過變換通信能級與遠近不一的鄰居節點通信，即與該節點位置近的節點選擇低通信能級，與該節點位置遠的節點選擇高通信能級。使用節點最小通信能耗關系式獲得該節點與所有鄰居節點進行通信的最小能量消耗為

(1)

式中：M為該節點的鄰居節點數目；Mi為節點A與第i個鄰居節點間進行通信時使用的通信能級。

協議同樣采用節點自身剩余能量與節點間的位置相關性作為分簇參數選舉簇首節點以及選擇加入簇。參考節點自身剩余能量來選擇隨機選擇節點當選為臨時簇首節點的概率，這樣會增大剩余能量大的節點臨時簇首節點的概率。通過節點自身剩余能量與周圍鄰居節點的剩余能量共同決定節點成為臨時簇首節點的概率，以此增加簇建立階段初始時的臨時簇首節點數目，加速簇首節點選舉的過程。節點隨機生成臨時簇首節點的概率Cprob計算式為

(2)

式中：Cprob為初始成為臨時簇首節點的百分比；Eresidual為節點的剩余能量；Emax-ner為該節點的鄰居中剩余能量最大的節點的剩余能量值；Pmin為Cprob的最小值。節點以Cprob與隨機數Ran進行比較，若大于或者等于Ran，則該節點成為臨時簇首節點，反之則為普通節點。

在選擇完最終簇首節點后，非簇首節點直接在鄰居簇首節點中選擇通信能耗最小的簇首節點作為自己加入的簇首節點。

3 降低能耗分簇算法BCCP-ESA

為了進一步降低簇首節點的能耗以及簇內通信能耗，本文對節點間的數值相似性、協同性進行了研究，提出了一種降低能耗分簇算法BCCP-ESA。

該算法在能耗均衡分簇算法BCCP-EBA的基礎上改進分簇路由協議，將節點間數據相似性引入簇首節點選舉階段、節點入簇階段，以此選擇通信能耗小且數值相似的簇首節點；將節點間數據相似性引入網絡數據傳輸階段，以此降低簇內通信數據量；將節點間協同性引入網絡數據傳輸階段，以此降低簇內、簇間通信數據量。

在能耗均衡分簇算法BCCP-EBA的能量消耗計算中加入數值差異通信能耗，以此加入節點間數值相似性對簇首節點選舉以及節點選擇加入簇的影響。引入數值差異通信能耗后的節點通信能耗計算式為

(3)

式中：α為節點間位置相關性對通信能耗的影響因子；β為節點間數據相似性對通信能耗的影響因子，且α+β=1;Ai為第i個節點與計算節點間通信時傳輸的數值平均位數。

簇首節點選擇完成后，對于任意協同的節點，若該節點與其他節點具有協同性，該節點的鄰居節點中存在最終簇首節點且此簇首節點與該節點具有協同性，則該節點選擇此簇首節點作為簇首節點；若該節點的鄰居節點中存在多個最終簇首節點，則選擇通信能耗小的簇首節點作為自己的簇首節點；若該節點的鄰居節點中不存在與該節點具有協同性的簇首節點，則該節點在協同節點中選擇與簇首節點通信能耗最小的節點作為協同中轉節點，并將此中轉節點的簇首節點作為自己加入的簇首節點。

將降低能耗分簇算法BCCP-ESA加入分簇路由協議中，可以降低簇內通信的數據量，降低簇間通信的數據量，以此保護節點能耗，延長網路偶的生命周期。

對于BCCP-ESA算法，在簇建立階段，利用式(3)修改節點間的通信能耗，修改通信能耗計算后，利用能耗均衡分簇算法BCCP-EBA的分簇機制對網絡中的簇首節點選擇及節點選擇入簇產生影響。在數據傳輸階段，進行簇內通信時直接使用節點間數值差異傳輸即可。

簇首節點選舉完成后，利用節點間協同性選擇協同節點的簇首節點、中繼節點，對于任意節點在選擇加入通信能耗最小的簇首節點時，按照如下步驟進行：

步驟1該節點感知周圍存在的簇首節點以及與該節點具有協同性的節點，轉至步驟2。

步驟2判斷該節點的鄰居節點中是否存在與該節點協同的節點，若不存在，則轉至步驟3，若存在，轉至步驟4。

步驟3在鄰居簇首節點中選擇通信能耗最小的簇首節點作為該節點加入的簇首節點，若該節點被最終簇首節點覆蓋，則結束。

步驟4判斷該節點的鄰居協同節點中是否存在簇首節點，若存在，轉至步驟5，否則，轉至步驟6。

步驟5該節點將鄰居協同節點中的簇首節點作為該節點加入的簇首節點，若該節點被最終簇首節點覆蓋，則結束。

步驟6該節點在協同節點中選擇與簇首節點通信能耗最小的節點作為協同中轉節點，并將此節點的簇首節點作為該節點加入的簇首節點，若該節點被最終簇首節點覆蓋，則結束。

4 仿真實驗

在WSNs中，由于其自身的特點，對于大規模部署的WSNs，在真實物理環境的測量中很難實現，只能利用計算機的模擬仿真實驗對研究的協議、算法等進行測試，對其性能進行分析評價。本文提出的BCCP分簇路由協議采用MATLAB平臺進行仿真實驗。

4.1 仿真環境設置

本實驗的仿真基于MATLAB 7.1平臺上進行，仿真參數設計如表1所示。

仿真實驗主要選擇了LEACH、HEED分簇路由協議與BCCP協議進行比較，并且分別與BCCP協議中的能耗均衡分簇算法BCCP-EBA與降低能耗分簇算法BCCP-ESA進行比較，驗證算法的有效性，主要的指標有簇建立消耗能量、網絡存活節點、網絡整體能耗。本文實驗以50%的節點死亡作為網絡失效的標志。

表1 仿真環境參數設置Table 1 Parameter setting of simulation environment

4.2 實驗結果分析

為了分析BCCP-EBA與BCCP-ESA對BCCP協議的影響，將BCCP協議分為3個版本：①能耗均衡分簇算法BCCP-EBA；②BCCP-VALUE，在BCCP-EBA基礎上加入節點間數據相似性后實現的分簇路由協議；③BCCP-COO，在BCCP-EBA基礎上加入節點間協同性后實現的分簇路由協議。

為了對比節點間數據相似性與節點間協同性對網絡能耗的影響，在LEACH協議基礎上實現了如下2個協議：①LEACH-VALUE，在LEACH的基礎上加入節點間數據相似性后實現的分簇路由協議；②LEACH-COO，在LEACH基礎上加入節點間協同性后實現的分簇路由協議。

4.2.1 BCCP-EBA協議仿真結果

LEACH、HEED和BCCP-EBA分簇路由協議在每軟次簇建立階段消耗的能量隨時間的變化曲線如圖2所示。圖中，橫坐標為網絡工作進行的輪數，用來代表網絡工作的時間，縱坐標為協議在簇建立階段消耗的能量。

圖2 簇建立階段消耗的能量對比Fig.2 Comparison of energy consumption for construction of clusters

由圖2可知，BCCP-EBA分簇路由協議在簇建立階段的能耗一直處于一個較低的水平；HEED分簇路由協議在存活節點較多時需要消耗較多的能量進行分簇，存活節點數目小時，簇建立階段的能耗也較低；LEACH分簇路由協議中的分簇能耗較大，主要是因為其簇內部存在個別成員節點與簇首節點距離過大，導致能耗過大。

LEACH、LEACH-COO、BCCP-EBA和BCCP-COO分簇路由協議的存活節點數目隨輪次的變化如圖3所示。圖中縱坐標為整個網絡中的存活節點的數目。圖4中LEACH-COO分簇路由協議相對于LEACH協議，其生存時間得到了微小的提升；圖3中BCCP-COO分簇路由協議相對于BCCP-EDA協議，其生存時間得到了一定程度的提升，將網絡的生存時間延長了5%左右。

LEACH、LEACH-COO、BCCP-EBA和BCCP-COO分簇路由協議的網絡整體能耗隨輪次的變化曲線如圖4所示。圖4中在LEACH引入節點間數據相似性要素后，其網絡整體能耗有了一定的改善，但是效果很不明顯；圖4中在BCCP-EBA分簇路由協議中引入節點間數據相似性要素后，網絡整體能耗降低了5%左右。所以，引入節點間數據相似性要素可以降低網絡的能耗，但是效果不明顯。

4.2.2 BCCP協議仿真結果

BCCP-EBA、BCCP-COO、BCCP-VALUE和BCCP分簇路由協議的存活節點數目隨軟次的變化曲線如圖5所示。由圖5可知，在將能耗均衡分簇算法BCCP-EBA與降低能耗分簇算法BCCP-ESA進行融合后，BCCP分簇路由協議能夠更好地進行工作，存活節點數目、網絡生存時間均有改善。

圖4 網絡整體能耗對比Fig.4 Comparison of complete network energy consumption

圖5 BCCP-EBA、BCCP-COO、BCCP-VALUE和BCCP分簇路由協議的網絡存活節點數目對比Fig.5 Comparison of number of live nodes in network of BCCP-EBA，BCCP-COO，BCCP-VALUE and BCCP clustering routing protocol

BCCP-VALUE協議中節點位置相關性α與節點數據相似性β在進行分簇時的權重比例對網絡的影響如圖6所示。由圖6可知，節點位置相關性對于網絡能耗的影響強于節點數據相似性，當節點數據相似性為0.7時，網絡性能最優。這是因為在節點的通信模型中，能耗與kd2成正比，k為數據量，即節點數據相似性的影響因素；d為節點間距離，即為幾點位置相關性的影響因素。因此，節點位置相關性對網絡性能影響較大。

圖6 不同α,β取值對網絡性能的影響Fig.6 Influence of different α and β on network performance

5 結 論

1) 以節點間的位置相關性為依據計算節點能耗，以節點自身的剩余能量與鄰居節點最大剩余能量計算隨機生成簇首節點的概率，以節點能耗為依據得到分布均勻的簇首節點，以節點能耗作為節點入簇的依據，以此使得簇首節點選舉階段時間短、開銷小，初始時隨機生成的臨時簇首節點數目穩定。

2) 以節點間的位置相關性和節點間數據相似性為依據共同計算節點能耗，以節點能耗和協同性作為節點入簇的依據，以節點間數據相似性和協同性作為簇內單跳通信的依據，以此降低簇內通信、簇間通信的數據量，降低節點自身、網絡整體的能耗。