移動(dòng)參考節(jié)點(diǎn)動(dòng)態(tài)路徑最優(yōu)規(guī)劃

張玉強(qiáng)，何涇沙，徐　晶，趙　斌，4，蔡方博

移動(dòng)參考節(jié)點(diǎn)動(dòng)態(tài)路徑最優(yōu)規(guī)劃

張玉強(qiáng)1，3，何涇沙2，3，徐晶1，3，趙斌2，3，4，蔡方博2，3

（1.北京工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，北京100124；2.北京工業(yè)大學(xué)軟件學(xué)院，北京100124；3.北京市物聯(lián)網(wǎng)軟件與系統(tǒng)工程技術(shù)研究中心，北京100124；4.濟(jì)寧學(xué)院計(jì)算機(jī)科學(xué)系，山東濟(jì)寧273155）

在利用移動(dòng)參考節(jié)點(diǎn)對(duì)無(wú)線傳感器網(wǎng)絡(luò)進(jìn)行時(shí)間同步或定位的過(guò)程中，參考節(jié)點(diǎn)的移動(dòng)路徑規(guī)劃，直接影響節(jié)點(diǎn)同步精度、定位精度和能量損耗.將移動(dòng)節(jié)點(diǎn)的移動(dòng)路徑規(guī)劃轉(zhuǎn)化為對(duì)廣播點(diǎn)的選取及廣播點(diǎn)間路徑規(guī)劃，對(duì)應(yīng)數(shù)學(xué)模型為經(jīng)典的選址問(wèn)題和旅行商問(wèn)題.通過(guò)建立兩者的最優(yōu)聯(lián)合數(shù)學(xué)模型，提出利用貪婪算法尋找最優(yōu)的廣播點(diǎn)并獲得最優(yōu)移動(dòng)路徑的方法.仿真結(jié)果表明:該路徑能夠覆蓋整個(gè)網(wǎng)絡(luò)，同時(shí)縮短參考節(jié)點(diǎn)的移動(dòng)距離.

時(shí)間同步；定位；移動(dòng)參考節(jié)點(diǎn)；路徑規(guī)劃；貪婪算法

在移動(dòng)參考節(jié)點(diǎn)的路徑規(guī)劃中，主要涉及2方面因素:節(jié)點(diǎn)的同步或定位精度和能量消耗.在現(xiàn)實(shí)試驗(yàn)環(huán)境中，當(dāng)傳感器節(jié)點(diǎn)靠近移動(dòng)參考節(jié)點(diǎn)的規(guī)劃路徑時(shí)，節(jié)點(diǎn)獲得信號(hào)較強(qiáng)、干擾少、時(shí)間或空間定位精度較高.距離較遠(yuǎn)時(shí)，信號(hào)弱、干擾強(qiáng)、時(shí)間或空間定位精度較低，甚至無(wú)法獲得信號(hào).當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)的分布密集靠近參考節(jié)點(diǎn)移動(dòng)的路徑時(shí)，網(wǎng)絡(luò)的整體精度較高.否則，精度急劇下降［1］.

根據(jù)能量消耗模型［2］，兩節(jié)點(diǎn)間的通信距離與節(jié)點(diǎn)的能耗成平方關(guān)系.在通信過(guò)程中，為了保障通信質(zhì)量，移動(dòng)參考節(jié)點(diǎn)和普通節(jié)點(diǎn)間需要進(jìn)行數(shù)據(jù)交換.節(jié)點(diǎn)在響應(yīng)參考節(jié)點(diǎn)信息時(shí)，隨節(jié)點(diǎn)離移動(dòng)參考節(jié)點(diǎn)間的距離的增大，能量損耗成平方比例增大.因此，在網(wǎng)絡(luò)的同步或節(jié)點(diǎn)的定位過(guò)程中，節(jié)點(diǎn)的通信能耗與移動(dòng)參考節(jié)點(diǎn)間的距離關(guān)系密切，距離越短，整個(gè)網(wǎng)絡(luò)的能量消耗越小.否則，網(wǎng)絡(luò)能耗越大.

