一種基于協同演化算法的無線傳感器網絡拓撲設計方法

0 引言

如今，無線傳感器網絡（WSN）因其高度認可的實用價值而迅速發展。為了不斷提高WSN 的相關技術和應用潛力，進行了各種研究和開發。例如，WSN 可用于連續傳感，事件檢測，位置傳感等^[1]。WSN 由低成本，低功耗的多功能傳感器組成，其中每個傳感器的尺寸都很小，并且在短距離內不受限制地通信。傳感器能夠檢測特定的環境參數、信息處理和無線通信。但是，每個傳感器節點只能進行有限數據量的處理。

以前，傳感器網絡由連接到中央處理站的少量傳感器節點組成。在大多數情況下，要監測的環境沒有現有的基礎設施來提供能源或通信渠道。因此，如何在小而有限的能源上生存并通過無線通信信道進行通信成為WSN 設計的必要條件^[2]。換句話說，WSN 的能耗、覆蓋范圍和最短路由路徑是WSN 設計過程中的關鍵問題。

如果每個傳感器將消息直接傳輸到中心節點，由于傳感器和中心節點之間的距離較長，可能會非常耗電^[3]。然而，由于傳感器體積小且儲能容量有限，傳感器很難將收集信息有效地直接中繼到中心節點。在這種情況下，所有傳感器都需要直接或間接地將其數據傳輸到中心節點，通信信號在傳感器通信半徑范圍內與其他傳感器節點進行通信^[4]。最小化通信距離且平衡每個節點工作負載的設計可以延長整體網絡生命周期^[3]。

如圖1 所示，WSN 已解決節能問題，還滿足了其他條件，如負載平衡、容錯等。在 WSN 中，節點使用集中或分布式方法成為多個集群。傳感器檢測到和收集的數據通過所選集群的中心節點路由的最優路徑傳輸到網絡中心節點^[5]。

與直接與中心節點進行通信相比，集群的形成可以大大降低通信成本。因為功耗與傳輸距離成正比，并且在集群形成中，傳感器節點將數據發送到最近的集群中心節點（主節點），而不是直接發送到可能更遠的網絡中心節點^[6]。對于那些遠離中心節點的主節點，直接通信是不合適的。我們必須找到最短路由路徑，必須考慮每個節點的路徑距離和工作負載。

最優路由路徑是對WSN 性能有重大影響的最重要的設計問題之一^[7-8]。最短路徑問題（SPP）是一個經典的網絡優化問題。最短路由路徑問題的搜索算法有很多，如Dijkstra 算法、Bellman-Ford 算法等。這些算法專為單目標 SPP 設計。然而，多目標SPP（MSPP）是一個NP 難題。MSPP 可以表述為一個用于查找包含指定源節點和目標節點的最小成本路徑，MSPP 是許多設計和規劃中出現的經典組合優化問題^[9]。

遺傳算法（GA）具有很強的并行搜索能力，是多目標優化問題中最有前途的算法之一。GA 和其他相關的進化算法可以解決MSPP 問題，并且它們已成功用于各種實際應用。在本文中，我們使用擴展的GA 方法來解決WSN 拓撲設計問題。與其他方法相比，本文提出的方法可以在更短的時間內獲得一組近似最優解。

1 背景與實際工作

目前，已經有不少專家進行了研究來改進WSN 設計。Kumar 等人^[10]旨在提取具有最小能耗的WSN 的最佳集群數。盡管他們采用的分析方法與預測結果一致^[11]，但他們對集群頭節點到中心節點的平均距離做出了過于嚴格的假設。

Si ^[12] 提出了一種用于不同數據傳輸路徑排列的梯度擴散算法，該算法側重于平衡傳輸路徑上傳感器節點的工作量，并提高所有傳感器節點的預期壽命。該算法記錄可用于構建整個傳輸路徑每個路徑段的節點數。通過計算找到最優路徑，而且可以降低整體能耗。仿真結果表明，與其他傳統算法相比，所提算法節能13.61%。此外，該算法平衡了各傳感器節點的負載，降低了能耗，使數據包能夠快速發送到最終目的節點。

Chang 和Ramakrishna^[13]提出了一種遺傳算法方法來解決最短路徑路由問題。他們使用可變長度的染色體及其基因來編碼。在位置無關的交叉位點交換部分染色體，突變操作保持了種群的遺傳多樣性。這個算法可以通過簡單的修復功能治愈所有不可行的染色體。

如上所述的WSN 工作很少關注多重目標方面的問題。本文的方法使用 EA 來確定集群頭和路由路徑的數量和位置，從而最大限度地減少WSN 中的通信距離。

2 建模

通過將WSN 組織成集群形式，可以大大縮短總通信距離，從而節省能源并延長每個節點的預期壽命，均衡主節點的負載。

2.1 定義參數

在本文中，我們假設WSN 要監測的區域是一個平坦的方形表面，并且每個傳感器節點都可以檢測由傳感器半徑確定的圓形區域內的所有數據。所有傳感器節點都是相同的，并且在部署在唯一的坐標上后，坐標是固定不變的。WSN 模型的參數和變量定義如下：

2.2 數學模型

為了模擬WSN設計問題，我們定義了一個有向圖，其中V 是一組M 個主節點，E 是一組邊。每個節點的負載對應一個非負，并表示節點k 和節點m 之間的距離。如果節點k 和節點m 之間的距離小于通信半徑，則節點k 和節點m 之間存在邊。主節點最大覆蓋、最小總距離和最佳路由路徑的數學模型表述如下：

