無線傳感器網絡多天線移動式數據收集算法

辛強偉，唐云凱，許曉婷

（咸陽師范學院 a.計算機學院，b.資源環(huán)境與歷史文化學院，陜西 咸陽 712000）

無線傳感器網絡（Wireless Sensor Networks,WSN）中節(jié)點通過一跳或多跳的方式將感知數據傳送到Sink。關于Sink的研究在數據收集中有著重要地位，其研究主要包括單一Sink、多Sink以及移動Sink等。單一Sink的WSN可能會存在負載不均衡問題[1-3]。多個Sink因為有多路徑的分流作用，從而減少或避免了熱點節(jié)點的出現，且多個Sink可以減少網絡平均跳數使節(jié)點的能耗降低，從而提高WSN的生存時間[4-8]。

通過多跳將數據傳送到位置固定的Sink有一定的局限。首先，對于特大面積的監(jiān)測區(qū)域，需要大量節(jié)點，成本較大。第二，野外復雜環(huán)境中有些地方不易到達，難以部署節(jié)點或及時更換節(jié)點電池，從而使WSN不連通，網絡分割為若干個連通分支和多個孤立節(jié)點。第三，如果采用隨機部署節(jié)點的方式，當節(jié)點部署密度較小時，節(jié)點分布有時是不均勻的，有可能存在空洞[9]。如果要避免空洞，則需部署大量節(jié)點，但會大幅提高成本[10]。第四，節(jié)點電量耗盡、故障以及人為破壞等原因，會使WSN由連通變?yōu)榉沁B通，導致不能完成監(jiān)測任務。移動Sink可以減少所需部署的節(jié)點，且能在無人狀態(tài)下前往環(huán)境復雜惡劣的地點，能夠在WSN非連通的情況下通過自身的移動收集數據。此外，使用移動Sink可減少節(jié)點能耗[11]。

使用移動Sink可解決存在的一些實際問題，但使用移動Sink容易導致時延增加，特別是當數據量較大且節(jié)點高度分散的情況。當節(jié)點分布較廣或數據量較大時如何降低時延是移動Sink數據收集的重要問題。為了盡可能降低時延，可采用多天線移動Sink進行數據收集。以往關于移動Sink的研究以單天線為主，近年來出現了對于WSN的多天線移動式數據收集的研究。多輸入移動收集器在每一個錨節(jié)點位置作一定時間的停留進行數據收集[12-13]。多天線移動Sink在數據收集時需要考慮停留時間和最小能耗等問題[14]。通過建立多天線移動Sink數據收集的分布式框架，用SDMA技術來進行數據的多天線收集[15]。

WSN節(jié)點能量有限，需要盡可能減少能耗并且時延要低，因此如何設計具有較小能耗并且低時延的多天線移動Sink數據收集方法是一個難點。已有研究缺少從節(jié)點分布或網絡結構方面進行討論。本文在已有研究的基礎上，通過對網絡結構的分析構建高效的多天線移動Sink數據收集方法，提出基于度和集聚系數的多天線移動Sink數據收集（degree，clustering coefficient and common point for multi antenna mobile Sink data collection，簡記 為DCCM）算法，該算法旨在降低節(jié)點能耗以及減小數據收集時延。

1 問題描述

假設監(jiān)測區(qū)域中部署N個傳感器節(jié)點，網絡是不連通的，分割為若干個連通分支和多個孤立節(jié)點，通過多天線移動Sink進行數據收集。

若Sink的天線數目為a，在Sink的停留點存在c個數據流，2≤c≤a，同時上傳數據到Sink，則稱為并發(fā)上傳數據。并發(fā)上傳數據可以縮短數據上傳的時間，但移動Sink的停留點的數據流需要和天線數目相匹配。然而如果片面追求數據流數目和天線數目相匹配，可能會導致移動Sink軌跡長度的增加，因此需要科學地選擇移動Sink停留點。

數據收集時間包含Sink移動時間和數據上傳時間，在縮短Sink移動時間的同時要使移動Sink停留點的數據流和天線數目相匹配，從而縮短數據上傳時間。此外，Sink移動的軌跡長度和節(jié)點的能耗是相矛盾的，需要在縮短Sink移動的軌跡長度和節(jié)點的能耗之間取得平衡。