目前，對(duì)移動(dòng)參考節(jié)點(diǎn)路徑的規(guī)劃分為靜態(tài)路徑規(guī)劃和動(dòng)態(tài)路徑規(guī)劃2種方式.靜態(tài)路徑規(guī)劃是預(yù)先設(shè)定移動(dòng)曲線，移動(dòng)參考節(jié)點(diǎn)沿此曲線移動(dòng).不考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的分布以及節(jié)點(diǎn)是否有效，移動(dòng)參考節(jié)點(diǎn)都按照預(yù)先規(guī)劃的路徑進(jìn)行移動(dòng)，且不會(huì)發(fā)生改變.其中文獻(xiàn)［3］提出Scan型、Double Scan型和H ILBERT型等3種移動(dòng)路徑.文獻(xiàn)［4］提出移動(dòng)參考節(jié)點(diǎn)的圓形和S形移動(dòng)路徑方法.文獻(xiàn)［5］提出參考節(jié)點(diǎn)的等距螺旋形軌跡移動(dòng)路徑方法.文獻(xiàn)［6］中LTS-MB算法提出參考節(jié)點(diǎn)采用正弦曲線進(jìn)行移動(dòng)的方法.

動(dòng)態(tài)路徑規(guī)劃是根據(jù)節(jié)點(diǎn)的分布以及節(jié)點(diǎn)是否有效等情況，動(dòng)態(tài)調(diào)整移動(dòng)路徑的方法.為移動(dòng)參考節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)路徑規(guī)劃的研究現(xiàn)在較少.在AHLoS算法［7］中提出了一種動(dòng)態(tài)路徑規(guī)劃，首先提出在區(qū)域中選取移動(dòng)參考經(jīng)過(guò)“最優(yōu)節(jié)點(diǎn)”，類似本文中的廣播點(diǎn)，繼而利用旅行商問(wèn)題建立最短距離的最優(yōu)數(shù)學(xué)模型.但是此算法沒有對(duì)廣播點(diǎn)進(jìn)行最優(yōu)規(guī)劃，因而最終的路徑不一定最優(yōu).

本文提出一種移動(dòng)參考節(jié)點(diǎn)的動(dòng)態(tài)路徑規(guī)劃方法（dynamic path planning method for mobile reference nodes，DP-MRN）.本文要求移動(dòng)參考節(jié)點(diǎn)首先采用MRN-CS算法［8］，進(jìn)行靜態(tài)路徑規(guī)劃.參考節(jié)點(diǎn)移動(dòng)一個(gè)周期后，搜集到整個(gè)網(wǎng)絡(luò)區(qū)域中的節(jié)點(diǎn)分布，繼而移動(dòng)參考節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)路徑規(guī)劃.DP-MRN算法將路徑規(guī)劃問(wèn)題轉(zhuǎn)化為聯(lián)合選址問(wèn)題和旅行商問(wèn)題的最優(yōu)數(shù)學(xué)規(guī)劃模型，最后利用貪婪算法進(jìn)行路徑規(guī)劃.

1　廣播點(diǎn)的最優(yōu)選取模型

對(duì)移動(dòng)參考節(jié)點(diǎn)的路徑規(guī)劃，本文首先建立廣播點(diǎn)的最優(yōu)選取模型.

假設(shè)目標(biāo)區(qū)域的傳感器節(jié)點(diǎn)集合為 T=｛1，2，…，M｝，傳感器節(jié)點(diǎn)i和j之間的距離為di，j，所有傳感器節(jié)點(diǎn)（包括參考節(jié)點(diǎn)）的通信半徑為r，建立如下廣播點(diǎn)的最優(yōu)選取模型（optimal acquisition point，OAP）.

