楊海波，陳友榮，劉半藤，祝云凱，蘇子漪

（1.浙江樹人大學(xué)信息科技學(xué)院，浙江 杭州 310015；2.浙江杭佳科技發(fā)展有限公司，浙江 杭州 310015）

1 引言

在無線傳感網(wǎng)（wireless sensor network，WSN）中，節(jié)點(diǎn)的能量約束限制了網(wǎng)絡(luò)覆蓋、生存時間等基本功能。網(wǎng)絡(luò)高覆蓋能確保從傳感節(jié)點(diǎn)收集的數(shù)據(jù)準(zhǔn)確表示監(jiān)控區(qū)域。根據(jù)感知對象的不同，網(wǎng)絡(luò)覆蓋可分成目標(biāo)覆蓋、柵欄覆蓋和區(qū)域覆蓋。其中，目標(biāo)覆蓋要求傳感節(jié)點(diǎn)能覆蓋到所有目標(biāo)點(diǎn)。當(dāng)目標(biāo)點(diǎn)遍布于監(jiān)測區(qū)域且數(shù)量足夠多時，目標(biāo)覆蓋問題可轉(zhuǎn)換成區(qū)域覆蓋問題。柵欄覆蓋要求傳感節(jié)點(diǎn)能完整覆蓋一條直線。當(dāng)直線數(shù)量足夠多時，柵欄覆蓋問題也可轉(zhuǎn)換成區(qū)域覆蓋。區(qū)域覆蓋問題是網(wǎng)絡(luò)覆蓋的基本問題之一，可應(yīng)用到環(huán)境監(jiān)測、智慧工廠、入侵檢測等多個領(lǐng)域[1-3]。同時，網(wǎng)絡(luò)生存時間是指WSN從整個網(wǎng)絡(luò)收集數(shù)據(jù)的有效工作時間。網(wǎng)絡(luò)生存時間越大，則WSN的壽命越長，其應(yīng)用成本越短，因此在環(huán)境監(jiān)測等應(yīng)用領(lǐng)域，WSN的設(shè)計(jì)應(yīng)保持令人滿意的區(qū)域覆蓋和持續(xù)幾個月或幾年時間收集所需的感測數(shù)據(jù)（如溫度），并傳輸給基站[4,5]。

目前許多研究側(cè)重于同構(gòu)無線傳感網(wǎng)（所有傳感節(jié)點(diǎn)具有相同的性能，如安裝有相同的傳感器、其位置都靜止或都可以移動）的網(wǎng)絡(luò)覆蓋問題，如參考文獻(xiàn)[6]考慮每一個傳感節(jié)點(diǎn)的數(shù)據(jù)感知具有方向性，建立和采用列生成法求解生存時間優(yōu)化模型。參考文獻(xiàn)[7]建立和求解最小工作傳感節(jié)點(diǎn)個數(shù)和最大網(wǎng)絡(luò)覆蓋的優(yōu)化模型，確定每一個傳感節(jié)點(diǎn)的工作調(diào)度。參考文獻(xiàn)[8]將監(jiān)測區(qū)域分成多個網(wǎng)格，每一個網(wǎng)格的傳感節(jié)點(diǎn)選擇成為簇頭和成員，并采用一種權(quán)值計(jì)算式和提出傳感節(jié)點(diǎn)的移動選擇算法。參考文獻(xiàn)[9]提出最大每一個移動傳感節(jié)點(diǎn)的覆蓋率和最大所有移動傳感節(jié)點(diǎn)覆蓋率的多目標(biāo)優(yōu)化模型，并求解該優(yōu)化模型獲得最優(yōu)解?？傊瑓⒖嘉墨I(xiàn)[6,7]考慮傳感節(jié)點(diǎn)的位置固定不變。參考文獻(xiàn)[8,9]考慮所有傳感節(jié)點(diǎn)都可移動。而且參考文獻(xiàn)[6-9]考慮同構(gòu)傳感節(jié)點(diǎn)，但是在一些特殊應(yīng)用中，傳感節(jié)點(diǎn)存在感知范圍、能量等方面的異構(gòu)。