用圖G來描述網絡，設圖G非連通，有連通分支G1，G2，…，Gm-1，Gm，各連通分支由已部署的節(jié)點組成，G1∪G2∪…∪Gm-1∪Gm。假設存在點集 S=可使G變?yōu)檫B通圖，則稱該點集中的點為虛擬點。

移動Sink的移動需保證每個節(jié)點都可被直接或間接通信到，移動Sink在停留點進行數據收集，數據收集過程中移動Sink有y個停留點，節(jié)點總能耗為E，數據收集的總時間（時延）為T，h表示跳數，則

多天線的應用可提高數據收集的效率，天線的空閑率要盡可能低，移動Sink的停留點需要具備與天線數目相匹配的度，或者在原本不相匹配的基礎上改變數據流使其匹配，以進一步減小時延。問題的難點在于停留點的度和天線數目往往是不匹配的，若要達到高度的匹配有可能會增大Sink移動距離，因此需要從節(jié)點分布的角度加以分析。本文通過加入若干虛擬點，使可能不連通的節(jié)點分布成為一個連通圖，從網絡結構的角度對多天線移動Sink數據收集進行研究，達到降低網絡能耗和時延。

2 多天線移動Sink數據收集

2.1 適應多天線移動Sink的分簇方式

各個連通分支和虛擬點一起構成連通圖，然后從連通圖的角度進行討論。適宜多天線數據收集的條件：m（m≥2）個連通分支之間存在公共點，公共點之間距離要短。從圖1可以看出高效的多天線移動Sink在節(jié)點隨機部署情況下進行數據收集，從網絡結構上來說需要具備大的集聚系數。因為需要移動Sink停留點具備與天線數目匹配的度（鄰居節(jié)點數目），最理想的情況是Sink的每個停留點的度都是a。

定義1設點k的度為d，那么與點k最多有d(d-2)/2條連線，如果它的鄰域中實際存在的連線數為E(k)，則點k的集聚系數為

圖1 100個節(jié)點通信半徑為40的隨機部署統(tǒng)計

點的集聚系數用來描述圖或網絡中的頂點（節(jié)點）之間結集成團的程度，是一個點的鄰接點之間相互連接的程度。集聚系數是一個介于0與1之間的數，集聚系數越接近1，表示這個節(jié)點附近的點越有集結成團的趨勢。設d表示停留點的度，若d＞a，則需要將(d-a)個數據流并入a個數據流中，即移動Sink的停留點需要有大的集聚系數。由于dk=a，天線數目a是固定的，對于點的確定要看其鄰域之間的連線是否緊密。首先計算網絡中3個連通節(jié)點的總數，然后計算網絡中三角形結構的總數，3倍三角形的總數在3個連通節(jié)點的總數中所占比例稱為網絡的集聚系數，即

其中N1表示網絡中3個連通節(jié)點的總數，N2表示網絡中三角形的總數。從能耗的角度分析，在數據并發(fā)上傳到移動Sink過程中，當d＞a時，(d-a)個數據流需要并入a個數據流中，這時最節(jié)約能耗的情況是圍繞著移動Sink所在位置有(d-a)個三角形結構。

在確定點的位置時，若數據流的數目與天線數目不相匹配時，通過尋找三角形的結構關系可以為移動Sink確定合適的停留位置。從全網的角度看，通過分析全網三角形結構的含量，可以判斷多天線移動Sink是否得到充分使用。

2.2 多天線移動Sink數據收集的數據流分析

通過對WSN中數據流地分析，可以進一步為多天線移動Sink數據收集提供優(yōu)化的依據。采用排隊網絡理論對WSN中數據流進行分析，排隊網絡指多個排隊系統(tǒng)互相連接所組成的網絡。

虛擬點和節(jié)點一起構成圖，將虛擬點以及非葉節(jié)點（沒有子節(jié)點的子節(jié)點叫做葉節(jié)點）稱為中心。由于數據流是守恒的，存在以下3種情況：eia表示一個節(jié)點的數據到達中心i；eij表示一個節(jié)點在中心i處接收結束并轉移到中心j；eid表示移動Sink在中心i處接收結束并離開。n表示各個隊列中節(jié)點的數目。當存在平穩(wěn)概率π(n)時，流出狀態(tài)n的強度之和為

其中λ為數據流總流入強度，移動Sink到達中心點，然后轉移到其他中心進行數據接收，因此

其中θi表示移動Sink在某中心接收結束后轉移到中心i的概率，ni表示第i個服務中心的隊長，πi(ni)表示中心i有ni個節(jié)點的概率。