式中決策變量xi和yi，j均為0～1變量.當(dāng)xi取值為1，表示將選取傳感器節(jié)點(diǎn)i位置作為廣播點(diǎn)位置；否則，將不選取傳感器節(jié)點(diǎn)i位置作為廣播點(diǎn)位置.當(dāng)yi，j取值為1，表示將在位置i處與傳感器節(jié)點(diǎn)j進(jìn)行通信；否則，將不在位置i處與傳感器節(jié)點(diǎn)j進(jìn)行通信.

該模型的目標(biāo)在于使廣播點(diǎn)總個(gè)數(shù)最小化.第1個(gè)約束要求只能在選取的廣播點(diǎn)處與附件的傳感器通信.第2個(gè)約束要求在一個(gè)移動(dòng)周期內(nèi)與任意傳感器只需要進(jìn)行一次通信即可.第3個(gè)約束要求進(jìn)行通信時(shí)，必須滿足通信距離限制，即只有在通信半徑的節(jié)點(diǎn)才能通信.

廣播點(diǎn)最優(yōu)選取模型是一個(gè)包含不超過(guò)M2+ M個(gè)變量以及M2+M個(gè)約束的0～1線性規(guī)劃問(wèn)題，該問(wèn)題可以采用CPLEX或Matlab等優(yōu)化軟件進(jìn)行有效求解.

該模型的計(jì)算量較大，不適合能量有限的傳感器節(jié)點(diǎn)進(jìn)行運(yùn)算；可以利用具有較強(qiáng)的處理能力的后臺(tái)服務(wù)器，有效地計(jì)算出最優(yōu)廣播點(diǎn)坐標(biāo)，然后傳送給移動(dòng)參考節(jié)點(diǎn).

2　聯(lián)合廣播點(diǎn)選取-最短路徑規(guī)劃模型

廣播點(diǎn)最優(yōu)選取模型（1）中，以最小化廣播點(diǎn)總個(gè)數(shù)為目標(biāo)函數(shù)，并未考慮參考節(jié)點(diǎn)的移動(dòng)路徑最優(yōu)化問(wèn)題.為此，進(jìn)一步提出了考慮參考節(jié)點(diǎn)的最短移動(dòng)路徑的聯(lián)合廣播點(diǎn)選取-最短路徑規(guī)劃模型.

2.1聯(lián)合路徑規(guī)劃模型

為建立聯(lián)合廣播點(diǎn)選取-最短路徑規(guī)劃模型，首先考慮不同廣播點(diǎn)對(duì)最短路徑規(guī)劃的影響.

如果將傳感器節(jié)點(diǎn)i位置和傳感器節(jié)點(diǎn)j位置選取為廣播點(diǎn)，那么其距離di，j將會(huì)出現(xiàn)在最優(yōu)路徑規(guī)劃問(wèn)題中，為此需要考慮所選取廣播點(diǎn)相互之間距離對(duì)最終最優(yōu)路徑的影響.

定義新的決策變量zi，j=xixj，用來(lái)表示是否同時(shí)將傳感器節(jié)點(diǎn)i位置和傳感器節(jié)點(diǎn)j位置都選取為廣播點(diǎn).從而建立如下數(shù)學(xué)模型.

模型（2）中包含二次乘積項(xiàng)，其求解非常困難.為此首先對(duì)二次乘積項(xiàng)的取值進(jìn)行分析.

表1　二次乘積項(xiàng)zi，j的分析Table 1　Analysis of the secondary product items

由此可知，通過(guò)引入如下約束進(jìn)行等價(jià)轉(zhuǎn)化

該約束保證當(dāng)xi和xj同時(shí)為1時(shí)，即傳感器節(jié)點(diǎn)i位置選為廣播點(diǎn)，同時(shí)傳感器節(jié)點(diǎn)j位置也選為廣播點(diǎn)；zi，j不小于1；否則zi，j不小于0.考慮目標(biāo)函數(shù)為最小化加權(quán)的zi，j的和，從而通過(guò)引入該約束可以將模型（3）等價(jià)轉(zhuǎn)化為如下考慮路徑規(guī)劃的最優(yōu)廣播點(diǎn)選取模型（routing based optimal acquisition point，ROAP）.