隨著無線傳感網(wǎng)應(yīng)用領(lǐng)域的不斷擴(kuò)大，同構(gòu)無線傳感網(wǎng)已經(jīng)不能滿足實(shí)際應(yīng)用的需要，如在無線傳感網(wǎng)的典型應(yīng)用——環(huán)境監(jiān)測中，需要監(jiān)測大氣溫度、濕度、光照強(qiáng)度等環(huán)境信息。顯然每個傳感節(jié)點(diǎn)不可能同時安裝所有傳感器，需要考慮安裝有不同類型的傳感器，即感知半徑不同的異構(gòu)傳感節(jié)點(diǎn)。因此一些學(xué)者研究異構(gòu)傳感節(jié)點(diǎn)的覆蓋問題，如參考文獻(xiàn)[10]提出一種基于多重覆蓋算法的異構(gòu)節(jié)點(diǎn)調(diào)度算法。該算法建立覆蓋率最大和工作節(jié)點(diǎn)數(shù)量最小的多目標(biāo)優(yōu)化模型，采用差分進(jìn)化算法求解獲得最優(yōu)方案。參考文獻(xiàn)[11]將覆蓋問題轉(zhuǎn)換成多個直線的覆蓋問題，并建立直線覆蓋的傳感節(jié)點(diǎn)移動優(yōu)化模型。采用線性求解算法求解獲得最短移動路徑。但是參考文獻(xiàn)[10,11]是集中式方法，其計(jì)算量隨著傳感節(jié)點(diǎn)個數(shù)的增加而急劇增大。參考文獻(xiàn)[12]根據(jù)鄰居覆蓋集合的信息，提出傳感節(jié)點(diǎn)的調(diào)度，從而最小覆蓋監(jiān)測區(qū)域且保證網(wǎng)絡(luò)連接。參考文獻(xiàn)[13]根據(jù)鄰居節(jié)點(diǎn)的不同位置，采用冗余方法對自身節(jié)點(diǎn)進(jìn)行判斷。如果判斷冗余，則關(guān)閉冗余節(jié)點(diǎn)。雖然參考文獻(xiàn)[12,13]是分布式方法，但是這些算法都沒有考慮網(wǎng)絡(luò)生存時間，也沒有考慮當(dāng)樞紐傳感節(jié)點(diǎn)失效時覆蓋盲區(qū)的修復(fù)問題。同時參考文獻(xiàn)[10-13]只是考慮異構(gòu)靜態(tài)傳感節(jié)點(diǎn)的調(diào)度，沒有考慮異構(gòu)傳感節(jié)點(diǎn)的移動性，容易出現(xiàn)能量空穴問題，因此部分學(xué)者考慮異構(gòu)傳感節(jié)點(diǎn)的移動，研究異構(gòu)移動傳感節(jié)點(diǎn)的覆蓋問題，如參考文獻(xiàn)[14]根據(jù)傳感節(jié)點(diǎn)的數(shù)量，判斷每一個網(wǎng)格的負(fù)載，負(fù)載高的網(wǎng)格中部分傳感節(jié)點(diǎn)向負(fù)載低的網(wǎng)格移動。參考文獻(xiàn)[15]在位置進(jìn)化中考慮異構(gòu)傳感節(jié)點(diǎn)間的虛擬力，提出虛擬力導(dǎo)向差分算法，從而優(yōu)化覆蓋率。參考文獻(xiàn)[16]考慮監(jiān)控區(qū)域內(nèi)存在覆蓋盲點(diǎn)，提出一種能耗最小和感知覆蓋最大的覆蓋洞修補(bǔ)算法，獲得異構(gòu)傳感節(jié)點(diǎn)的移動規(guī)劃路徑。但是參考文獻(xiàn)[14-16]都是集中式算法，其算法計(jì)算量較大，一般只適合傳感節(jié)點(diǎn)數(shù)量較少的網(wǎng)絡(luò)，而且只是考慮所有傳感節(jié)點(diǎn)具有移動性，需要配置移動設(shè)備和大功率的電池，大大增加了無線傳感網(wǎng)部署的成本。

綜上所述，目前同構(gòu)靜態(tài)或移動傳感節(jié)點(diǎn)的覆蓋優(yōu)化算法沒有考慮傳感節(jié)點(diǎn)的異構(gòu)性。異構(gòu)靜態(tài)傳感節(jié)點(diǎn)的覆蓋優(yōu)化算法同樣存在能量空穴問題。異構(gòu)移動傳感節(jié)點(diǎn)的覆蓋優(yōu)化算法主要偏向于假設(shè)所有傳感節(jié)點(diǎn)具有移動性，具有較大的硬件成本，且側(cè)重于集中式方法，較少涉及分布式算法。因此在上述參考文獻(xiàn)的基礎(chǔ)上，為降低系統(tǒng)的硬件成本，考慮環(huán)境監(jiān)測等應(yīng)用中同時存在異構(gòu)靜態(tài)傳感節(jié)點(diǎn)和少量移動傳感節(jié)點(diǎn)。當(dāng)網(wǎng)絡(luò)啟動后，靜態(tài)傳感節(jié)點(diǎn)的分布不均勻造成覆蓋盲區(qū)，或者當(dāng)網(wǎng)絡(luò)運(yùn)行一段時間后，部分靜態(tài)傳感節(jié)點(diǎn)因能量耗盡而死亡，造成網(wǎng)絡(luò)覆蓋盲區(qū)時，利用傳感節(jié)點(diǎn)的移動，提出一種優(yōu)化網(wǎng)絡(luò)生存時間的移動傳感節(jié)點(diǎn)覆蓋調(diào)度算法（coverage scheduling algorithm，CSA）。在CSA中，靜態(tài)傳感節(jié)點(diǎn)根據(jù)鄰居靜態(tài)傳感節(jié)點(diǎn)的信息，發(fā)現(xiàn)靜態(tài)傳感節(jié)點(diǎn)的覆蓋盲區(qū)和估計(jì)移動傳感節(jié)點(diǎn)的停留位置，廣播通知移動傳感節(jié)點(diǎn)。同時建立移動傳感節(jié)點(diǎn)的移動優(yōu)化模型，分布式求解該優(yōu)化模型，獲得異構(gòu)移動傳感節(jié)點(diǎn)的分布式移動策略，修補(bǔ)覆蓋盲區(qū)，從而保證最大網(wǎng)絡(luò)覆蓋，盡可能提高網(wǎng)絡(luò)生存時間和降低算法的時間復(fù)雜度。

2 網(wǎng)絡(luò)模型和算法設(shè)計(jì)

在CSA中作出如下假設(shè)。

（1）在二維的無線傳感網(wǎng)中，同時存在靜態(tài)傳感節(jié)點(diǎn)、移動傳感節(jié)點(diǎn)和靜態(tài)sink節(jié)點(diǎn)。移動傳感節(jié)點(diǎn)可移動到監(jiān)控區(qū)域的任一位置。

（2）傳感節(jié)點(diǎn)的感知覆蓋異構(gòu)，即每一個傳感節(jié)點(diǎn)的感知覆蓋半徑不一致。

（3）傳感節(jié)點(diǎn)通過 GPS、北斗等衛(wèi)星定位模塊或其他定位算法，獲知自身的位置坐標(biāo)。

