一種基于協(xié)同演化算法的無線傳感器網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)方法

張麗

關(guān)鍵詞：進(jìn)化算法；無線傳感器網(wǎng)絡(luò)；網(wǎng)絡(luò)優(yōu)化；路由路徑

0引言

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

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

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

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

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

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

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

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

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

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

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

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

2 建模

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

2.1 定義參數(shù)

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

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

3 協(xié)同演化算法

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

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

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

4 實(shí)驗(yàn)與分析

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

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

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

5結(jié)束語

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