等式（6）是兩個節點之間的距離，它必須小于通信距離，約束（7）確保每個主節點與中心節點之間的距離在通信距離限制范圍內，式（8）是集群中節點之間的總距離，式（9）是整個網絡的總距離，約束（10）保證主節點數和傳感器節點數等于節點總數。式（11）是兩個主節點之間的距離。式（14）和式（15）確保除源節點和目標節點外，每個節點不存在或只有兩條相鄰邊。約束（16）和式（17）確保結果是源節點和目標節點之間沒有環路的路徑。

圖2 生態系統中的可協商進化算法

3 協同演化算法

EA 是一種啟發式優化方法，靈感來自生物物種遺傳特征的自然進化過程^[11]。EA 在為多目標問題找到最佳解決方案方面無效，但它可以快速收斂，找到最優的解決方案。在本文中，我們使用可協商進化算法[14] 來解決多目標WSN 布局問題。NEA 過程如圖2 所示，生態系統可用于表示WSN 的整體性能，并且生態系統中物種的進化可用于對相應子問題的進行求解，優化算法進行建模。

首先將WSN 問題劃分為N 個子問題，每個問題都可以通過EA 更有效地解決。進行進化過程后，選擇一些解決方案作為跨物種進化候選者，然后評估每個子解決方案對系統目標的貢獻。從本質上講，可以識別顯著能提高系統目標適應性的基因模式，并在合作伙伴之間共享信息。最優的基因模式可能會在EA 模型之間遷移，以促進對整體解決方案的合理探索，從而避免重復收斂到局部目標，然后重新啟動每個EA 模型的演變并迭代該過程，直到滿足終止標準。^[14]

圖3 NEA優化結果

本文采用合作貝葉斯優化算法（COBOA）實現協商促進。圖3 描述了每個物種的每個迭代器使用任何標準的進化算法，從原始種群中選擇有較優的解決方案。首先，構建一個用于對子問題進行建模的貝葉斯網絡，獲得最優的解決方案。然后，使用構建的網絡對一些新的候選個體進行采樣，新的候選個體與其他種群的代表合作。最后，將評估的新候選個體納入原始種群。該過程將迭代，直到滿足預定義的終止條件。^[16]

4 實驗與分析

在本文中，NEA 和CEA（交叉EA-baesd）[15] 都是在Eclipse 環境下使用JAVA 語言編程的。該程序在配置有2.33 GHz CPU 和2.00 GB RAM 的PC 上運行。

圖4 顯示了當中心節點位于（0，0）時NEA 的優化結果。

圖4 NEA優化結果

從圖5 和圖6 中，我們可以看到NEA 方法取得了更好的結果。圖5 顯示了與CEA 相比，NEA 發現更短的總通信距離值，圖6 分別顯示了NEA 和CEA 實現的覆蓋值曲線。

圖5 距離值曲線

圖6 覆蓋值曲線

5 結束語

本文提出了一種NEA方法來解決多目標優化問題，例如確定WSN 的布局和路由策略。實驗表明，NEA 在復雜環境下提供的決策是有效的。在我們未來的工作中，作者希望改進談判促進者，以解決建模和解決復雜多目標問題?；谒岢龅姆椒?，作者還希望及時實現一個功能齊全的軟件應用程序，用于設計真實案例場景的WSN。

參考文獻：

[1] 汪清清,王茜,李小平.網絡環境下數據交換方案的設計與實現[J].東南大學學報(自然科學版).2007(4):59-66.

[2] ARCHANA B, VIJAY A S P. Sensor networks: an overview[J].University of California, Davis, CA 95616.

[3] 楊平,鄭金華.遺傳選擇算子的比較與研究[J].計算機工程與應用,2007(15)：37-46.

[4] NAVID A, ALIREZA V, XU W Y, et al. Cluster size optimization in sensor networks with decentralized clusterbased protocols [J]. Computer Communications, 2012(35):207-220.

[5] NAVID A, ALIREZA V, XU W Y, et al. Cluster size optimization in sensor networks with decentralized clusterbased protocols [J]. Computer Communications, 2012(35): 207-220.

[6] W. STALLING. High-Speed Networks: TCP/IP and ATM Design Principles[J]. Englewood Cliffs, NJ: Prentice- Hall,1998.

[7] M. K. ALI, F. KAMOUN. Neural networks for shortest path computation and routing in computer networks[J]. IEEE Trans. Neural Networks, 1993,4(11):941–954.

[8] 董紅斌,丁蕊.協同演化算法及其應用[M].哈爾濱:哈爾濱工程大學出版社,2021.

[9] D. KUMAR, C.A. TRILOK, R.B. Patel. EEHC: energy efficient heterogeneous clustered scheme for wireless sensor networks[J]. Computer Communication, 2009,32 (4) :662-667.

[10] W.B. HEINZELMAN, A.P. CHANDRAKASAN, H. BALAKRISHNAN, An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Transactions on Wireless Communications, 2002 (4) : 660-670.

[11] 何俊輝, 潘正祥.“梯度擴散算法”2011年信息技術與應用學術會議[C],2011.

[12] CHANG W A, R. S. RAMAKRISHNA. A genetic algorithm for shortest path routing”, IEEE transactions on evolutionary computation[J]. 2002,6(12):566-578.

[13] HAO X, LIN H W, T MURATA. Application of negotiable evolutionary algorithm in flexible manufacturing planning and scheduling[C]. Proceedings of 17th International Conference on Industrial Engineering and Engineering Management (IE&EM 2010)

[14] 張麗,林文浩. 基于種群交叉策略遺傳算法的無線傳感器網絡結構設計[D].哈爾濱:哈爾濱工業大學,2012.

[15] HAO X, CHEN X, LIN H W, et al. Cooperative bayesian optimization algorithm: a novel approach to simultaneous multiple resources scheduling problem[C]. Second International Conference on Innovations in Bio-inspired Computing and Applications, 2011.

（本文來源于《電子產品世界》雜志2023年4月期）