（4）靜態(tài)傳感節(jié)點(diǎn)可處于工作狀態(tài)或者睡眠狀態(tài)。處于工作狀態(tài)的傳感節(jié)點(diǎn)定時感知數(shù)據(jù)，并將數(shù)據(jù)發(fā)送給sink節(jié)點(diǎn)。

（5）傳感節(jié)點(diǎn)具有相同的通信半徑和初始能量，且采用如下數(shù)據(jù)發(fā)送和接收能耗計(jì)算式計(jì)算自身能耗。

其中，Efa表示節(jié)點(diǎn)數(shù)據(jù)發(fā)送能耗，Ejie表示節(jié)點(diǎn)數(shù)據(jù)接收能耗，Dataij表示傳感節(jié)點(diǎn)i需要發(fā)送給鄰居傳感節(jié)點(diǎn)j的數(shù)據(jù)量，Eelec表示數(shù)據(jù)處理能耗參數(shù)，εfs表示數(shù)據(jù)發(fā)送能耗參數(shù)，dij表示傳感節(jié)點(diǎn)i到鄰居傳感節(jié)點(diǎn)j的距離。

傳感節(jié)點(diǎn)隨機(jī)分布在監(jiān)測區(qū)域內(nèi)且需要獲知自身的位置，如圖1所示。每一個傳感節(jié)點(diǎn)具有不同的感知半徑。當(dāng)網(wǎng)絡(luò)運(yùn)行后，靜態(tài)傳感節(jié)點(diǎn)分析周圍鄰居傳感節(jié)點(diǎn)的位置和剩余能量狀態(tài)，判斷是否存在覆蓋盲區(qū)。采用少量的移動傳感節(jié)點(diǎn)修補(bǔ)覆蓋盲區(qū)，從而提高感知覆蓋和網(wǎng)絡(luò)生存時間。但是CSA仍需要解決以下3個問題：靜態(tài)傳感節(jié)點(diǎn)如何根據(jù)鄰居傳感節(jié)點(diǎn)的位置、剩余能量等信息，判斷其周圍是否存在覆蓋盲區(qū)，并估計(jì)移動傳感節(jié)點(diǎn)的停留位置；如何根據(jù)停留位置，建立移動傳感節(jié)點(diǎn)的覆蓋調(diào)度模型；如何分布式求解覆蓋調(diào)度模型，從而移動傳感節(jié)點(diǎn)可移動到合適位置，修補(bǔ)覆蓋盲區(qū)，提高網(wǎng)絡(luò)生存時間。這3個問題的具體解決如下。

2.1 停留位置計(jì)算

當(dāng)網(wǎng)絡(luò)運(yùn)行后，主要存在兩種覆蓋盲區(qū)的生成情況。一種是傳感節(jié)點(diǎn)的能量耗盡，則其負(fù)責(zé)的覆蓋區(qū)域出現(xiàn)覆蓋盲區(qū)，此時直接將該傳感節(jié)點(diǎn)的位置作為移動傳感節(jié)點(diǎn)的停留位置。另一種是由于傳感節(jié)點(diǎn)位置分布的隨機(jī)性，傳感節(jié)點(diǎn)部署后出現(xiàn)覆蓋盲區(qū)，此時采用如下方法確定移動傳感節(jié)點(diǎn)的可選停留位置。

圖1 CSA原理

當(dāng)傳感節(jié)點(diǎn)部署后，通過與鄰居傳感節(jié)點(diǎn)通信，獲知鄰居傳感節(jié)點(diǎn)的位置、感知半徑等信息，如圖2所示。根據(jù)自身感知半徑，在自身感知圓弧上確定間隔相同的Nhu個點(diǎn)位置，其中Nhu表示圓弧上計(jì)算點(diǎn)個數(shù)，選擇感知半徑相交的鄰居傳感節(jié)點(diǎn)位置，并計(jì)算Nhu個點(diǎn)是否被鄰居傳感節(jié)點(diǎn)覆蓋。即：

其中，chu(i,j)表示與自身節(jié)點(diǎn)j的圓弧上第i個點(diǎn)是否被鄰居傳感節(jié)點(diǎn)覆蓋的標(biāo)識符。表示覆蓋，否則表示不覆蓋。表示圓弧上第i個點(diǎn)的位置，表示鄰居傳感節(jié)點(diǎn)av的位置坐標(biāo)，表示鄰居傳感節(jié)點(diǎn)av的感知半徑，Sj表示與自身節(jié)點(diǎn)j的感知半徑相交的鄰居傳感節(jié)點(diǎn)集合，表示兩位置的距離。根據(jù)Nhu個點(diǎn)的狀態(tài)，合并所有標(biāo)識符為0的相鄰位置，可獲得多個未覆蓋的弧及其兩端點(diǎn)位置。

如果靜態(tài)傳感節(jié)點(diǎn)存在未覆蓋的弧，其兩端頂點(diǎn)為A和B，坐標(biāo)分別為和則圖2中C點(diǎn)的坐標(biāo)滿足以下計(jì)算式：

圖2 靜態(tài)傳感節(jié)點(diǎn)的移動傳感節(jié)點(diǎn)停留位置選擇

其中，rC表示圓C的半徑。式（4）減式（5），可得：

將式（6）代入式（4），并令，求解得：