2.2路徑規(guī)劃最優(yōu)廣播點(diǎn)選取模型

模型（4）為0～1線性規(guī)劃問(wèn)題，該問(wèn)題可以采用CPLEX或Matlab等優(yōu)化軟件進(jìn)行有效求解.

考慮到在最終的最優(yōu)路徑規(guī)劃中往往只包含那些較短的距離，可以引入加權(quán)變換的距離來(lái)重新建立模型（4）.具體而言，引入如下加權(quán)函數(shù)w:R+→R+，其滿足如下性質(zhì):

1）單調(diào)性:當(dāng)d1≥d2時(shí)，

2）邊際遞減:即隨著自變量的增大，w的導(dǎo)數(shù)逐漸變小，即w為凹函數(shù).

w滿足以上性質(zhì)可以保證當(dāng)距離較大時(shí)，其映射后的懲罰仍較大，同時(shí)隨著距離的增大，其懲罰效應(yīng)逐漸減小（因?yàn)檩^大的距離往往不會(huì)出現(xiàn)在最終的最短路徑中，所以其影響應(yīng)該不會(huì)增大）.w可以選為開根號(hào)函數(shù)，例如w=等.

2.3加權(quán)模型

基于加權(quán)距離的方法，可以得到如下模型:

同時(shí)，也可以綜合考慮最小廣播點(diǎn)和最優(yōu)路徑，建立加權(quán)模型

式中θ為0～1的正實(shí)數(shù).

3　仿真實(shí)驗(yàn)

為了驗(yàn)證聯(lián)合廣播點(diǎn)選取-最短路徑規(guī)劃模型（簡(jiǎn)稱聯(lián)合算法）的優(yōu)越性，與 LTS-MB算法和MRN-CS算法進(jìn)行路徑對(duì)比實(shí)驗(yàn)，仿真條件設(shè)置如表2所示.

表2　實(shí)驗(yàn)參數(shù)設(shè)置Table 2　Experimental parameters

聯(lián)合算法采用貪婪算法，部分關(guān)鍵程序如下: while（Leftnum＞0）%尋找當(dāng)前最多覆蓋的節(jié)點(diǎn)

for i=1:datanum

Covernum（i）=0；

for j=1:datanum

Covernum（i）=Covernum（i）+Index（i，j）；

end

end

［maxcovernum，index］=max（Covernum）；%計(jì)算得到最多覆蓋節(jié)點(diǎn)的覆蓋數(shù)量和下標(biāo)

Referencenumber=Referencenumber+1；%更新采樣點(diǎn)數(shù)目

Referencepoint（Referencenumber）=index；%存儲(chǔ)采樣點(diǎn)下標(biāo)

Leftnum=Leftnum-maxcovernum；%更新剩余節(jié)點(diǎn)數(shù)目

for j=1:datanum

if（Index（index，j）==1）%如果第j個(gè)節(jié)點(diǎn)可以被index節(jié)點(diǎn)覆蓋

for k=1:datanum

Index（k，j）=0；%那么其他任意節(jié)點(diǎn)對(duì)該節(jié)點(diǎn)的覆蓋都沒有意義，從而可以設(shè)為0.

end

end

Index（index，j）=0；%從數(shù)據(jù)中刪去已選取的采樣點(diǎn)的覆蓋信息，從而下次循環(huán)不會(huì)再重新選擇其為采樣點(diǎn)

end

end

MRN-CS算法中參考節(jié)點(diǎn)的移動(dòng)路徑如圖2所示.

可見，移動(dòng)參考節(jié)點(diǎn)的路徑形成了一個(gè)閉合曲線.移動(dòng)參考節(jié)點(diǎn)在兩同步點(diǎn)間移動(dòng)的距離為R.移動(dòng)過(guò)程中經(jīng)過(guò)所有的同步點(diǎn)，同時(shí)有且經(jīng)過(guò)1次.

LTS-MB算法的移動(dòng)路徑如圖3所示.

