一種基于協(xié)同演化算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )拓撲設計方法

0 引言

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

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

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

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

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

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

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

1 背景與實(shí)際工作

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

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

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

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

2 建模

通過(guò)將WSN 組織成集群形式，可以大大縮短總通信距離，從而節省能源并延長(cháng)每個(gè)節點(diǎn)的預期壽命，均衡主節點(diǎn)的負載。

2.1 定義參數

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

2.2 數學(xué)模型

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

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

圖2 生態(tài)系統中的可協(xié)商進(jìn)化算法

3 協(xié)同演化算法

EA 是一種啟發(fā)式優(yōu)化方法，靈感來(lái)自生物物種遺傳特征的自然進(jìn)化過(guò)程^[11]。EA 在為多目標問(wèn)題找到最佳解決方案方面無(wú)效，但它可以快速收斂，找到最優(yōu)的解決方案。在本文中，我們使用可協(xié)商進(jìn)化算法[14] 來(lái)解決多目標WSN 布局問(wèn)題。NEA 過(guò)程如圖2 所示，生態(tài)系統可用于表示W(wǎng)SN 的整體性能，并且生態(tài)系統中物種的進(jìn)化可用于對相應子問(wèn)題的進(jìn)行求解，優(yōu)化算法進(jìn)行建模。

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

圖3 NEA優(yōu)化結果

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

4 實(shí)驗與分析

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

圖4 顯示了當中心節點(diǎn)位于（0，0）時(shí)NEA 的優(yōu)化結果。

圖4 NEA優(yōu)化結果

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

圖5 距離值曲線(xiàn)

圖6 覆蓋值曲線(xiàn)

5 結束語(yǔ)

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

參考文獻：

[1] 汪清清,王茜,李小平.網(wǎng)絡(luò )環(huán)境下數據交換方案的設計與實(shí)現[J].東南大學(xué)學(xué)報(自然科學(xué)版).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] 董紅斌,丁蕊.協(xié)同演化算法及其應用[M].哈爾濱:哈爾濱工程大學(xué)出版社,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年信息技術(shù)與應用學(xué)術(shù)會(huì )議[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] 張麗,林文浩. 基于種群交叉策略遺傳算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò )結構設計[D].哈爾濱:哈爾濱工業(yè)大學(xué),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.

（本文來(lái)源于《電子產(chǎn)品世界》雜志2023年4月期）