根據(jù)式（6）可得和，即C點(diǎn)的兩種可能性和 (根據(jù)兩點(diǎn)可選坐標(biāo)，分別計(jì)算到自身圓點(diǎn)D的距離且

當(dāng)自身節(jié)點(diǎn)未覆蓋弧的角度0 ≤θL≤ π ，則選擇作為自身節(jié)點(diǎn)期望的移動傳感節(jié)點(diǎn)位置，否則選擇作為自身節(jié)點(diǎn)期望的移動傳感節(jié)點(diǎn)位置。如果存在多個不連續(xù)的未覆蓋弧，則分別計(jì)算這些弧所對應(yīng)的移動傳感節(jié)點(diǎn)位置，即可估計(jì)移動傳感節(jié)點(diǎn)的位置。

2.2 覆蓋調(diào)度模型建立

當(dāng)覆蓋盲區(qū)不能被靜態(tài)傳感節(jié)點(diǎn)覆蓋時，此時需要移動傳感節(jié)點(diǎn)移動修復(fù)該區(qū)域。令當(dāng)前移動傳感節(jié)點(diǎn)的數(shù)量為Nm，移動傳感節(jié)點(diǎn)的初始位置為pm=(xm,ym)，新的停留位置則移動傳感節(jié)點(diǎn)新的位置區(qū)域覆蓋率增量Δc overp為：

其中，Xi表示負(fù)責(zé)計(jì)算停留位置的傳感節(jié)點(diǎn)i和其處于工作狀態(tài)鄰居傳感節(jié)點(diǎn)的位置集合，表示根據(jù)Xi中傳感節(jié)點(diǎn)位置的區(qū)域覆蓋率。為方便計(jì)算覆蓋率，如圖 3所示，以傳感節(jié)點(diǎn)i的自身位置為中心，將周圍區(qū)域分解成多個網(wǎng)格。如果該區(qū)域網(wǎng)格中心在處于工作狀態(tài)的傳感節(jié)點(diǎn)的感知覆蓋區(qū)域內(nèi)，則該網(wǎng)格被覆蓋，即：

其中，cgv(Xi)表示集合Xi下網(wǎng)格gv是否被覆蓋的標(biāo)識符，則區(qū)域覆蓋率的計(jì)算式為：

其中，ngrid表示網(wǎng)格的個數(shù)。

移動傳感節(jié)點(diǎn)從初始位置移動到新位置的路程為：

圖3 傳感節(jié)點(diǎn)的覆蓋計(jì)算方法

需要讓所有移動傳感節(jié)點(diǎn)新的位置區(qū)域覆蓋率增長最多且移動路程最短，則獲得如下目標(biāo)函數(shù)：

根據(jù)上述的多目標(biāo)問題，建立以下優(yōu)化模型：

其中，vi,j表示一個移動傳感節(jié)點(diǎn)i是否移動到該集合中位置j的標(biāo)識符。當(dāng)時，該節(jié)點(diǎn)將移動并停留在該位置上，否則不移動。式（16）表示移動傳感節(jié)點(diǎn)從當(dāng)前位置移動到新位置的路程，式（17）表示當(dāng)前移動傳感節(jié)點(diǎn)的數(shù)量為Nm，式（18）表示同一個移動傳感節(jié)點(diǎn)只能移動到某一個固定位置，式（19）表示不同的移動傳感節(jié)點(diǎn)不能移動到同一個位置，則移動傳感節(jié)點(diǎn)的覆蓋調(diào)度問題轉(zhuǎn)化成匹配問題。

2.3 算法設(shè)計(jì)

覆蓋調(diào)度模型——式（15）可采用遺傳算法、粒子群算法等人工智能算法求解該優(yōu)化模型，但是上述算法是集中式算法，需要能收集所有傳感節(jié)點(diǎn)的算法處理中心，且計(jì)算量較大，因此采用包括靜態(tài)傳感節(jié)點(diǎn)和移動傳感節(jié)點(diǎn)的啟發(fā)式方法求解該優(yōu)化模型，獲得較優(yōu)方案，具體 CSA設(shè)計(jì)如下。

設(shè)第i類生產(chǎn)設(shè)備的第k臺機(jī)器在一個工作日內(nèi)用于生產(chǎn)第j種零件的時間為xikj(k=1,2,…,pi)．類似地，對每一臺設(shè)備，被分配用于生產(chǎn)所有零件的工作時間總和為1，即有約束條件:

在CSA中，靜態(tài)傳感節(jié)點(diǎn)、移動傳感節(jié)點(diǎn)和sink節(jié)點(diǎn)分別執(zhí)行各自不同的算法。sink節(jié)點(diǎn)定時發(fā)送盲區(qū)計(jì)算分組和路由信息分組，并通過多跳傳輸收集所有傳感節(jié)點(diǎn)的感知數(shù)據(jù)。靜態(tài)傳感節(jié)點(diǎn)完成程序初始化后，監(jiān)聽不同的分組，并判斷屬于不同的情況，執(zhí)行不同的程序，是一個事情驅(qū)動的算法。如圖4所示，具體實(shí)現(xiàn)步驟如下。

步驟 1 網(wǎng)絡(luò)啟動后，設(shè)置定時時間。定時時間到后發(fā)送包含自身位置、感知半徑、剩余能量等狀態(tài)信息的節(jié)點(diǎn)信息分組。

步驟 2 接收所有鄰居傳感節(jié)點(diǎn)的位置、感知半徑、剩余能量等狀態(tài)信息，存儲到鄰居傳感節(jié)點(diǎn)的狀態(tài)信息表中。

步驟3 如果接收sink節(jié)點(diǎn)的盲區(qū)計(jì)算分組，則根據(jù)所有鄰居靜態(tài)傳感節(jié)點(diǎn)的位置，判斷其弧是否全覆蓋，如果其弧未全覆蓋，計(jì)算未覆蓋弧中連續(xù)子弧的數(shù)量NL和每一個子弧的兩個端點(diǎn)位置坐標(biāo)，根據(jù)式（7）、式（8）計(jì)算移動傳感節(jié)點(diǎn)位置的兩種可能，根據(jù)子弧的角度確定每一個子弧所對應(yīng)的移動傳感節(jié)點(diǎn)位置。計(jì)算需要移動傳感節(jié)點(diǎn)停留的可選位置坐標(biāo)和位置權(quán)重，向未盲區(qū)計(jì)算的鄰居傳感節(jié)點(diǎn)轉(zhuǎn)發(fā)盲區(qū)計(jì)算分組。

步驟 4 如果接收到鄰居傳感節(jié)點(diǎn)的能量失效分組，獲知該鄰居傳感節(jié)點(diǎn)的位置、感知半徑等信息。計(jì)算需要移動傳感節(jié)點(diǎn)停留的位置坐標(biāo)和位置權(quán)重。

步驟 5 如果存在到移動傳感節(jié)點(diǎn)的路徑且需要發(fā)送停留位置，則將包含有停留位置、權(quán)值等信息的移動傳感節(jié)點(diǎn)請求分組多跳傳輸給移動傳感節(jié)點(diǎn)。

步驟 6 如果接收到移動傳感節(jié)點(diǎn)的路由查詢分組，則記錄到該移動傳感節(jié)點(diǎn)的路徑。判斷路由查詢分組的跳數(shù)。當(dāng)完成m跳后，則不轉(zhuǎn)發(fā)該分組，否則轉(zhuǎn)發(fā)該分組。

步驟 7 如果接收到移動傳感節(jié)點(diǎn)的位置確認(rèn)分組或位置取消分組，則廣播通知其周圍的其他靜態(tài)傳感節(jié)點(diǎn)。

步驟 8 如果接收到靜態(tài)傳感節(jié)點(diǎn)的位置確認(rèn)分組，則考慮該位置停留移動傳感節(jié)點(diǎn)。如果接收到靜態(tài)傳感節(jié)點(diǎn)的位置取消分組，則考慮該位置沒有停留移動傳感節(jié)點(diǎn)，重新判斷其弧是否全覆蓋。如果其弧未全覆蓋，更新移動傳感節(jié)點(diǎn)位置和其權(quán)值。

圖4 CSA的靜態(tài)傳感節(jié)點(diǎn)的工作流程

網(wǎng)絡(luò)啟動后，移動傳感節(jié)點(diǎn)根據(jù)靜態(tài)傳感節(jié)點(diǎn)的位置信息分組，選擇并移動到目標(biāo)位置。如圖5所示，具體實(shí)現(xiàn)步驟如下。

圖5 CSA的移動傳感節(jié)點(diǎn)的工作流程

步驟1 初始化，并獲知自身位置。

步驟2 定時向周圍傳感節(jié)點(diǎn)發(fā)送自身的路由信息分組。

步驟 3 如果接收到傳感節(jié)點(diǎn)的停留位置坐標(biāo)和位置權(quán)重，則將該分組信息添加到可選位置信息表中。

步驟4 如果停留在初始位置，則直接向該位置移動，跳到步驟5，否則根據(jù)位置信息表中的信息，計(jì)算每一個位置的移動權(quán)值并比較自身位置的位置權(quán)值。如果存在大于自身位置權(quán)值且具有最大移動權(quán)值的位置，選擇和移動到該位置，并將位置確認(rèn)分組發(fā)送給對應(yīng)的靜態(tài)傳感節(jié)點(diǎn)，否則仍停留在原位置。如果在移動過程中接收到新的位置信息分組，則更新位置信息表，重新計(jì)算新位置的移動權(quán)值其中Li′表示已經(jīng)移動的距離，表示當(dāng)前最新位置到可選位置信息表中的距離。如果大于當(dāng)前目標(biāo)位置的移動權(quán)值，則選擇新位置作為移動目標(biāo)位置，將位置確認(rèn)分組和位置取消分組發(fā)送給對應(yīng)的靜態(tài)傳感節(jié)點(diǎn)。

步驟 5 移動和停留在當(dāng)前目標(biāo)位置，感知和發(fā)送自身數(shù)據(jù)，轉(zhuǎn)發(fā)其他靜態(tài)傳感節(jié)點(diǎn)數(shù)據(jù)。

如圖4和圖5所示，CSA算法是一個分布式算法，其時間復(fù)雜度分析主要是分析靜態(tài)傳感節(jié)點(diǎn)和移動傳感節(jié)點(diǎn)的時間復(fù)雜度。靜態(tài)傳感節(jié)點(diǎn)主要是根據(jù)每一個鄰居傳感節(jié)點(diǎn)的信息，計(jì)算可選位置坐標(biāo)和位置權(quán)重，即其時間復(fù)雜度為，其中ni表示傳感節(jié)點(diǎn)i的鄰居傳感節(jié)點(diǎn)個數(shù)。移動傳感節(jié)點(diǎn)主要是根據(jù)接收到的靜態(tài)傳感節(jié)點(diǎn)停留位置信息分組，選擇和移動到目標(biāo)位置，即其時間復(fù)雜度為，其中np表示移動傳感節(jié)點(diǎn)接收到的期待停留位置個數(shù)，因此CSA算法對時間復(fù)雜度的要求不高。在消息交互過程中，由于靜態(tài)傳感節(jié)點(diǎn)的狀態(tài)信息和路由查詢、移動傳感節(jié)點(diǎn)路由信息等信息可整合到路由算法的消息分組中，且位置確認(rèn)分組、位置取消分組、能量失效分組等消息分組是根據(jù)發(fā)生的事件選擇發(fā)送，因此CSA的消息開銷不大。

3 算法仿真

3.1 仿真參數(shù)選擇和比較算法

在仿真中，只考慮無線傳感網(wǎng)感知數(shù)據(jù)的無線通信能耗，不考慮信息分組傳輸能耗、數(shù)據(jù)計(jì)算能耗等其他能耗。根據(jù)上述算法分析，采用MATLAB R2014a軟件，編寫M語言程序仿真實(shí)現(xiàn)不考慮移動傳感節(jié)點(diǎn)算法（Mno）、MNode[8]、MGrid[14]和CSA 4種算法，并比較各算法性能參數(shù)。其中，MNode算法讓移動傳感節(jié)點(diǎn)選擇最近的失效節(jié)點(diǎn)位置作為其停留位置。MGrid算法將監(jiān)控區(qū)域劃分成多個大小相同的網(wǎng)格，讓移動傳感節(jié)點(diǎn)選擇存在覆蓋盲區(qū)的網(wǎng)格中心停留。即在仿真實(shí)驗(yàn)中隨機(jī)均勻產(chǎn)生[50 m, 150 m]區(qū)間的靜態(tài)傳感節(jié)點(diǎn)感知半徑，隨機(jī)均勻產(chǎn)生監(jiān)控區(qū)域內(nèi)傳感節(jié)點(diǎn)的位置分布，選擇分布式貪婪算法（disturbed greedy algorithm，DGA）[8]調(diào)度靜態(tài)傳感節(jié)點(diǎn)的工作狀態(tài)，選擇分布式Bellman_Ford算法[17]作為傳感節(jié)點(diǎn)的數(shù)據(jù)路由算法，考慮移動傳感節(jié)點(diǎn)可移動修復(fù)覆蓋盲區(qū)，并采用以下參數(shù)實(shí)現(xiàn)算法仿真，輸出網(wǎng)絡(luò)生存時間、區(qū)域覆蓋率、存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)、平均靜態(tài)傳感節(jié)點(diǎn)能耗等性能參數(shù)值：監(jiān)測區(qū)域的長和寬均為1 000 m，傳感節(jié)點(diǎn)的最大通信半徑為200 m，移動傳感節(jié)點(diǎn)的感知半徑為 200 m，傳感節(jié)點(diǎn)個數(shù)為100，一次數(shù)據(jù)收集周期的傳感節(jié)點(diǎn)感知數(shù)據(jù)量為1 Mbit，初始能量Einital為1 000 J，數(shù)據(jù)處理能耗參數(shù)Eelec為50 nJ/bit，數(shù)據(jù)發(fā)送能耗參數(shù)εfs為100 pJ/(bit·m2)，圓弧上點(diǎn)個數(shù)Nhu為 50。其中定義一個數(shù)據(jù)收集周期（data collection period，DCP）表示 sink節(jié)點(diǎn)收集完監(jiān)控區(qū)域內(nèi)處于工作狀態(tài)的所有傳感節(jié)點(diǎn)1 Mbit數(shù)據(jù)所需要的時間。x%區(qū)域覆蓋的網(wǎng)絡(luò)生存時間定義為網(wǎng)絡(luò)啟動后，傳感節(jié)點(diǎn)保持x%以上區(qū)域覆蓋的DCP個數(shù)。區(qū)域覆蓋率定義為處于工作狀態(tài)的靜態(tài)傳感節(jié)點(diǎn)和移動傳感節(jié)點(diǎn)覆蓋面積和監(jiān)控區(qū)域面積的比值。存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)定義為網(wǎng)絡(luò)啟動到當(dāng)前時間，處于工作和睡眠狀態(tài)的靜態(tài)傳感節(jié)點(diǎn)個數(shù)。平均靜態(tài)傳感節(jié)點(diǎn)能耗定義為靜態(tài)傳感節(jié)點(diǎn)的總能耗與靜態(tài)傳感節(jié)點(diǎn)個數(shù)和 DCP個數(shù)的比值。

