一種優(yōu)化網(wǎng)絡(luò)生存時(shí)間的移動(dòng)傳感節(jié)點(diǎn)覆蓋調(diào)度算法

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2.1 停留位置計(jì)算

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

圖1 CSA原理

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

其中，chu(i,j)表示與自身節(jié)點(diǎn)j的圓弧上第i個(gè)點(diǎn)是否被鄰居傳感節(jié)點(diǎn)覆蓋的標(biāo)識(shí)符。表示覆蓋，否則表示不覆蓋。表示圓弧上第i個(gè)點(diǎn)的位置，表示鄰居傳感節(jié)點(diǎn)av的位置坐標(biāo)，表示鄰居傳感節(jié)點(diǎn)av的感知半徑，Sj表示與自身節(jié)點(diǎn)j的感知半徑相交的鄰居傳感節(jié)點(diǎn)集合，表示兩位置的距離。根據(jù)Nhu個(gè)點(diǎn)的狀態(tài)，合并所有標(biāo)識(shí)符為0的相鄰位置，可獲得多個(gè)未覆蓋的弧及其兩端點(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)的移動(dòng)傳感節(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)期望的移動(dòng)傳感節(jié)點(diǎn)位置，否則選擇作為自身節(jié)點(diǎn)期望的移動(dòng)傳感節(jié)點(diǎn)位置。如果存在多個(gè)不連續(xù)的未覆蓋弧，則分別計(jì)算這些弧所對(duì)應(yīng)的移動(dòng)傳感節(jié)點(diǎn)位置，即可估計(jì)移動(dòng)傳感節(jié)點(diǎn)的位置。

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

當(dāng)覆蓋盲區(qū)不能被靜態(tài)傳感節(jié)點(diǎn)覆蓋時(shí)，此時(shí)需要移動(dòng)傳感節(jié)點(diǎn)移動(dòng)修復(fù)該區(qū)域。令當(dāng)前移動(dòng)傳感節(jié)點(diǎn)的數(shù)量為Nm，移動(dòng)傳感節(jié)點(diǎn)的初始位置為pm=(xm,ym)，新的停留位置則移動(dòng)傳感節(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ū)域分解成多個(gè)網(wǎng)格。如果該區(qū)域網(wǎng)格中心在處于工作狀態(tài)的傳感節(jié)點(diǎn)的感知覆蓋區(qū)域內(nèi)，則該網(wǎng)格被覆蓋，即：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真

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

在仿真中，只考慮無(wú)線傳感網(wǎng)感知數(shù)據(jù)的無(wú)線通信能耗，不考慮信息分組傳輸能耗、數(shù)據(jù)計(jì)算能耗等其他能耗。根據(jù)上述算法分析，采用MATLAB R2014a軟件，編寫(xiě)M語(yǔ)言程序仿真實(shí)現(xiàn)不考慮移動(dòng)傳感節(jié)點(diǎn)算法（Mno）、MNode[8]、MGrid[14]和CSA 4種算法，并比較各算法性能參數(shù)。其中，MNode算法讓移動(dòng)傳感節(jié)點(diǎn)選擇最近的失效節(jié)點(diǎn)位置作為其停留位置。MGrid算法將監(jiān)控區(qū)域劃分成多個(gè)大小相同的網(wǎng)格，讓移動(dò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ù)路由算法，考慮移動(dòng)傳感節(jié)點(diǎn)可移動(dòng)修復(fù)覆蓋盲區(qū)，并采用以下參數(shù)實(shí)現(xiàn)算法仿真，輸出網(wǎng)絡(luò)生存時(shí)間、區(qū)域覆蓋率、存活靜態(tài)傳感節(jié)點(diǎn)個(gè)數(shù)、平均靜態(tài)傳感節(jié)點(diǎn)能耗等性能參數(shù)值：監(jiān)測(cè)區(qū)域的長(zhǎng)和寬均為1 000 m，傳感節(jié)點(diǎn)的最大通信半徑為200 m，移動(dòng)傳感節(jié)點(diǎn)的感知半徑為 200 m，傳感節(jié)點(diǎn)個(gè)數(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)個(gè)數(shù)Nhu為 50。其中定義一個(gè)數(shù)據(jù)收集周期（data collection period，DCP）表示 sink節(jié)點(diǎn)收集完監(jiān)控區(qū)域內(nèi)處于工作狀態(tài)的所有傳感節(jié)點(diǎn)1 Mbit數(shù)據(jù)所需要的時(shí)間。x%區(qū)域覆蓋的網(wǎng)絡(luò)生存時(shí)間定義為網(wǎng)絡(luò)啟動(dòng)后，傳感節(jié)點(diǎn)保持x%以上區(qū)域覆蓋的DCP個(gè)數(shù)。區(qū)域覆蓋率定義為處于工作狀態(tài)的靜態(tài)傳感節(jié)點(diǎn)和移動(dòng)傳感節(jié)點(diǎn)覆蓋面積和監(jiān)控區(qū)域面積的比值。存活靜態(tài)傳感節(jié)點(diǎn)個(gè)數(shù)定義為網(wǎng)絡(luò)啟動(dòng)到當(dāng)前時(shí)間，處于工作和睡眠狀態(tài)的靜態(tài)傳感節(jié)點(diǎn)個(gè)數(shù)。平均靜態(tài)傳感節(jié)點(diǎn)能耗定義為靜態(tài)傳感節(jié)點(diǎn)的總能耗與靜態(tài)傳感節(jié)點(diǎn)個(gè)數(shù)和 DCP個(gè)數(shù)的比值。

3.2 仿真結(jié)果分析

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

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

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

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

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

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

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

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

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

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

本文提出了一種優(yōu)化網(wǎng)絡(luò)生存時(shí)間的移動(dòng)傳感節(jié)點(diǎn)覆蓋調(diào)度算法（CSA）。首先，提出算法假設(shè)。提出移動(dòng)傳感節(jié)點(diǎn)覆蓋調(diào)度的基本原理，具體包括停留位置的估計(jì)、覆蓋調(diào)度模型建立和啟發(fā)式求解方法。其次，提出CSA的實(shí)現(xiàn)，包括sink節(jié)點(diǎn)、移動(dòng)傳感節(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)存活個(gè)數(shù)。不管移動(dòng)傳感節(jié)點(diǎn)個(gè)數(shù)如何變化，在保持相同的區(qū)域覆蓋率下，CSA提高了網(wǎng)絡(luò)生存時(shí)間和降低了平均靜態(tài)傳感節(jié)點(diǎn)能耗。但是CSA只是選擇啟發(fā)式算法求解覆蓋調(diào)度模型，其移動(dòng)傳感節(jié)點(diǎn)的位置選擇只是當(dāng)前移動(dòng)方案的較優(yōu)解，因此下一個(gè)階段目標(biāo)是采用分布式最優(yōu)化方法求解覆蓋調(diào)度模型，獲得移動(dòng)傳感節(jié)點(diǎn)的停留位置選擇最優(yōu)方案。

參考文獻(xiàn)：

[1]卓琨, 張衡陽(yáng), 鄭博, 等.無(wú)人機(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è)備識(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]馮劍, 王平陽(yáng), 王琳, 等.基于能量獲取的無(wú)線通信系統(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ú)線傳感器網(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ú)線傳感器網(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ú)線傳感器網(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)移動(dòng)傳感網(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), 程菊花, 等.基于最短路徑樹(shù)的優(yōu)化生存時(shí)間路由算法[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.