其中π(n)表示停留點1的隊長為n1，停留點2的隊長為n2，依次類推，停留點M的隊長為nM，δ為歸一化因子，則

X（t）表示t時刻的狀態(tài)，可以判斷X（t）是一個馬爾科夫過程。

通過以上的分析可知，若n＞nL，即隊列長度大于隊長限制nL，則希望π（n）小，π（n）表示各個中心平均隊列長度為n的概率，π（n）小意味著M大。若n≤nL，即隊列長度不大于隊長限制，則希望π（n）大。停留點少或者負載均衡有利于π（n）大。由于停留點之間是相乘的關系，而隊列長度的變化是相加的關系，停留點少的作用更顯著，且增加停留點會加大時延，所以首先考慮減少停留點。當n≤nL時，隊列長度n1≈n2≈…≈nM，即在負載均衡時，不通過減少停留點，也可使π（n）大。

減少停留點主要的因素是度和集聚系數。若需要停留點具備與天線數目匹配的度，全網的平均度要大于等于天線數目，這樣才能充分發(fā)揮多天線對數據收集的作用?？赡艹霈F的情況有兩種：一是停留點的度大于天線數目且集聚系數小，造成有的數據流無法并入其他數據流，即事件eij不能發(fā)生，從而移動Sink另外選擇其他停留點；二是停留點的度小于等于天線數目，或者停留點的度大于天線數目且集聚系數大，停留點的度小于等于天線數目不能充分利用多天線的優(yōu)勢，使停留點的度大于天線數目且集聚系數大則可充分利用多天線的優(yōu)勢。

2.3 多天線移動Sink數據收集的路徑規(guī)劃

Sink移動的軌跡長度和節(jié)點的能耗是相矛盾的，需要在Sink移動的軌跡長度和節(jié)點的能耗之間取得平衡。若要降低節(jié)點能耗，會使移動Sink增大移動距離造成時延的增加。最極限的情況是移動Sink移動到每一個節(jié)點的一跳通信范圍內，從而使節(jié)點的能耗最小。本文通過對虛擬點輔助形成的連通圖分析，科學地選擇移動Sink停留點，使數據收集過程中節(jié)點能耗與時延達到平衡。

停留點的度大于天線數目且集聚系數大則可充分利用并發(fā)上傳的優(yōu)勢，但卻有可能造成跳數過多的長鏈路。網絡的平均距離的減小，不僅會使節(jié)點能耗降低，也會使Sink的移動距離減小。因此需要尋找有效減小網絡平均距離的方法。

介數可以體現節(jié)點在網絡中的重要性或影響力，大的介數對于跳數有減小的作用。介數通常分為點介數和邊介數兩種，本文所討論的是點介數。

定義2設Ljk（i）表示節(jié)點j和節(jié)點k之間經過節(jié)點i的最短路徑數目，Ljk表示節(jié)點j和節(jié)點k之間的最短路徑數目，則點k的介數為

根據介數的定義可知，若G1和G2相同，由于本文中節(jié)點在某一時刻采用的是單一的轉發(fā)方式，因此在本文中指相同的節(jié)點數，即當NG1=NG2時停留點k的介數最大。當NG1＞NG2或NG1＜NG2時，NG1∪NG2中經過停留點k的最短路徑的次數不相等，停留點k的介數大于等于G1和G2中節(jié)點數多的一方的任一節(jié)點。因此若停留點k連通著獨立連通分支G1和獨立連通分支G2，則該點的介數不小于G1或G2中的任一節(jié)點。

Sink的停留點應選擇位于介數之和最大的兩個點c和d之間，c和d分別來自不同的連通分支，且兩點距離Icd≤2R。

數據收集時間包含Sink移動時間和數據上傳時間，在縮短Sink移動的軌跡長度的同時要使移動Sink的停留點的數據流和天線數目相匹配，從而縮短數據上傳時間。對于停留點的選擇需要其具備在大的集聚系數作用下與天線數目匹配的度以及可連接多個連通分支中介數大的點（或獨立點）的公共點。通過前面的分析可知多天線移動Sink數據收集問題與網絡結構密切相關，以下提出一種新的多天線移動Sink數據收集算法。

2.4 一種新的多天線移動Sink數據收集算法：DC?CM算法

DCCM算法主要過程：首先根據節(jié)點部署信息加入點（即虛擬點）構成連通圖，然后從連通圖的角度通過尋找優(yōu)化的點的位置形成一系列停留點，從而確定Sink移動軌跡。