3.2 仿真結(jié)果分析

采用第 3.1節(jié)的仿真參數(shù)和移動傳感節(jié)點(diǎn)個數(shù)20，分別計(jì)算Mno、MNode、MGrid和CSA 4種算法的區(qū)域覆蓋率和存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)，獲得圖6和圖7。

圖6 區(qū)域覆蓋率的變化曲線

圖7 存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)的變化曲線

CSA保持相同區(qū)域覆蓋率的 DCP個數(shù)高于Mno、MNode和MGrid算法，如圖6所示。這是因?yàn)樵谝苿觽鞲泄?jié)點(diǎn)的調(diào)度中，CSA讓移動傳感節(jié)點(diǎn)停留在失效節(jié)點(diǎn)的位置，修復(fù)因節(jié)點(diǎn)失效引起的覆蓋盲區(qū)，讓移動傳感節(jié)點(diǎn)停留在靜態(tài)傳感節(jié)點(diǎn)計(jì)算的可選位置，修復(fù)因節(jié)點(diǎn)位置分布出現(xiàn)的覆蓋盲區(qū)，盡可能讓移動傳感節(jié)點(diǎn)停留在合適的位置，同時在保證最大化覆蓋的情況下提高網(wǎng)絡(luò)生存時間。Mno算法沒有考慮移動傳感節(jié)點(diǎn)，沒有移動傳感節(jié)點(diǎn)的修復(fù)功能，因此相同區(qū)域覆蓋率的DCP個數(shù)最低。MGrid算法只是選擇網(wǎng)格中心的位置，可選位置有限，MNode算法選擇失效節(jié)點(diǎn)的位置，只是考慮覆蓋盲區(qū)出現(xiàn)的一個方面。因此，Mno、MNode和MGrid算法的網(wǎng)絡(luò)生存時間比CSA算法的網(wǎng)絡(luò)生存時間低。而且由于移動傳感節(jié)點(diǎn)移動覆蓋的效果較好，當(dāng)覆蓋率第一次下降時，通過移動修復(fù)，其網(wǎng)絡(luò)覆蓋率重新達(dá)到100%。因此其覆蓋率曲線是上下起伏。