聯(lián)合算法的參考節(jié)點(diǎn)的移動(dòng)路徑如圖4所示.

從圖4中可以看出，區(qū)域中有2個(gè)廣播點(diǎn)之間的路徑最長(zhǎng)，這2個(gè)廣播點(diǎn)是路徑規(guī)劃的起點(diǎn)和終點(diǎn).聯(lián)合算法的數(shù)學(xué)模型實(shí)質(zhì)上是選址問(wèn)題和起止點(diǎn)相同的旅行商問(wèn)題的綜合模型.首先利用貪婪算法最優(yōu)的選取廣播點(diǎn)，繼而選取最短的2個(gè)廣播點(diǎn)中的一個(gè)為起點(diǎn)，繼而通過(guò)貪婪算法尋找最短的廣播點(diǎn)，這造成了終點(diǎn)可能是距離起點(diǎn)最遠(yuǎn)的廣播點(diǎn).

假若不要求移動(dòng)路徑是起止點(diǎn)相同的閉合曲線，那么圖4的最長(zhǎng)線段可以去掉，此時(shí)的路徑將是動(dòng)態(tài)規(guī)劃的最短路徑，否則將為最優(yōu)路徑.繼續(xù)上述假設(shè)，移動(dòng)路徑起止點(diǎn)不相同時(shí)，處于路徑中心廣播點(diǎn)附近的普通節(jié)點(diǎn)的同步周期等于移動(dòng)周期，處在起止廣播點(diǎn)附近的普通節(jié)點(diǎn)同步周期最長(zhǎng)等于2倍的移動(dòng)周期，最短為零.這將使得網(wǎng)絡(luò)中節(jié)點(diǎn)時(shí)鐘偏移可能增大1倍，這將背離研究目的.

通過(guò)3種算法的實(shí)驗(yàn)得到各自的路徑規(guī)劃長(zhǎng)度，結(jié)果如圖5所示.

從圖5中可以看出，聯(lián)合算法路徑長(zhǎng)度最小. LTS-MB算法要求參考節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)中的節(jié)點(diǎn)進(jìn)行3次覆蓋，所以路徑最長(zhǎng).MRN-CS算法因?yàn)椴捎酶采w圓的內(nèi)正六邊形，使用1次覆蓋，路徑長(zhǎng)度居中.在小規(guī)模網(wǎng)絡(luò)，以及網(wǎng)絡(luò)中“空洞”較少時(shí)，該聯(lián)合算法優(yōu)勢(shì)不明顯，以致路徑規(guī)劃所產(chǎn)生的同步精度與所付出的代價(jià)不相符.

4　結(jié)論

1）針對(duì)靜態(tài)路徑規(guī)劃的不足，提出移動(dòng)參考節(jié)點(diǎn)的動(dòng)態(tài)移動(dòng)路徑最優(yōu)規(guī)劃方案.

2）通過(guò)結(jié)合經(jīng)典的選址問(wèn)題和旅行商問(wèn)題，建立廣播點(diǎn)的最優(yōu)選取模型、聯(lián)合廣播點(diǎn)選取-最短路徑規(guī)劃模型以及改進(jìn)后的加權(quán)模型，利用貪婪算法尋找最優(yōu)的廣播點(diǎn)，最終得到移動(dòng)參考節(jié)點(diǎn)的最優(yōu)移動(dòng)路徑.

3）通過(guò)仿真實(shí)驗(yàn)顯示，最優(yōu)移動(dòng)路徑不僅有效覆蓋整個(gè)網(wǎng)絡(luò)，同時(shí)縮短了參考節(jié)點(diǎn)的移動(dòng)距離.

［1］鄭國(guó)強(qiáng)，李建東，周志立.多跳無(wú)線傳感器網(wǎng)絡(luò)的高能效數(shù)據(jù)收集協(xié)議［J］.軟件學(xué)報(bào)，2010，21（9）:2320-2337.