在監(jiān)測區(qū)域中，設Sink起始點的坐標為（x0，y0）。根據前文的分析，本文提出的DCCM算法具體如下：

步驟1輸入移動Sink起始點位置的坐標（x0，y0）。

步驟2找距（x0，y0）最近的連通分支（或獨立的點）附近的點：

（Ⅰ）若dmax≤a，點唯一則作為停留點P1，點不唯一則轉到第3步。

（Ⅱ）若dmax＞a，點唯一則作為停留點P1，通過數據流的整合使得d=a，若不能則尋找度第二大的點，再從第1步開始；若dmax＞a，有多個點均為dmax，則轉到第3步，經過第3步若還無法確定停留點，則比較集聚系數，選擇Cmax的點，通過數據流的整合使得d=a，若通過數據流的整合仍然d＞a，則在多個度均為dmax的點中尋找集聚系數第二大的點，進行數據流的整合。依次類推，如果根據集聚系數不能完成數據流整合，則尋找度第二大的點。

（Ⅲ）比較點是否為多個連通分支中介數大的點的公共點，若是則作為停留點P2。

步驟3若d＞a，則將d個數據流合并為a個數據流，Sink直線移至P1進行數據收集；若d≤a，則為d個數據流，Sink直線移至P1進行數據收集。

步驟4去除在P1位置Sink可通信的連通分支。

步驟5找距離P1最近的連通分支（或獨立的點）附近的點，重復第2步選擇點作為停留點P2。

步驟6 依次完成P1，P2，…，Pn。

步驟7判斷移動Sink是否直接或間接通信過所有節(jié)點，若已完成，程序結束；若未完成，轉至步驟5。

連接P1，P2，…，Pn位置即形成Sink軌跡。DCCM算法能夠良好實現多天線移動Sink數據收集。DCCM算法的優(yōu)點主要有：（1）可以較好地完成對并發(fā)上傳數據和天線的匹配，其原因是當度與天線不匹配時可以通過大的集聚系數來調節(jié)，度和集聚系數的結合使多天線得到充分利用；（2）進一步降低了能耗以及縮短了Sink移動軌跡，其原因是多個連通分支中介數大的點的公共點作為Sink停留點，使平均跳數減少的同時縮短了Sink移動軌跡。

3 性能評估

為了驗證算法的有效性，本文使用Matlab對DCCM算法進行仿真與分析。仿真實驗部署的節(jié)點為全向節(jié)點，節(jié)點通信半徑為R，在1 000×1 000的范圍內，取R=40，a=2，隨機部署節(jié)點，為便于對比，實驗場景與文獻[15]一致。

3.1 三角形結構含量的影響

通過統(tǒng)計隨機部署的網絡中的三角形結構含量，三角形結構含量大說明網絡的集聚系數大，網絡的集聚系數大可以為數據流提供更多的路徑選擇，為多天線完成其對并發(fā)上傳數據的收集提供了便利，其中z表示三角形結構的含量。從圖2可以看出三角形結構含量大有利于減小能耗，即集聚系數大有利于減小能耗，其原因是數據流有了更多的到達Sink的路徑選擇，便于數據流的優(yōu)化重組。

3.2 網絡能耗

圖2 三角形結構含量對能耗的影響

假設收集相同的數據，均采用雙天線。DaGCM算法[15]通過分裂數據來節(jié)約能耗，暫不收集遠離停留點的數據，而在另外距此節(jié)點較近的停留點進行收集。而DCCM算法則通過尋找多個連通分支中介數大的點的公共點作為停留點進行數據收集。DaGCM算法加大了時延，而DCCM算法減小能耗的同時減小了時延。圖3顯示了在能耗方面的比較，可見DCCM算法優(yōu)于DaGCM算法。因為運用點介數指標減小了平均跳數以及移動Sink軌跡長度，所以較好地減小了網絡的能耗和時延。

圖3 網絡能耗對比

4 結論

移動Sink是面向復雜環(huán)境下WSN數據收集的一種有效方法。本文從網絡結構的角度研究多天線移動Sink的數據收集問題。首先論證了多天線移動Sink數據收集問題包含的結構特征，然后提出了基于度、集聚系數以及多個連通分支中介數大的點的公共點的多天線移動Sink數據收集算法。仿真表明，該算法降低了網絡的能耗以及時延。