隨著 DCP個數(shù)的增加，靜態(tài)傳感節(jié)點(diǎn)因能量耗盡而死亡，因此各個算法的存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)隨之下降，如圖7所示。但是除了一小段時間，MNode的存活靜態(tài)傳感節(jié)點(diǎn)個數(shù)高于其他3個算法，在大多數(shù)時間內(nèi)，CSA算法因移動傳感節(jié)點(diǎn)停留在適合的位置，調(diào)度靜態(tài)傳感節(jié)點(diǎn)工作，其平均節(jié)點(diǎn)能耗較少，存活的傳感節(jié)點(diǎn)個數(shù)大于Mno、MNode、MGrid算法。

最后，選擇移動傳感節(jié)點(diǎn)個數(shù)5、10、15、20、25、30，隨機(jī)產(chǎn)生10個均勻分布的拓?fù)浣Y(jié)構(gòu)。在仿真過程中，由于靜態(tài)傳感節(jié)點(diǎn)隨機(jī)分布，靜態(tài)傳感節(jié)點(diǎn)的初始位置沒有覆蓋整個監(jiān)控區(qū)域，Mno、MNode、MGrid算法只考慮到局部信息，較難覆蓋整個監(jiān)控區(qū)域。雖然CSA能修復(fù)傳感節(jié)點(diǎn)分布的覆蓋盲區(qū)，但是很難與上述3個算法比較。因此計(jì)算Mno、MNode、MGrid、CSA算法的 90%區(qū)域覆蓋的網(wǎng)絡(luò)生存時間和平均節(jié)點(diǎn)能耗，取其平均值作為仿真結(jié)果值。

