基于離散粒子群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化

黃紅波 王勇智

摘要：無(wú)線(xiàn)傳感器網(wǎng)絡(luò)技術(shù)的出現(xiàn)使得農(nóng)業(yè)更加精準(zhǔn)化、智能化，其在農(nóng)業(yè)上的應(yīng)用環(huán)境如果園與水果大棚等往往具有面積大、作物多等特點(diǎn)，需要更多的傳感器節(jié)點(diǎn)以用于監(jiān)測(cè)。由于傳感器節(jié)點(diǎn)往往使用電池進(jìn)行供電，有限的能量也給網(wǎng)絡(luò)的魯棒性帶來(lái)了更大的挑戰(zhàn)?；陔x散粒子群算法設(shè)計(jì)了一種無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的拓?fù)鋬?yōu)化算法，在保證網(wǎng)絡(luò)覆蓋的情況下，通過(guò)盡可能減少活動(dòng)節(jié)點(diǎn)的數(shù)量來(lái)降低網(wǎng)絡(luò)的能量損耗，延長(zhǎng)網(wǎng)絡(luò)的生命周期，從而提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的魯棒性。

關(guān)鍵詞：無(wú)線(xiàn)傳感器網(wǎng)絡(luò);離散粒子群優(yōu)化算法;網(wǎng)絡(luò)拓?fù)?/p>

Abstract：The emergence of wireless sensor network technology makes agriculture more precise and intelligent. Its application environment in agriculture， such as gardens and fruit greenhouses， often has the characteristics of a large area and many crops， and more sensor nodes are needed for monitoring. Since batteries often power sensor nodes， limited energy brings more significant challenges to the network's robustness. This paper sets up a topology optimization algorithm for wireless sensor networks based on the discrete particle swarm algorithm. Under the condition of ensuring network coverage， the energy loss of the network is reduced by reducing the number of active nodes as much as possible， and the life cycle of the network is prolonged， thereby improving the robustness of the wireless sensor network.

Key words：wireless sensor network; discrete particle swarm optimization algorithm; network topology

1 引言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的迅速發(fā)展，推動(dòng)了農(nóng)業(yè)的精準(zhǔn)化、智能化發(fā)展。為最大化無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生命周期，保障農(nóng)業(yè)環(huán)境監(jiān)測(cè)的穩(wěn)定性，研究降低網(wǎng)絡(luò)能耗的方法至關(guān)重要[1，2]。粒子群算法（Particle Swarm Optimization， PSO）[3]模仿鳥(niǎo)群、魚(yú)群等群體智能，將連續(xù)空間的優(yōu)化求解問(wèn)題轉(zhuǎn)化為粒子朝著全局最優(yōu)解不斷移動(dòng)的過(guò)程，其搜索速度快、效率高、算法簡(jiǎn)單，但對(duì)于離散的優(yōu)化問(wèn)題處理不佳[4]。為了解決在進(jìn)行農(nóng)業(yè)大棚環(huán)境監(jiān)測(cè)過(guò)程中，無(wú)線(xiàn)傳感器網(wǎng)絡(luò)存在的各節(jié)點(diǎn)剩余能量及負(fù)載不均的問(wèn)題，我們?cè)O(shè)計(jì)了一種基于離散粒子群算法的網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法（DiscreteParticle Swarm OptimizationforTopologyControl， DPSOTC），算法采用一個(gè)激活函數(shù)將連續(xù)空間內(nèi)的粒子位置轉(zhuǎn)化為離散空間內(nèi)的位置，通過(guò)將節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)以及剩余能量等建立適應(yīng)度函數(shù)，來(lái)優(yōu)化無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的拓?fù)?，能有效求出滿(mǎn)足網(wǎng)絡(luò)覆蓋條件下所需的最少活動(dòng)節(jié)點(diǎn)數(shù)，從而能提高無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的生命周期，增強(qiáng)網(wǎng)絡(luò)的魯棒性。

2粒子群優(yōu)化算法簡(jiǎn)述

在粒子群算法中，每個(gè)粒子在初始化時(shí)將被分配一個(gè)隨機(jī)的位置與速度，每個(gè)粒子的位置代表著一個(gè)可行解。對(duì)于種群規(guī)模為[Np]，維度為[D]的種群，一個(gè)粒子[i∈[1，Np]]在第[t+1]次迭代時(shí)，[d∈[1，D]]維的解空間位置

3基于離散粒子群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法

粒子群算法的優(yōu)化求解問(wèn)題是一個(gè)連續(xù)空間問(wèn)題，而無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)的活動(dòng)與否是一個(gè)離散空間問(wèn)題。為將粒子群算法應(yīng)用到精準(zhǔn)農(nóng)業(yè)的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化問(wèn)題中，我們?cè)O(shè)計(jì)了一種基于離散粒子群算法的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法DPSOTC。

算法首先采用一個(gè)激活函數(shù)將連續(xù)空間內(nèi)的粒子位置[Xi，dt]轉(zhuǎn)化為離散空間內(nèi)的位置[Bi，dt]，激活函數(shù)定義如下：

通過(guò)該函數(shù)，粒子當(dāng)前在連續(xù)空間內(nèi)的位置[Xi，dt]將被轉(zhuǎn)化為[ （0，1）]上的輸出，并且其值越接近于1代表粒子在連續(xù)空間內(nèi)的位置越大，其值越接近于0則連續(xù)空間內(nèi)的位置越小。通過(guò)設(shè)置一個(gè)閾值，可以將激活函數(shù)的輸出劃分為0和1兩類(lèi)，即離散空間內(nèi)的位置[Bi，dt]。

其中，閾值[rand]為[0，1]范圍內(nèi)的一個(gè)滿(mǎn)足均勻分布的隨機(jī)數(shù)。[Bi，dt]表示第t次迭代后，粒子群中第[i]個(gè)粒子的位置所代表的無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中第[d]個(gè)節(jié)點(diǎn)的狀態(tài)。為0表示該節(jié)點(diǎn)處于休眠狀態(tài)，為1則表示該節(jié)點(diǎn)處于活動(dòng)狀態(tài)。通過(guò)統(tǒng)計(jì)粒子在所有維度的位置，即可得到無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中所有節(jié)點(diǎn)的狀態(tài)，即網(wǎng)絡(luò)拓?fù)洹?/p>

針對(duì)農(nóng)業(yè)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)監(jiān)測(cè)面積大、節(jié)點(diǎn)多、地勢(shì)復(fù)雜、作物多樣化以及要求低能耗等特點(diǎn)，結(jié)合相應(yīng)農(nóng)業(yè)監(jiān)測(cè)系統(tǒng)的設(shè)計(jì)原理和需求分析，我們提出的算法PSOTC在搜索過(guò)程中更傾向于尋找節(jié)點(diǎn)鄰居數(shù)大、剩余能量多且活動(dòng)節(jié)點(diǎn)少的解。為了解決這個(gè)問(wèn)題，我們將公式（3）、（4）中的適應(yīng)度函數(shù)進(jìn)行了針對(duì)的改進(jìn)，提出了一個(gè)基于節(jié)點(diǎn)[d]的鄰居數(shù)[Nd]、剩余能量[Ed]以及其在離散空間的位置[Bi，d]的適應(yīng)度函數(shù)，以此評(píng)估算法在每次迭代過(guò)程中所有粒子構(gòu)成的網(wǎng)絡(luò)拓?fù)涞膬?yōu)劣，其值越小代表著得到的網(wǎng)絡(luò)拓?fù)湓絻?yōu)秀。即