ZHENG G Q，LI J D，ZHOU Z L.Energy-efficient data gathering protocol for multihop wireless sensor networks［J］.Journal of Software，2010，21（9）:2320-2337.（in Chinese）

［2］徐朝農(nóng)，徐勇軍，李曉維.無(wú)線傳感器網(wǎng)絡(luò)時(shí)間同步新技術(shù)［J］.計(jì)算機(jī)研究與發(fā)展，2015，45（1）:138-145.

XU C N，XU Y J，LI X W.New time synchronization techniques for wireless sensor networks［J］.Journal of Computer Research and Development，2015，45（1）:138-145.（in Chinese）

［3］ELSON J，GIROD L，ESTRIN D.Fine-grained network time synchronization using reference broadcasts［J］.ACM SIGOPS Operating Systems Review，2002，36（SI）:147-163.

［4］GANERIWAL S，KUMARR，SRIVASTAVAMB. Timing-syncprotocolforsensornetworks［C］∥Proceedingsofthe1stinternationalconferenceon Embedded networked sensor systems.Los Angeles:ACM，2003:138-149.

［5］PING S.Delay measurement time synchronization for wireless sensor networks［R］.［s.l.］:Intel Research Berkeley Lab，2003.

［6］SICHITIU M L，VEERARITTIPHAN C.Simple，accurate time synchronization for wireless sensor networks［C］∥Wireless Communications and Networking.New Orleans: IEEE，2003，2:1266-1273.

［7］MAR譫TI M，KUSY B，SIMON G，et al.The flooding time synchronization protocol［C］∥Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems.New York:ACM，2004:39-49.

［8］張玉強(qiáng)，何涇沙，徐晶，等.基于移動(dòng)參考節(jié)點(diǎn)的無(wú)線傳感器時(shí)鐘同步方法［J］.通信學(xué)報(bào)，2015，36（11）: 171-180.

ZHANG Y Q，HE J S，XU J，et al.Time synchronization method for wireless sensor networks based on mobile reference nodes［J］.Journal of Communications，2015，36（11）:171-180.（in Chinese）

（責(zé)任編輯楊開英）

Dynamic Optimal Planning of Path of Mobile Nodes

ZHANG Yuqiang1，3，HE Jingsha2，3，XU Jing1，3，ZHAO Bin2，3，4，CAI Fangbo2，3
（1.College of Computer Science，Beijing University of Technology，Beijing 100124，China；2.School of Software Engineering，Beijing University of Technology，Beijing 100124，China；3.Beijing Engineering Research Center for IOT Software and Systems，Beijing 1000124，China；4.Department of Computer Science，Jining University，Jining 273155，Shandong，China）

In the process of time synchronization and location of wireless sensor networks based on mobile reference nodes，the path planning of the reference node directly affects the accuracy and energy loss of the nodes.This paper transforms the path planning of mobile nodes into the selection of broadcast points with the path planning，and sets up a mathematical model based on the problem of location and traveling salesman problem.By establishing the optimal joint mathematical model，a method that uses a greedy algorithm was proposed to find the optimal broadcast point and obtain the optimal path.The simulation experiments were done to validate the performance of the method.Experimental data shows that the mobile path witch through this method can cover the whole network，and significantly shorten the moving distance of the reference node.

time synchronization；localization；mobile reference node；path planning；greedy algorithm

TP 393

A

0254-0037（2016）06-0851-05

10.11936/bjutxb2015070087

2015-07-16

國(guó)家“863”計(jì)劃資助項(xiàng)目（2015AA017204）；北京市自然科學(xué)基金資助項(xiàng)目（4142008）

張玉強(qiáng)（1982—），男，博士研究生，主要從事無(wú)線傳感器網(wǎng)絡(luò)、信息安全方面的研究，E-mail:yuqzhang@emails. bjut.edu.cn

何涇沙（1961—），男，教授，博士生導(dǎo)師，主要從事無(wú)線傳感網(wǎng)技術(shù)、信息安全方面的研究，E-mail:jhe@bjut. edu.cn