保持90%以上的區(qū)域覆蓋下CSA的網(wǎng)絡(luò)生存時間比Mno、MNode和MGrid算法的網(wǎng)絡(luò)生存時間長，如圖8所示。Mno算法沒有考慮移動傳感節(jié)點(diǎn)。在MNode算法中，移動傳感節(jié)點(diǎn)選擇距離最近的能量失效節(jié)點(diǎn)移動。在MGrid算法中，移動傳感節(jié)點(diǎn)選擇距離最近且具有覆蓋盲區(qū)的網(wǎng)格中心位置移動。這3個算法只是考慮覆蓋的某一個方面，而CSA同時考慮能量失效節(jié)點(diǎn)和傳感節(jié)點(diǎn)分布所引起的覆蓋盲區(qū)，讓移動傳感節(jié)點(diǎn)選擇合適的停留位置停留，從而其網(wǎng)絡(luò)生存時間略高于Mno、MNode和MGrid算法。

圖8 90%區(qū)域覆蓋的網(wǎng)絡(luò)生存時間比較

圖9 90%區(qū)域覆蓋的平均靜態(tài)傳感節(jié)點(diǎn)能耗比較

如圖9所示，Mno算法只考慮靜態(tài)傳感節(jié)點(diǎn)工作，其平均靜態(tài)傳感節(jié)點(diǎn)能耗較高，MGrid算法的移動傳感節(jié)點(diǎn)停留位置不夠理想，網(wǎng)絡(luò)生存時間相對較短，其平均靜態(tài)傳感節(jié)點(diǎn)能耗較高。MNode和 CSA算法的平均靜態(tài)傳感節(jié)點(diǎn)能耗較低。當(dāng)移動傳感節(jié)點(diǎn)個數(shù)為20、25和30時，網(wǎng)絡(luò)中移動傳感節(jié)點(diǎn)數(shù)量較多，CSA充分利用移動傳感節(jié)點(diǎn)修復(fù)兩種覆蓋盲區(qū)，網(wǎng)絡(luò)生存時間較高，其平均靜態(tài)傳感節(jié)點(diǎn)能耗小于MNode算法。因此90%區(qū)域覆蓋下，CSA的平均靜態(tài)傳感節(jié)點(diǎn)能耗小于Mno、MNode和MGrid算法的平均靜態(tài)傳感節(jié)點(diǎn)能耗。

4 結(jié)束語

本文提出了一種優(yōu)化網(wǎng)絡(luò)生存時間的移動傳感節(jié)點(diǎn)覆蓋調(diào)度算法（CSA）。首先，提出算法假設(shè)。提出移動傳感節(jié)點(diǎn)覆蓋調(diào)度的基本原理，具體包括停留位置的估計(jì)、覆蓋調(diào)度模型建立和啟發(fā)式求解方法。其次，提出CSA的實(shí)現(xiàn)，包括sink節(jié)點(diǎn)、移動傳感節(jié)點(diǎn)和靜態(tài)傳感節(jié)點(diǎn)的實(shí)現(xiàn)步驟。最后給出算法的仿真參數(shù)，采用分布式Bellman_Ford算法實(shí)現(xiàn)數(shù)據(jù)路由，采用DGA算法實(shí)現(xiàn)靜態(tài)傳感節(jié)點(diǎn)的覆蓋調(diào)度，仿真比較Mno、MNode、MGrid算法和CSA的性能。

總之，相比 Mno、MNode和 MGrid算法，CSA提高了區(qū)域覆蓋率和靜態(tài)傳感節(jié)點(diǎn)存活個數(shù)。不管移動傳感節(jié)點(diǎn)個數(shù)如何變化，在保持相同的區(qū)域覆蓋率下，CSA提高了網(wǎng)絡(luò)生存時間和降低了平均靜態(tài)傳感節(jié)點(diǎn)能耗。但是CSA只是選擇啟發(fā)式算法求解覆蓋調(diào)度模型，其移動傳感節(jié)點(diǎn)的位置選擇只是當(dāng)前移動方案的較優(yōu)解，因此下一個階段目標(biāo)是采用分布式最優(yōu)化方法求解覆蓋調(diào)度模型，獲得移動傳感節(jié)點(diǎn)的停留位置選擇最優(yōu)方案。

參考文獻(xiàn)：

[1]卓琨, 張衡陽, 鄭博, 等.無人機(jī)自組網(wǎng)研究進(jìn)展綜述[J].電信科學(xué), 2015, 31(4)： 134-144.ZHUO K, ZHANG H Y, ZHENG B, et al.Progress of UAV Ad Hoc network： a survey[J].Telecommunications Science, 2015,31(4)： 134-144.

[2]魏穎琪, 林瑋平, 李穎.物聯(lián)網(wǎng)智能終端技術(shù)研究[J].電信科學(xué), 2015, 31(8)： 146-152.WEI Y Q, LIN W P, LI Y.Study on key technologies of intelligent IoT device[J].Telecommunications Science, 2015, 31(8)：146-152

[3]肖清旺, 王錦華, 朱易翔.物聯(lián)網(wǎng)智能終端設(shè)備識別方法[J].電信科學(xué), 2017, 33(2)： 3-8.XIAO Q W, WANG J H, ZHU Y X.Intelligent terminal device identification method of internet of things[J].Telecommunications Science, 2017, 33(2)： 3-8.

[4]CASTILLO I D, TOBAJAS F, ESPER CHAIN R, et al.Hardware platform for wide-area vehicular sensor networks with mobile nodes[J].Vehicular Communications, 2016, 3(1)： 21-30.

[5]馮劍, 王平陽, 王琳, 等.基于能量獲取的無線通信系統(tǒng)研究[J].電信科學(xué), 2015, 31(2)： 124-131.FENG J, WANG P Y, WANG L, et al.Research on energy harvesting communication system[J].Telecommunications Science, 2015, 31(2)： 124-131.

[6]SINGH A, ROSSI A.A genetic algorithm based exact approach for lifetime maximization of directional sensor networks[J].Ad Hoc Networks, 2013, 11(3)： 1006-1021.

[7]IDREES A K, DESCHINKEL K, SALOMON M, et al.Distributed lifetime coverage optimization protocol in wireless sensor networks[J].The Journal of Supercomputing, 2015, 71(12)：4578-4593.

[8]AHMED M K, WALID O.Mobility-assisted minimum connected cover in a wireless sensor network[J].Journal of Parallel and Distributed Computing, 2012, 72(7)： 827-837.

[9]BARA A A, ENAN A K, SUAT O, et al.A multi-objective disjoint set covers for reliable lifetime maximization of wireless sensor networks[J].Wireless Personal Communications, 2015,81(2)： 819-838.

[10]李明.基于差分算法的異構(gòu)無線傳感器網(wǎng)絡(luò)多重覆蓋節(jié)點(diǎn)調(diào)度方案[J].傳感技術(shù)學(xué)報(bào), 2012, 25(6)： 826-830.LI M.A weighted multiple coverage node scheduling scheme based on differential evolution algorithm for heterogeneous sensor networks[J].Chinese Journal of Sensors and Actuators,2012, 25(6)： 826-830.

[11]杜曉玉, 孫力娟, 郭劍, 等.異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J].電子與信息學(xué)報(bào), 2014, 36(3)： 696-702.DU X Y, SUN L J, GUO J, et al.Coverage optimization algorithm for heterogeneous WSN[J].Journal of Electronics & Information Technology, 2014, 36(3)： 696-702.

[12]KHEDR A M, OSAMY W.Minimum connected cover of a query region in heterogeneous wireless sensor networks[J].Information Sciences, 2013, 223(2)： 153-163.

[13]孫力娟, 魏靜, 郭劍, 等.面向異構(gòu)無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)調(diào)度算法[J].電子學(xué)報(bào), 2014, 42(10)： 1907-1912.SUN L J, WEI J, GUO J, et al.Node scheduling algorithm for heterogeneous wireless sensor networks[J].Acta Electronica Sinica, 2014, 42(10)： 1907-1912.

[14]NUDURUPATIA D P, SINGHA R K.Enhancing coverage ratio using mobility in heterogeneous wireless sensor network[C]//International Conference on Computational Intelligence： Modeling Techniques and Applications (CIMTA), Sept 27, 2013, Kalyani, India.Piscataway： IEEE Press, 2013：538-545.

[15]李明, 石為人.虛擬力導(dǎo)向差分算法的異構(gòu)移動傳感網(wǎng)絡(luò)覆蓋策略[J].儀器儀表學(xué)報(bào), 2011, 32(5)： 1143-1150.LI M, SHI W R.Virtual force-directed differential evolution algorithm based coverage-enhancing algorithm for heterogeneous mobile sensor networks[J].Chinese Journal of Scientific Instrument, 2011, 32(5)： 1143-1150.

[16]劉軍, 程良倫, 王建華, 等.一種混合異構(gòu)傳感網(wǎng)的覆蓋洞修補(bǔ)算法[J].控制與決策, 2015, 30(11)： 2080-2084.LIU J, CHENG L L, WANG J H, et al.A coverage hole repair algorithm for hybrid heterogeneous sensor networks[J].Control and Decision, 2015, 30(11)： 2080-2084.

[17]陳友榮, 王章權(quán), 程菊花, 等.基于最短路徑樹的優(yōu)化生存時間路由算法[J].傳感技術(shù)學(xué)報(bào), 2012, 25(3)： 406-412.CHEN Y R, WANG Z Q, CHENG J H, et al.Lifetime optimized routing algorithm based on shortest path tree[J].Chinese Journal of Sensors and Actuators, 2012, 25(3)： 406-412.