樂俊，張維明，肖衛(wèi)東，湯大權(quán)，唐九陽

（國防科學(xué)技術(shù)大學(xué) 信息系統(tǒng)工程重點(diǎn)實(shí)驗(yàn)室，湖南 長沙 410073）

1 引言

微機(jī)電系統(tǒng)、無線通信和數(shù)字電子等技術(shù)的發(fā)展促進(jìn)了低成本、低功率和多功能傳感器的發(fā)展，這些傳感器由感知、數(shù)據(jù)處理和通信等模塊組成，尺寸小并可以進(jìn)行短距離無線通信，將大量傳感器部署在監(jiān)控區(qū)域，通過無線通信的方式相互連接，就可以組成無線傳感器網(wǎng)絡(luò)(WSN, wireless sensor networks)[1]。WSN一般包括大量傳感器節(jié)點(diǎn)（以下簡稱節(jié)點(diǎn)）和一個(gè)收集數(shù)據(jù)的基站，能夠?qū)崟r(shí)監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象信息，并對這些信息進(jìn)行處理，然后傳送到需要這些信息的用戶。WSN不需要固定網(wǎng)絡(luò)支持，具有快速展開、抗毀性強(qiáng)等特點(diǎn)，可廣泛應(yīng)用于軍事、工業(yè)、交通、環(huán)保等領(lǐng)域[2]。

在WSN的傳統(tǒng)應(yīng)用中，網(wǎng)絡(luò)部署區(qū)域通常位于人無法輕易接近的遠(yuǎn)程環(huán)境中，如森林、戰(zhàn)場、災(zāi)難現(xiàn)場等場合，節(jié)點(diǎn)一般位于感知對象周邊，位置基本固定、電源不便更換，多個(gè)節(jié)點(diǎn)協(xié)同感知，基站往往位于網(wǎng)絡(luò)部署區(qū)域之外。隨著應(yīng)用范圍的不斷擴(kuò)展，尤其是物聯(lián)網(wǎng)的發(fā)展和應(yīng)用，WSN的應(yīng)用也出現(xiàn)了新的模式，網(wǎng)絡(luò)部署在日常環(huán)境如停車場、商場、倉庫中，更換節(jié)點(diǎn)電源相對可行，節(jié)點(diǎn)通常隨著物體移動，某個(gè)節(jié)點(diǎn)往往只負(fù)責(zé)感知其所對應(yīng)物體及物體周圍環(huán)境的相關(guān)信息，基站位于網(wǎng)絡(luò)內(nèi)部或邊緣。在這些新應(yīng)用中，WSN具有網(wǎng)絡(luò)動態(tài)變化頻繁、對數(shù)據(jù)通信的可靠性要求高等特點(diǎn)。另一方面，WSN的一些本質(zhì)特性在這些新應(yīng)用中并沒有改變，由于節(jié)點(diǎn)體積受限、使用有限電源、采用無線通信方式等原因，節(jié)點(diǎn)的能量、通信距離和帶寬等資源都受到限制，所以，如何節(jié)約能量，提高通信效率仍然是需要面臨的問題。

數(shù)據(jù)融合是WSN解決資源受限問題所普遍采用的一種技術(shù)，它的基本思想是：當(dāng)節(jié)點(diǎn)收到其他節(jié)點(diǎn)的數(shù)據(jù)后，不是分別轉(zhuǎn)發(fā)出去，而是對這些數(shù)據(jù)進(jìn)行融合處理，將融合后的結(jié)果轉(zhuǎn)發(fā)出去，從而減少數(shù)據(jù)通信量[3]。在 WSN中，數(shù)據(jù)通信所消耗的能量要大大高于數(shù)據(jù)采集和數(shù)據(jù)處理所消耗的能量。所以，減少數(shù)據(jù)通信量就能夠有效降低能量的消耗，同時(shí)還能在一定程度上避免無線信道中的數(shù)據(jù)碰撞，從而提高通信效率。

在WSN新應(yīng)用中，仍然可以采用數(shù)據(jù)融合節(jié)約能量和提高通信效率。本文針對WSN新應(yīng)用中所出現(xiàn)的新需求，提出了一種無結(jié)構(gòu)動態(tài)適應(yīng)數(shù)據(jù)融合 (SFDA, structure-free and dynamic-adaptive data fusion) 算法，該算法不需要在傳感器之間建立和維護(hù)數(shù)據(jù)通信的結(jié)構(gòu)、采用“多對多”的數(shù)據(jù)通信方式，以適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，提供高可靠性的數(shù)據(jù)通信。

2 相關(guān)工作

WSN中的數(shù)據(jù)融合就是在數(shù)據(jù)從節(jié)點(diǎn)向基站傳輸?shù)倪^程中，由中間節(jié)點(diǎn)對來自多個(gè)節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行融合[4]。它需要完成2項(xiàng)工作：數(shù)據(jù)收集和融合處理。根據(jù)應(yīng)用的不同，數(shù)據(jù)收集的方式可以分為事件觸發(fā)式、查詢式和周期性匯報(bào)式。融合處理則包括數(shù)據(jù)計(jì)算、數(shù)據(jù)分組合并或數(shù)據(jù)壓縮等方式。

現(xiàn)有的數(shù)據(jù)融合算法可以歸納為基于平面結(jié)構(gòu)、基于分簇結(jié)構(gòu)、基于樹狀結(jié)構(gòu)、基于鏈路結(jié)構(gòu)、基于混合結(jié)構(gòu)和無結(jié)構(gòu)幾大類。下面分別簡單介紹。

定向擴(kuò)散(directed diffusion)[5]和 SPIN (sensor protocol for information via negotiation)[6]是基于平面結(jié)構(gòu)算法的典型代表。在定向擴(kuò)散算法中，基站周期性地向鄰近節(jié)點(diǎn)廣播興趣消息，興趣包括任務(wù)類型、目標(biāo)區(qū)域、時(shí)間戳等參數(shù)。每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)興趣列表，在接收到興趣消息后，將興趣的信息保存在興趣列表中，以建立該節(jié)點(diǎn)指向基站的梯度關(guān)系，并向鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)興趣消息。這樣，隨著興趣消息的轉(zhuǎn)發(fā)，每個(gè)收到興趣消息的節(jié)點(diǎn)都能建立起指向基站的梯度。當(dāng)節(jié)點(diǎn)收集到與興趣相匹配的數(shù)據(jù)時(shí)，可以通過梯度信息將數(shù)據(jù)由其他節(jié)點(diǎn)依次轉(zhuǎn)發(fā)至基站。SPIN是一組基于協(xié)商的算法，節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前與其他節(jié)點(diǎn)進(jìn)行協(xié)商，從而建立數(shù)據(jù)傳輸?shù)穆窂剑缓笤侔绰窂较蚧景l(fā)送數(shù)據(jù)。

LEACH(low energy adaptive clustering hierarchy)[7]是一種經(jīng)典的基于分簇結(jié)構(gòu)算法，它按照輪周期性運(yùn)行，每輪都包括設(shè)置和穩(wěn)定2個(gè)階段。在設(shè)置階段，節(jié)點(diǎn)以自組織的方式隨機(jī)選擇一定數(shù)目的簇首，然后，簇首廣播自己成為簇首的消息，其他節(jié)點(diǎn)依據(jù)接收該消息的信號強(qiáng)度選擇加入一個(gè)簇。在穩(wěn)定階段，簇成員將數(shù)據(jù)發(fā)送至簇首，由簇首對數(shù)據(jù)進(jìn)行融合處理后將結(jié)果發(fā)送至基站。很多分簇算法在LEACH的基礎(chǔ)上對簇首選擇方法和分簇的方式進(jìn)行改進(jìn)，例如，HEED(hybrid energyefficient distributed clustering)[8]在簇首選擇和分簇的過程中綜合考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)與鄰居節(jié)點(diǎn)的鄰近性或節(jié)點(diǎn)的度，使剩余能量較高的節(jié)點(diǎn)更有機(jī)會成為簇首，并能夠平衡簇間的負(fù)載。

基于樹狀結(jié)構(gòu)算法通常以基站為根節(jié)點(diǎn)，將網(wǎng)絡(luò)中的節(jié)點(diǎn)組織成樹狀結(jié)構(gòu)，數(shù)據(jù)沿著該結(jié)構(gòu)向基站傳輸，并由非葉子節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的融合處理。這類算法的研究主要集中在如何建立樹狀結(jié)構(gòu)方面，例如文獻(xiàn)[9]所提到的 3種方法：GIT(greedy incremental tree)、SPT(shortest paths tree)和 CNS(center at nearest source)。

基于鏈路結(jié)構(gòu)算法的代表是PEGASIS (powerefficient gathering in sensor information systems)[10]，它將網(wǎng)絡(luò)中的所有節(jié)點(diǎn)連接成一條相鄰節(jié)點(diǎn)之間距離最短的鏈路，然后隨機(jī)選擇一個(gè)節(jié)點(diǎn)作為首領(lǐng)，從鏈路的兩端開始，節(jié)點(diǎn)依次向首領(lǐng)節(jié)點(diǎn)方向發(fā)送數(shù)據(jù)，中間節(jié)點(diǎn)將接收到的數(shù)據(jù)進(jìn)行融合處理，并將融合結(jié)果發(fā)送至下一節(jié)點(diǎn)，最終由首領(lǐng)節(jié)點(diǎn)將數(shù)據(jù)發(fā)送至基站。

基于混合結(jié)構(gòu)算法結(jié)合了上述結(jié)構(gòu)中的2種或多種。例如，GSEN(group-based sensor network)[11]融合了分簇和鏈路2種結(jié)構(gòu)，將每個(gè)簇內(nèi)的節(jié)點(diǎn)構(gòu)造成鏈路，簇首之間也形成高一級的鏈路，MLC(multi-level clusteirng)[12]則融合了分簇和樹狀 2種結(jié)構(gòu)，在簇首和基站之間構(gòu)造樹狀結(jié)構(gòu)。

除了上述基于結(jié)構(gòu)的數(shù)據(jù)融合算法外，也有文獻(xiàn)對無結(jié)構(gòu)的數(shù)據(jù)融合算法進(jìn)行了研究。文獻(xiàn)[13]針對事件觸發(fā)式數(shù)據(jù)收集，首次提出無結(jié)構(gòu)數(shù)據(jù)融合算法，在該算法中，需要發(fā)送數(shù)據(jù)的節(jié)點(diǎn)采用任意多播機(jī)制將數(shù)據(jù)發(fā)送至某個(gè)可進(jìn)行融合處理的節(jié)點(diǎn)。文獻(xiàn)[14]同樣針對事件觸發(fā)式數(shù)據(jù)收集，先動態(tài)選擇一些節(jié)點(diǎn)擔(dān)任融合節(jié)點(diǎn)，再由融合節(jié)點(diǎn)從其他節(jié)點(diǎn)收集數(shù)據(jù)進(jìn)行融合后發(fā)送至基站。

3 相關(guān)模型及問題描述

3.1 網(wǎng)絡(luò)模型

網(wǎng)絡(luò)模型的建立是為了對算法的前提進(jìn)行限定。假設(shè)WSN的部署區(qū)域是一個(gè)邊長為L、在二維坐標(biāo)系中起始點(diǎn)（左下角頂點(diǎn)）坐標(biāo)為(O_x,O_y)的二維正方形區(qū)域，節(jié)點(diǎn)均勻分布而且分布密度較大。除此之外，網(wǎng)絡(luò)還具有如下性質(zhì)：1)基站位于網(wǎng)絡(luò)內(nèi)部或邊緣、位置固定、坐標(biāo)為(BS_x,BS_y)；2)所有節(jié)點(diǎn)都是同構(gòu)的，節(jié)點(diǎn)可以通過定位設(shè)備或定位算法等方法獲得自己的位置信息；3)節(jié)點(diǎn)可以在網(wǎng)絡(luò)中移動或退出網(wǎng)絡(luò)，也可以有新的節(jié)點(diǎn)加入網(wǎng)絡(luò)；4)各節(jié)點(diǎn)以及基站之間時(shí)間同步；5)節(jié)點(diǎn)的通信距離可控，節(jié)點(diǎn)能夠根據(jù)通信距離調(diào)整發(fā)射功率；6)數(shù)據(jù)收集采用周期性匯報(bào)式，也就是說，每過一段時(shí)間，所有節(jié)點(diǎn)都向基站發(fā)送數(shù)據(jù)。

3.2 能耗模型

由于數(shù)據(jù)通信的能耗占傳感器節(jié)點(diǎn)總能耗的絕大部分，遠(yuǎn)遠(yuǎn)大于其他部分的能耗，因此，和同類算法一樣，本文只考慮數(shù)據(jù)傳輸和融合數(shù)據(jù)的能耗，節(jié)點(diǎn)獲得位置信息的能耗不考慮。

本文采用與LEACH相同的能耗模型，如果發(fā)送距離小于能耗模型閾值d0，采用自由空間模型，否則，采用多路徑衰減模型。節(jié)點(diǎn)發(fā)送和接收數(shù)據(jù)的能耗公式分別為

其中，l是數(shù)據(jù)的長度即比特?cái)?shù)，d是數(shù)據(jù)發(fā)送距離，ETx-elec(l)是無線收發(fā)電路發(fā)送長度為 l的數(shù)據(jù)的電路能耗，ETx-amp(l,d)是將長度為l的數(shù)據(jù)發(fā)送至距離d的放大器能耗，Eelec是無線收發(fā)電路發(fā)送或接收單位長度數(shù)據(jù)的電路能耗，εfs和 εmp分別是自由空間模型和多路徑衰減模型的放大器能耗，ERx-elec(l)是無線收發(fā)電路接收長度為l的數(shù)據(jù)的電路能耗。

節(jié)點(diǎn)對k個(gè)長度為lbit的數(shù)據(jù)進(jìn)行融合處理所需要消耗的能量為

其中，EDA是融合單位長度數(shù)據(jù)所需的能耗。

3.3 問題描述

與傳統(tǒng)應(yīng)用相比，WSN的新應(yīng)用尤其是其在物聯(lián)網(wǎng)中的應(yīng)用具有一些新的特點(diǎn)，主要表現(xiàn)在以下2個(gè)方面。

1) 節(jié)點(diǎn)的動態(tài)加入或退出以及節(jié)點(diǎn)在網(wǎng)絡(luò)中的移動，導(dǎo)致網(wǎng)絡(luò)動態(tài)變化更加頻繁。傳感器往往附著在物體表面或安裝在物體內(nèi)部，而這些物體往往具有較高的移動性。如果物體移動，傳感器就會隨之移動，物體從網(wǎng)絡(luò)之外進(jìn)入網(wǎng)絡(luò)內(nèi)、從網(wǎng)絡(luò)內(nèi)移動至網(wǎng)絡(luò)外或者在網(wǎng)絡(luò)內(nèi)的移動以及傳感器失效等都會造成網(wǎng)絡(luò)的變化。

2) 對數(shù)據(jù)通信的可靠性要求更高。在傳統(tǒng)應(yīng)用中，多個(gè)節(jié)點(diǎn)協(xié)同工作，某些節(jié)點(diǎn)的數(shù)據(jù)傳輸失敗并不會對網(wǎng)絡(luò)的整體性能造成很大影響。而在新應(yīng)用中，一個(gè)傳感器通常只負(fù)責(zé)感知和收集其所對應(yīng)物體及物體周圍環(huán)境的相關(guān)信息。這就意味著，如果某個(gè)節(jié)點(diǎn)的數(shù)據(jù)無法傳送至基站，就無法獲得該節(jié)點(diǎn)對應(yīng)物體的相關(guān)信息，從而產(chǎn)生不利的影響。

節(jié)點(diǎn)直接將數(shù)據(jù)發(fā)送至基站的方式雖然可以提高數(shù)據(jù)通信的可靠性，但是，由于節(jié)點(diǎn)的通信距離有限，網(wǎng)絡(luò)的規(guī)模和可擴(kuò)展性都會受到限制，而采用泛洪的方法則會出現(xiàn)“信息爆炸”。上面所介紹的各類基于結(jié)構(gòu)的數(shù)據(jù)融合算法也都不能滿足上述需求。首先，這些算法需要預(yù)先在節(jié)點(diǎn)之間構(gòu)建某種結(jié)構(gòu)，一個(gè)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前需要與另外一個(gè)確定的節(jié)點(diǎn)建立連接，然后再按照該結(jié)構(gòu)傳輸數(shù)據(jù)。而結(jié)構(gòu)的建立需要節(jié)點(diǎn)間相互通信，節(jié)點(diǎn)會因?yàn)榘l(fā)送和接收控制消息而消耗較多的能量，如果采用固定的結(jié)構(gòu)，必然無法適應(yīng)網(wǎng)絡(luò)的動態(tài)變化，如果動態(tài)維護(hù)結(jié)構(gòu)，就需要再花費(fèi)額外的能量開銷；其次，基于結(jié)構(gòu)的數(shù)據(jù)融合算法均采用“多對一”或者“一對一”的數(shù)據(jù)通信方式，傳輸路徑上存在一些關(guān)鍵節(jié)點(diǎn)，例如分簇結(jié)構(gòu)中的簇首、樹狀結(jié)構(gòu)中的非葉子節(jié)點(diǎn)以及鏈路結(jié)構(gòu)中處于鏈路中間的節(jié)點(diǎn)等，如果這些節(jié)點(diǎn)失效，就會影響其他相關(guān)節(jié)點(diǎn)的數(shù)據(jù)傳輸?，F(xiàn)有的無結(jié)構(gòu)數(shù)據(jù)融合算法主要是針對事件觸發(fā)式數(shù)據(jù)收集，不適用于周期性匯報(bào)式數(shù)據(jù)收集，而且這些算法也采用“多對一”或者“一對一”的數(shù)據(jù)通信方式，同樣無法提供高可靠性的數(shù)據(jù)通信。

為了滿足這些新應(yīng)用需求，本文針對周期性匯報(bào)式數(shù)據(jù)收集的無線傳感器網(wǎng)絡(luò)，提出SFDA這種新的數(shù)據(jù)融合算法，在實(shí)現(xiàn)數(shù)據(jù)融合以節(jié)約能耗和提高通信效率的同時(shí)，還能夠適應(yīng)網(wǎng)絡(luò)的動態(tài)變化、保證高可靠性的數(shù)據(jù)通信。

4 SFDA算法設(shè)計(jì)

SFDA是一種無需在節(jié)點(diǎn)之間建立和維護(hù)結(jié)構(gòu)、采用“多對多”數(shù)據(jù)通信方式的數(shù)據(jù)融合算法，它按輪運(yùn)行，既可以按照固定的周期運(yùn)行，也可以由基站隨時(shí)重新發(fā)起新的一輪，每輪包括設(shè)置階段和穩(wěn)定階段。在設(shè)置階段，網(wǎng)絡(luò)被劃分為多個(gè)正方形柵格，各個(gè)節(jié)點(diǎn)確定自己所屬的柵格、傳輸數(shù)據(jù)的目的地和傳輸距離。在穩(wěn)定階段，各個(gè)節(jié)點(diǎn)按照一定的時(shí)序發(fā)送數(shù)據(jù)，如果基站位于節(jié)點(diǎn)所屬柵格的鄰近柵格，節(jié)點(diǎn)就直接將數(shù)據(jù)發(fā)送至基站，其他柵格內(nèi)的節(jié)點(diǎn)則從鄰近柵格中選擇一個(gè)作為下一跳目的地，一個(gè)柵格內(nèi)的所有節(jié)點(diǎn)分別接收其上一跳柵格所有節(jié)點(diǎn)發(fā)送的數(shù)據(jù)并和自身的數(shù)據(jù)進(jìn)行融合處理，再將融合結(jié)果發(fā)送至下一跳目的地，從而使節(jié)點(diǎn)的數(shù)據(jù)能夠通過一跳或多跳傳輸?shù)竭_(dá)基站。

4.1 設(shè)置階段

在設(shè)置階段，首先由各個(gè)節(jié)點(diǎn)向基站發(fā)送自己的位置坐標(biāo)、節(jié)點(diǎn)標(biāo)識等相關(guān)信息，基站在收集完所有節(jié)點(diǎn)的信息后，就能夠獲得當(dāng)前網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)和節(jié)點(diǎn)分布信息，再結(jié)合節(jié)點(diǎn)可能失效的概率以及節(jié)點(diǎn)最大通信距離確定柵格的大小也就是柵格邊長，然后劃分柵格，確定每個(gè)柵格內(nèi)節(jié)點(diǎn)的下一跳目的地，為每個(gè)柵格及柵格中的節(jié)點(diǎn)分配通信時(shí)隙。

柵格邊長是SFDA算法的一個(gè)參數(shù)，其取值由具體的應(yīng)用決定，在同一應(yīng)用中，每輪的柵格邊長也可以由基站動態(tài)確定。確定柵格邊長需要考慮 2個(gè)因素：一個(gè)是網(wǎng)絡(luò)的節(jié)點(diǎn)分布和動態(tài)性，必須使每個(gè)柵格中均分布有可參與數(shù)據(jù)通信的節(jié)點(diǎn)以提高數(shù)據(jù)通信的可靠性；一個(gè)是節(jié)點(diǎn)的通信距離，必須保證節(jié)點(diǎn)能夠完成下一跳數(shù)據(jù)傳輸。前一個(gè)條件要求柵格邊長不能小于某個(gè)值，也就是限定了柵格邊長的下界，后一個(gè)條件要求柵格邊長不能大于某個(gè)值，也就是限定了柵格邊長的上界。然后，可以在該下界和上界所確定的范圍內(nèi)選擇一個(gè)合適的取值確定為柵格的邊長。

假設(shè)當(dāng)前網(wǎng)絡(luò)中均勻分布有N個(gè)節(jié)點(diǎn)，需要確定的柵格邊長為B，則柵格的總數(shù)G為(L/B)2個(gè)，每個(gè)柵格中節(jié)點(diǎn)數(shù)目的期望值 NG為 N/G，每個(gè)節(jié)點(diǎn)失效的概率相同并設(shè)為PO，那么每個(gè)柵格可參與數(shù)據(jù)通信的節(jié)點(diǎn)（也就是有效節(jié)點(diǎn)）總數(shù)的期望值NT為

為了提高數(shù)據(jù)通信的可靠性，所以需要保證每個(gè)柵格中都分布著有效節(jié)點(diǎn)，也就是要求NT大于1，所以柵格邊長需要滿足：

另外，在數(shù)據(jù)通信時(shí)，一個(gè)柵格內(nèi)的節(jié)點(diǎn)需要向鄰近某個(gè)柵格的所有節(jié)點(diǎn)發(fā)送數(shù)據(jù)，而節(jié)點(diǎn)與鄰近柵格節(jié)點(diǎn)最大距離的情況就是這2個(gè)節(jié)點(diǎn)分別位于2個(gè)柵格對角線的兩端，如圖1所示。設(shè)節(jié)點(diǎn)最大通信距離為R，則柵格邊長還應(yīng)滿足：

圖1 相鄰柵格節(jié)點(diǎn)最大距離示意

為了提高對網(wǎng)絡(luò)的動態(tài)適應(yīng)性，算法基于網(wǎng)絡(luò)中節(jié)點(diǎn)的當(dāng)前狀態(tài)和動態(tài)變化趨勢來預(yù)估其未來的狀態(tài)。需要說明的是，式(5)給出的柵格邊長下界是在節(jié)點(diǎn)均勻分布且分布密度較大以及每個(gè)節(jié)點(diǎn)失效概率均相等的條件下確定的，而式(6)給出的柵格邊長上界是在所有節(jié)點(diǎn)同構(gòu)也就是最大通信距離相等的條件下確定的，因而，只要網(wǎng)絡(luò)能夠滿足上述條件，而且柵格邊長能夠同時(shí)滿足式(5)和式(6)，算法就可以保證每個(gè)柵格中都分布著有效節(jié)點(diǎn)而且節(jié)點(diǎn)能夠完成下一跳數(shù)據(jù)傳輸。在本文限定范圍之外的應(yīng)用中，如果出現(xiàn)節(jié)點(diǎn)分布不均勻、節(jié)點(diǎn)失效概率不同或節(jié)點(diǎn)異構(gòu)的情況，即使?jié)M足式(5)和式(6)的柵格邊長也無法保證每個(gè)柵格中都分布著有效節(jié)點(diǎn)或節(jié)點(diǎn)能夠完成下一跳數(shù)據(jù)傳輸，針對這些情況，將在下一步工作中進(jìn)行研究并分別提出相應(yīng)的解決方案，擴(kuò)展算法以提高算法的健壯性和擴(kuò)大算法的應(yīng)用范圍。還有，算法的性能如對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力和能量消耗都與柵格邊長的取值相關(guān)，未來，將通過定量的方法分析柵格邊長的最佳取值，以優(yōu)化算法的性能。

基站的另一個(gè)工作是確定每個(gè)柵格內(nèi)節(jié)點(diǎn)的下一跳目的地以及每個(gè)柵格和柵格內(nèi)節(jié)點(diǎn)傳輸數(shù)據(jù)的時(shí)隙。首先給出幾個(gè)相關(guān)定義。

定義 1 （鄰近柵格）和某個(gè)柵格有公共邊或公共頂點(diǎn)的柵格稱為該柵格的鄰近柵格。

定義 2 （臨近柵格）基站位于內(nèi)部或邊緣的柵格以及基站位于鄰近柵格內(nèi)部或邊緣的柵格稱為臨近柵格。

定義 3 （臨近區(qū)域）所有臨近柵格組成的區(qū)域稱為臨近區(qū)域。

用二元組(G_x,G_y)作為柵格標(biāo)識，其中，G_x是柵格橫標(biāo)識，G_y是柵格縱標(biāo)識，坐標(biāo)為(x, y)的位置所處的柵格為，左下角柵格的標(biāo)識為(1,1)、右上角柵格的標(biāo)識為(L/B,L/B)，基站用(0,0)表示，基站所在柵格的標(biāo)識為。臨近柵格和臨近區(qū)域的分布分為基站位于某個(gè)柵格頂點(diǎn)、邊界（不包括柵格頂點(diǎn)）或內(nèi)部3種情況，如圖2所示，其中，五角星代表基站，陰影區(qū)域代表臨近區(qū)域。

圖2 臨近柵格和臨近區(qū)域示意

用[LB_x:RT_x,LB_y:RT_y]表示臨近區(qū)域，其中，LB_x和RT_x分別為左下角和右上角臨近柵格的橫標(biāo)識，LB_y和RT_y分別為左下角和右上角臨近柵格的縱標(biāo)識，可以通過算法1確定網(wǎng)絡(luò)的臨近區(qū)域。

算法1 確定臨近區(qū)域的算法偽碼

臨近柵格將基站作為目的地，其他柵格(G_x, G_y)選擇距離最近的臨近柵格(A_x,A_y)作為目的地，并從鄰近柵格中選擇一個(gè)柵格(N_x,N_y)作為下一跳，確定所有柵格目的地和下一跳的算法分別描述如下。

算法2 確定柵格目的地的算法偽碼

算法3 確定柵格下一跳的算法偽碼

在確定了每個(gè)柵格的下一跳目的地之后，整個(gè)網(wǎng)絡(luò)就形成了以柵格為單位的從柵格到基站的有向連通結(jié)構(gòu)，每個(gè)柵格都能夠直接或間接與基站連通，如圖3所示。

圖3 從柵格到基站的有向連通結(jié)構(gòu)示意

為了能夠?qū)崿F(xiàn)數(shù)據(jù)的融合并提高通信效率，還需要確定通信時(shí)隙，在同一條鏈路上，按照由遠(yuǎn)及近的原則以柵格為單位發(fā)送數(shù)據(jù)，從而使中間柵格內(nèi)的節(jié)點(diǎn)能夠進(jìn)行數(shù)據(jù)的融合處理。另外，如果相互之間不會產(chǎn)生干擾，不同鏈路的多個(gè)柵格可以同時(shí)進(jìn)行數(shù)據(jù)的傳輸。

基于所收集的節(jié)點(diǎn)信息和柵格劃分的結(jié)果，基站能夠獲得每個(gè)柵格中所分布的節(jié)點(diǎn)信息，從而可以為每個(gè)柵格以及柵格內(nèi)的節(jié)點(diǎn)分配時(shí)隙。當(dāng)然，分配時(shí)隙的時(shí)候必須要考慮網(wǎng)絡(luò)的動態(tài)變化。

同一個(gè)柵格內(nèi)節(jié)點(diǎn)的時(shí)隙先后順序可以按照一定規(guī)則確定，如按照節(jié)點(diǎn)標(biāo)識從小到大排列，設(shè)柵格(G_x,G_y)內(nèi)的i個(gè)節(jié)點(diǎn)標(biāo)識排列為N_1，N_2，…，N_i，設(shè)基站為該柵格分配的時(shí)隙表示為(G_x，G_y，T0，TN，T1，i，N_1，N_2，…，N_i)，其中，T0為該柵格時(shí)隙開始的時(shí)刻，TN為單個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)所需時(shí)間的期望值，T1為預(yù)留時(shí)隙長度。設(shè)置預(yù)留時(shí)隙是為了提高算法的動態(tài)適應(yīng)能力，因?yàn)榭赡艹霈F(xiàn)節(jié)點(diǎn)移動等情況使得某些柵格內(nèi)分布的節(jié)點(diǎn)發(fā)生變化。柵格時(shí)隙的時(shí)間長度、節(jié)點(diǎn)N_k(1≤k≤i)時(shí)隙的開始時(shí)刻Tk和預(yù)留時(shí)隙開始時(shí)刻Tr分別為

預(yù)留時(shí)隙可以根據(jù)應(yīng)用需求由基站動態(tài)確定，不同輪的預(yù)留時(shí)隙可以不同，同一輪中的各個(gè)柵格的預(yù)留時(shí)隙也可以不同。

上述工作完成之后，基站就向網(wǎng)絡(luò)中的所有節(jié)點(diǎn)廣播當(dāng)前輪數(shù)、部署區(qū)域起始點(diǎn)坐標(biāo)、基站位置坐標(biāo)、柵格邊長、每個(gè)柵格的下一跳目的地、每個(gè)柵格以及柵格中節(jié)點(diǎn)的時(shí)隙等信息以發(fā)起一輪數(shù)據(jù)收集，節(jié)點(diǎn)接收廣播消息并將這些信息保存在本地。

4.2 穩(wěn)定階段

在穩(wěn)定階段，每個(gè)節(jié)點(diǎn)首先根據(jù)本輪基站廣播的相關(guān)信息以及自己的位置確定節(jié)點(diǎn)所屬柵格、下一跳目的地、數(shù)據(jù)傳輸?shù)木嚯x、需要接收的上一跳柵格標(biāo)識以及發(fā)送數(shù)據(jù)時(shí)隙等信息，在收發(fā)數(shù)據(jù)時(shí)，節(jié)點(diǎn)接收上一跳柵格內(nèi)的所有節(jié)點(diǎn)發(fā)送的數(shù)據(jù)并和自己感知的數(shù)據(jù)進(jìn)行融合處理，最后在相應(yīng)的時(shí)隙中向下一跳目的地發(fā)送數(shù)據(jù)。和其他同類算法一樣，SFDA算法并不對采用何種融合處理方式進(jìn)行限定，而是在應(yīng)用中根據(jù)具體的需求，采用合適的融合處理方式。

首先，每個(gè)節(jié)點(diǎn)如節(jié)點(diǎn)j根據(jù)自己當(dāng)前的位置坐標(biāo)(j_x,j_y)確定自己所處柵格的標(biāo)識，然后從保存的基站廣播信息中查找該柵格對應(yīng)的下一跳目的地和所有以其為下一跳目的地的柵格。如果下一跳目的地的標(biāo)識為(0,0)，則說明該節(jié)點(diǎn)需要直接向基站發(fā)送數(shù)據(jù)，它的最小數(shù)據(jù)傳輸距離D_min為節(jié)點(diǎn)與基站之間的距離，否則，它的下一跳目的地就是某個(gè)柵格，設(shè)該柵格的標(biāo)識為(G_x,G_y)，則該節(jié)點(diǎn)的最小數(shù)據(jù)傳輸距離為它與這個(gè)柵格的4個(gè)頂點(diǎn)距離中的最大值。在理想條件下，最小數(shù)據(jù)傳輸距離就能夠滿足數(shù)據(jù)傳輸?shù)男枨?，但在?shí)際應(yīng)用中，數(shù)據(jù)的實(shí)際傳輸距離會小于節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)所使用的數(shù)據(jù)傳輸距離，因而，需要在最小數(shù)據(jù)傳輸距離之上再增加一定的預(yù)留距離Dr，以確保數(shù)據(jù)傳輸?shù)目煽啃浴Ｍ瑯拥?，預(yù)留距離的大小也取決于具體的應(yīng)用，每個(gè)節(jié)點(diǎn)的預(yù)留距離也可由節(jié)點(diǎn)分別確定。節(jié)點(diǎn)j確定數(shù)據(jù)傳輸距離D的算法描述如下：

算法4 節(jié)點(diǎn)確定數(shù)據(jù)傳輸距離的算法偽碼

節(jié)點(diǎn)接收到其他節(jié)點(diǎn)發(fā)送的數(shù)據(jù)消息時(shí)，首先檢查該消息是否來自其上一跳柵格，如果不是，不接收該消息，否則，接收該消息。節(jié)點(diǎn)在自己發(fā)送數(shù)據(jù)之前將所有接收的數(shù)據(jù)與自己感知的數(shù)據(jù)進(jìn)行融合處理，融合處理的方式可以根據(jù)應(yīng)用需求選擇。

發(fā)送數(shù)據(jù)時(shí)，各個(gè)節(jié)點(diǎn)根據(jù)時(shí)隙信息在相應(yīng)的時(shí)隙內(nèi)發(fā)送數(shù)據(jù)。首先，節(jié)點(diǎn)從所屬柵格的時(shí)隙信息中查找自己的節(jié)點(diǎn)標(biāo)識，如果節(jié)點(diǎn)標(biāo)識在時(shí)隙信息中，則節(jié)點(diǎn)計(jì)算自己時(shí)隙的開始時(shí)刻，并在該時(shí)刻到來時(shí)檢測信道是否可用，如果信道可用，則發(fā)送數(shù)據(jù)，如果信道不可用，節(jié)點(diǎn)先隨機(jī)生成一個(gè)延遲，待該延遲結(jié)束時(shí)再檢測信道是否可用，然后決定是否發(fā)送數(shù)據(jù)，如果還不能發(fā)生數(shù)據(jù)，則重復(fù)上述操作，直至完成數(shù)據(jù)發(fā)送或者節(jié)點(diǎn)的時(shí)隙結(jié)束；如果節(jié)點(diǎn)標(biāo)識不在所屬柵格的時(shí)隙信息中，該節(jié)點(diǎn)就在柵格的預(yù)留時(shí)隙內(nèi)發(fā)送數(shù)據(jù)，在柵格的預(yù)留時(shí)隙開始時(shí)，節(jié)點(diǎn)首先隨機(jī)生成一個(gè)延遲，待該延遲結(jié)束時(shí)再檢測信道是否可用，如果信道可用，則開始發(fā)送數(shù)據(jù)，否則，就重復(fù)上述隨機(jī)等待，檢測信道，決定是否發(fā)送數(shù)據(jù)的操作，直至完成數(shù)據(jù)發(fā)送或者柵格時(shí)隙結(jié)束。算法5描述了節(jié)點(diǎn)在相應(yīng)時(shí)隙中發(fā)送數(shù)據(jù)Data的操作。

算法5 節(jié)點(diǎn)發(fā)送數(shù)據(jù)操作的算法偽碼

節(jié)點(diǎn)在發(fā)送數(shù)據(jù)時(shí)，附帶將節(jié)點(diǎn)標(biāo)識、所屬柵格標(biāo)識等信息一起發(fā)送。另外，為了提高動態(tài)適應(yīng)性，所有在本輪中未發(fā)送數(shù)據(jù)的節(jié)點(diǎn)都定期檢測自己的位置并確定所屬柵格信息，如果節(jié)點(diǎn)的所屬柵格改變，則節(jié)點(diǎn)立即更新相關(guān)信息，并準(zhǔn)備在相應(yīng)時(shí)隙發(fā)送數(shù)據(jù)，從而盡量確保其仍然能夠發(fā)送數(shù)據(jù)。

5 SFDA算法分析

本節(jié)主要從網(wǎng)絡(luò)動態(tài)適應(yīng)性和能量消耗2個(gè)方面對SFDA算法進(jìn)行分析。

在基于結(jié)構(gòu)的算法中，必須預(yù)先在節(jié)點(diǎn)之間建立某種結(jié)構(gòu)，然后再按照結(jié)構(gòu)傳輸數(shù)據(jù)，這種結(jié)構(gòu)可以看作是節(jié)點(diǎn)之間的一個(gè)有向連通圖，每個(gè)節(jié)點(diǎn)與其下一跳節(jié)點(diǎn)連接，也就是說，每個(gè)節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前都必須清楚自己需要將數(shù)據(jù)發(fā)送至哪個(gè)節(jié)點(diǎn)、數(shù)據(jù)傳輸距離是多遠(yuǎn)。而在SFDA算法中，設(shè)置階段將網(wǎng)絡(luò)劃分為多個(gè)正方形柵格后，節(jié)點(diǎn)的數(shù)據(jù)傳輸就可以按照柵格為單位分類進(jìn)行，每個(gè)節(jié)點(diǎn)（直接向基站發(fā)送數(shù)據(jù)的節(jié)點(diǎn)除外）只需知道將數(shù)據(jù)發(fā)送至哪個(gè)柵格，而不需要知道接收數(shù)據(jù)的是哪個(gè)或哪些節(jié)點(diǎn)，也就是說，節(jié)點(diǎn)在發(fā)送數(shù)據(jù)之前，只需要知道數(shù)據(jù)的傳輸距離，而不需要知道目的地節(jié)點(diǎn)，也就沒有基于結(jié)構(gòu)算法所建立的那種由每一個(gè)節(jié)點(diǎn)與另外一個(gè)節(jié)點(diǎn)連接而構(gòu)建的確定結(jié)構(gòu)。如果網(wǎng)絡(luò)中的節(jié)點(diǎn)動態(tài)變化，在基于結(jié)構(gòu)的算法中，只要結(jié)構(gòu)還沒有更新，節(jié)點(diǎn)之間的連接就不會改變，也就對動態(tài)變化做出反應(yīng)。而在SFDA算法中，節(jié)點(diǎn)則可以通過定期檢測來更新自己的下一跳柵格。

WSN的新應(yīng)用中，網(wǎng)絡(luò)動態(tài)變化的原因主要分為節(jié)點(diǎn)從網(wǎng)絡(luò)中退出、節(jié)點(diǎn)在網(wǎng)絡(luò)中移動以及新的節(jié)點(diǎn)加入網(wǎng)絡(luò)3種。

節(jié)點(diǎn)從網(wǎng)絡(luò)中退出的情況有2種，一種是節(jié)點(diǎn)移動到了網(wǎng)絡(luò)部署區(qū)域之外，另一種則是節(jié)點(diǎn)雖然還在網(wǎng)絡(luò)中但由于節(jié)點(diǎn)故障、能量耗盡等因素造成節(jié)點(diǎn)無法正常工作。在采用“多對一”或“一對一”數(shù)據(jù)通信方式的數(shù)據(jù)融合算法中，如果某些節(jié)點(diǎn)退出網(wǎng)絡(luò)，則可能會造成以這些節(jié)點(diǎn)為轉(zhuǎn)發(fā)節(jié)點(diǎn)的所有節(jié)點(diǎn)都無法將數(shù)據(jù)發(fā)送至基站。而SFDA以柵格為單位進(jìn)行數(shù)據(jù)通信，是一種“多對多”的數(shù)據(jù)通信方式，這樣，即使某些節(jié)點(diǎn)退出網(wǎng)絡(luò)，只要柵格中還分布有節(jié)點(diǎn)，則仍然可以實(shí)現(xiàn)數(shù)據(jù)的有效收集。

對于節(jié)點(diǎn)在網(wǎng)絡(luò)中移動的情況，SFDA使節(jié)點(diǎn)定期檢測位置信息，如果節(jié)點(diǎn)沒有離開原來的柵格，則不會產(chǎn)生任何影響，否則，節(jié)點(diǎn)能夠及時(shí)更新相關(guān)信息從而仍然可以發(fā)送數(shù)據(jù)，所以，節(jié)點(diǎn)在網(wǎng)絡(luò)中的移動對數(shù)據(jù)的收集影響很小。而在基于結(jié)構(gòu)的算法中，如果節(jié)點(diǎn)的移動破壞了所建立的結(jié)構(gòu)，相關(guān)節(jié)點(diǎn)的數(shù)據(jù)都無法發(fā)送至基站，從而會影響網(wǎng)絡(luò)的數(shù)據(jù)收集。

因?yàn)楣?jié)點(diǎn)加入網(wǎng)絡(luò)而引起的網(wǎng)絡(luò)動態(tài)變化對SFDA的影響與其他算法類似，只有在新一輪開始之前加入網(wǎng)絡(luò)的節(jié)點(diǎn)才能夠發(fā)送數(shù)據(jù)。

在能量消耗方面，“多對多”的數(shù)據(jù)通信會增加節(jié)點(diǎn)的數(shù)據(jù)接收量，額外消耗一定的能量，實(shí)際上就是以能量為代價(jià)換取數(shù)據(jù)通信的可靠性。雖然如此，SFDA以柵格為單位對進(jìn)行數(shù)據(jù)的“多對多”傳輸，某個(gè)柵格的節(jié)點(diǎn)只將數(shù)據(jù)發(fā)送至一個(gè)鄰近柵格內(nèi)的節(jié)點(diǎn)，限制了重復(fù)接收數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)，另外，節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離只能覆蓋其鄰近柵格，限制了節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離，從而盡量降低了額外的能量開銷。再者，算法只增加了數(shù)據(jù)接收次數(shù)而并沒有增加數(shù)據(jù)發(fā)送次數(shù)，考慮到接收數(shù)據(jù)的能耗大大小于發(fā)送數(shù)據(jù)的能耗，所以，SFDA的額外能耗并不高。

由于SFDA所針對的是WSN的新應(yīng)用，這些網(wǎng)絡(luò)部署在日常環(huán)境中，通過人工或其他方式為節(jié)點(diǎn)更換電源或?yàn)殡娫闯潆娋哂幸欢ǖ目尚行浴Ｋ?，在這些應(yīng)用中，節(jié)能位于次要位置，數(shù)據(jù)通信的可靠性才是首要考慮，因而，SFDA對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力強(qiáng)、可實(shí)現(xiàn)高可靠的數(shù)據(jù)通信，能夠以較小的能耗代價(jià)滿足這種應(yīng)用需求。

需要說明的是，SFDA算法采用了不同于現(xiàn)有數(shù)據(jù)融合算法的數(shù)據(jù)傳輸方式，因?yàn)槿魏?種數(shù)據(jù)融合算法可以被同一個(gè)無線傳感器網(wǎng)絡(luò)分別采用但卻不能在一次數(shù)據(jù)收集中同時(shí)使用，所以，對于同一個(gè)無線傳感器網(wǎng)絡(luò)，可以采用SFDA算法的數(shù)據(jù)傳輸方式，也可以采用包括基于結(jié)構(gòu)算法在內(nèi)的其他數(shù)據(jù)傳輸方式，但是，不能在同一次數(shù)據(jù)收集中同時(shí)采用2種方式。此外，SFDA算法的“無結(jié)構(gòu)”是指不需要為數(shù)據(jù)傳輸而在節(jié)點(diǎn)之間建立每一個(gè)節(jié)點(diǎn)與另外一個(gè)節(jié)點(diǎn)連接的結(jié)構(gòu)，并非指組網(wǎng)結(jié)構(gòu)，所以，在有結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)中，SFDA算法并不會影響網(wǎng)絡(luò)自身的數(shù)據(jù)傳輸，網(wǎng)絡(luò)的結(jié)構(gòu)對SFDA算法也沒有影響。

6 仿真實(shí)驗(yàn)及結(jié)果分析

本文在 MATLAB平臺上進(jìn)行對比仿真實(shí)驗(yàn)，考察SFDA算法對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力以及能量消耗情況，并與其他幾種算法進(jìn)行比較。因?yàn)楝F(xiàn)有的無結(jié)構(gòu)數(shù)據(jù)融合算法都是針對事件觸發(fā)式，而在基于平面結(jié)構(gòu)算法中，定向擴(kuò)散算法是基于查詢式、SPIN算法是基于事件觸發(fā)式，與本文 SFDA算法所針對的周期性匯報(bào)式數(shù)據(jù)收集有所不同，所以，從基于分簇結(jié)構(gòu)、樹狀結(jié)構(gòu)和鏈路結(jié)構(gòu)算法中分別選擇一種具有代表性的、可應(yīng)用于周期性匯報(bào)式數(shù)據(jù)收集的算法與本文的算法進(jìn)行對比實(shí)驗(yàn)，它們分別是LEACH算法、GIT算法和PEGASIS算法。

6.1 仿真實(shí)驗(yàn)環(huán)境

網(wǎng)絡(luò)部署區(qū)域邊長、基站位置、節(jié)點(diǎn)總數(shù)、SFDA的柵格邊長都作為可設(shè)置參數(shù)，LEACH的每輪簇首期望數(shù)目依據(jù)文獻(xiàn)[7]確定為節(jié)點(diǎn)總數(shù)的 5%，以使LEACH達(dá)到較好的性能。融合處理能夠?qū)⑷舾蓚€(gè)長度相同的數(shù)據(jù)消息分組融合為一個(gè)仍為該長度的數(shù)據(jù)消息分組，其他仿真實(shí)驗(yàn)參數(shù)的設(shè)置如表1所示。

表1 其他仿真實(shí)驗(yàn)參數(shù)的設(shè)置

6.2 仿真實(shí)驗(yàn)結(jié)果分析

首先比較各個(gè)算法對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力。由于節(jié)點(diǎn)新加入網(wǎng)絡(luò)對幾種算法的影響相同，因此，仿真實(shí)驗(yàn)只考察算法對節(jié)點(diǎn)在網(wǎng)絡(luò)中移動或退出網(wǎng)絡(luò)所造成的網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力。如果節(jié)點(diǎn)因?yàn)樵诰W(wǎng)絡(luò)中移動或退出網(wǎng)絡(luò)而導(dǎo)致節(jié)點(diǎn)無法正常收發(fā)數(shù)據(jù)，則稱該節(jié)點(diǎn)失效。因?yàn)閹追N對比算法都是針對節(jié)點(diǎn)位置固定而非節(jié)點(diǎn)移動的應(yīng)用場景而設(shè)計(jì)的，所以實(shí)驗(yàn)不考慮導(dǎo)致節(jié)點(diǎn)失效的具體原因，而只設(shè)置節(jié)點(diǎn)的失效概率，每次對比實(shí)驗(yàn)中，各個(gè)算法的初始狀態(tài)、失效的節(jié)點(diǎn)（失效節(jié)點(diǎn)總數(shù)以及哪些節(jié)點(diǎn)失效）都是相同的，從而使實(shí)驗(yàn)結(jié)果具有可比較性。分別進(jìn)行多次對比仿真實(shí)驗(yàn)，每次對比仿真實(shí)驗(yàn)中幾種算法的節(jié)點(diǎn)失效概率相同，統(tǒng)計(jì)仿真實(shí)驗(yàn)中產(chǎn)生的連帶失效節(jié)點(diǎn)的數(shù)目，所謂連帶失效節(jié)點(diǎn)是指節(jié)點(diǎn)自身沒有失效但是因?yàn)槠渌?jié)點(diǎn)失效而無法將數(shù)據(jù)發(fā)送至基站的節(jié)點(diǎn)。相同條件下，算法的連帶實(shí)效節(jié)點(diǎn)的數(shù)目越小，就說明算法越能夠適應(yīng)網(wǎng)絡(luò)的動態(tài)變化。

每次對比仿真中節(jié)點(diǎn)的失效概率均相同，網(wǎng)絡(luò)部署區(qū)域邊長為200m，基站位置為(100, 100)，網(wǎng)絡(luò)中均勻分布有1 200個(gè)節(jié)點(diǎn)，SFDA的柵格邊長為20m，每個(gè)算法的仿真分別進(jìn)行100輪，節(jié)點(diǎn)失效概率為0.01～0.09和0.1～0.9的仿真結(jié)果分別如圖4和圖5所示?？梢钥闯?，在相同的條件下，SFDA、LEACH、GIT和PEGASIS的連帶失效節(jié)點(diǎn)平均數(shù)依次遞減，而且，SFDA的連帶失效節(jié)點(diǎn)平均數(shù)都要遠(yuǎn)遠(yuǎn)小于其他幾種算法。在節(jié)點(diǎn)失效概率小于0.4時(shí)，SFDA幾乎沒有連帶失效節(jié)點(diǎn)產(chǎn)生，隨著節(jié)點(diǎn)失效概率的增大，SFDA的連帶失效節(jié)點(diǎn)也只是緩慢增加，而其他幾種算法的連帶失效節(jié)點(diǎn)則較多，尤其是GIT和PEGASIS，在節(jié)點(diǎn)失效概率較大時(shí)，幾乎沒有節(jié)點(diǎn)能夠成功將數(shù)據(jù)傳輸至基站，主要原因是這些算法的關(guān)鍵節(jié)點(diǎn)較多，而一個(gè)關(guān)鍵節(jié)點(diǎn)的失效就可能影響其他很多節(jié)點(diǎn)的數(shù)據(jù)傳輸。仿真結(jié)果證明，使用SFDA算法，網(wǎng)絡(luò)動態(tài)變化對網(wǎng)絡(luò)數(shù)據(jù)收集的影響比使用LEACH、GIT和PEGASIS要小得多，SFDA對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力更強(qiáng)、能夠提供更為可靠的數(shù)據(jù)通信。

對于SFDA算法，在同一應(yīng)用場景中，柵格邊長取值的不同以及基站所處位置的不同都會給SFDA算法對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力造成影響。保持上述實(shí)驗(yàn)場景的其他條件不變，分別設(shè)置不同的柵格邊長和改變基站的位置，每次仿真100輪，考察連帶失效節(jié)點(diǎn)平均數(shù)，分析柵格邊長和基站位置對SFDA算法的動態(tài)變化適應(yīng)性的影響。

圖4 節(jié)點(diǎn)失效概率為0.01～0.09的仿真結(jié)果

圖5 節(jié)點(diǎn)失效概率為0.1～0.9的仿真結(jié)果

柵格邊長分別為20m、25m和40m時(shí)，在不同節(jié)點(diǎn)失效概率的情況下，實(shí)驗(yàn)中網(wǎng)絡(luò)產(chǎn)生的連帶失效節(jié)點(diǎn)平均數(shù)如圖6所示。柵格邊長的取值越大，產(chǎn)生的連帶失效節(jié)點(diǎn)越少，這就說明，柵格邊長越大，SFDA算法對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力越強(qiáng)。在SFDA算法中，連帶失效節(jié)點(diǎn)的產(chǎn)生原因是處于中間的柵格內(nèi)的所有節(jié)點(diǎn)都失效，從而造成以中間柵格內(nèi)的節(jié)點(diǎn)為中繼節(jié)點(diǎn)的其他相關(guān)柵格內(nèi)的有效節(jié)點(diǎn)無法完成數(shù)據(jù)傳輸而失效。柵格邊長取值越大，柵格就越大，在節(jié)點(diǎn)均勻分布的情況下，柵格內(nèi)的節(jié)點(diǎn)也就越多，在節(jié)點(diǎn)失效概率相同時(shí)，柵格內(nèi)所有節(jié)點(diǎn)都失效的可能性就越小，此外，柵格邊長越大，網(wǎng)絡(luò)中的柵格就越少，相同節(jié)點(diǎn)將數(shù)據(jù)發(fā)送至基站所需的跳數(shù)就越少，數(shù)據(jù)傳輸失敗的可能性也越小。因而，柵格邊長越大所產(chǎn)生的連帶失效節(jié)點(diǎn)就越少，對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力就越強(qiáng)。當(dāng)然，柵格邊長也不是越大就越好，在上述實(shí)驗(yàn)條件下，如果柵格邊長達(dá)到50m，則所有的柵格都是臨近柵格，也就是說，所有的節(jié)點(diǎn)都直接將數(shù)據(jù)發(fā)送至基站，而且柵格越大，節(jié)點(diǎn)發(fā)送數(shù)據(jù)的距離就越大，能耗也越多，如何確定最優(yōu)的柵格邊長以平衡各方面的性能將是未來研究的重點(diǎn)。

圖6 柵格邊長對SFDA算法的動態(tài)變化適應(yīng)性的影響

將基站位置分別設(shè)置為(100，100)、(100，110)和(110，110)，使基站分別位于柵格頂點(diǎn)、柵格邊界和柵格內(nèi)部，在不同節(jié)點(diǎn)失效概率的情況下，網(wǎng)絡(luò)產(chǎn)生的連帶失效節(jié)點(diǎn)平均數(shù)如圖7所示。上述3種情況產(chǎn)生的連帶失效節(jié)點(diǎn)依次遞增，說明對網(wǎng)絡(luò)動態(tài)變化的適應(yīng)能力依次減弱。主要是因?yàn)榫W(wǎng)絡(luò)中臨近柵格數(shù)目不同而造成的，基站位于柵格頂點(diǎn)時(shí)臨近柵格最多，位于柵格邊界時(shí)次之，位于柵格內(nèi)部時(shí)最少。臨近柵格越多，則直接向基站發(fā)送數(shù)據(jù)的節(jié)點(diǎn)越多，可能出現(xiàn)連帶失效的節(jié)點(diǎn)就越少。另外，臨近柵格越多，為其他柵格內(nèi)節(jié)點(diǎn)向基站傳輸數(shù)據(jù)提供中繼服務(wù)的柵格就越多，以每個(gè)這樣的柵格為中繼的節(jié)點(diǎn)數(shù)目就越少，如果某個(gè)這樣的柵格內(nèi)的所有節(jié)點(diǎn)都失效，其所造成的連帶失效節(jié)點(diǎn)也就越少。因此，應(yīng)設(shè)置基站的位置使得臨近柵格的個(gè)數(shù)盡量多，以提高網(wǎng)絡(luò)的動態(tài)適應(yīng)能力。

圖7 基站位置對SFDA算法的動態(tài)變化適應(yīng)性的影響

再對比幾種算法的能耗。分別為SFDA設(shè)置不同的柵格邊長、基站位置、節(jié)點(diǎn)數(shù)目、網(wǎng)絡(luò)部署區(qū)域邊長，既比較幾種算法的能耗，也對相關(guān)參數(shù)對SFDA能耗的影響進(jìn)行考察。每次條件相同的仿真分別進(jìn)行100輪，統(tǒng)計(jì)節(jié)點(diǎn)發(fā)送消息、接收消息和融合數(shù)據(jù)的能耗。最后，比較不同條件下幾種算法平均每輪整個(gè)網(wǎng)絡(luò)和每個(gè)節(jié)點(diǎn)的能耗，仿真結(jié)果如表2所示。從表中的實(shí)驗(yàn)結(jié)果可以看出，SFDA的能耗在大多數(shù)情況下都高于GIT和PEGASIS，只有在柵格邊長較小時(shí)，SFDA的能耗才低于GIT和PEGASIS，但是，與LEACH相比，SFDA的能耗性能在大多數(shù)情況下都更好，只有在柵格邊長較大時(shí)，SFDA的能耗才高于LEACH。主要是因?yàn)樵贕IT和PEGASIS算法中，節(jié)點(diǎn)只需要向距離較近或距離最近的節(jié)點(diǎn)發(fā)送數(shù)據(jù)，所以它們的能耗性能較好。雖然SFDA算法的能耗性能在某些條件下不及一些能耗性能較好的基于結(jié)構(gòu)算法，卻仍然要優(yōu)于其他一些基于結(jié)構(gòu)算法。

表2 能量消耗仿真結(jié)果

另外，分析能耗仿真結(jié)果可以得出，在其他條件相同時(shí)，柵格邊長越小能耗越小，因?yàn)闁鸥裨叫?，每個(gè)柵格內(nèi)的節(jié)點(diǎn)越少、節(jié)點(diǎn)傳輸數(shù)據(jù)的距離越短，所以接收和發(fā)送數(shù)據(jù)的能耗就越??；基站的位置越靠近網(wǎng)絡(luò)的中心能耗越小，因?yàn)榛驹娇拷W(wǎng)絡(luò)中心，負(fù)責(zé)轉(zhuǎn)發(fā)數(shù)據(jù)的柵格就越少，從而降低了能量消耗；節(jié)點(diǎn)總數(shù)越少能耗越小，因?yàn)楣?jié)點(diǎn)總數(shù)越少則分布在每個(gè)柵格中的節(jié)點(diǎn)也會越少，轉(zhuǎn)發(fā)柵格內(nèi)的節(jié)點(diǎn)接收的數(shù)據(jù)量就越小，從而減小了能耗；網(wǎng)絡(luò)部署范圍越大能耗越小，因?yàn)椴渴鸱秶酱?，每個(gè)柵格內(nèi)的節(jié)點(diǎn)就越少，節(jié)點(diǎn)數(shù)據(jù)接收量減少，但是柵格大小沒有變化，發(fā)送距離也沒有變化，所以能耗也會減小。

7 結(jié)束語

本文分析了WSN在的一些新應(yīng)用中出現(xiàn)的新特點(diǎn)——網(wǎng)絡(luò)動態(tài)變化更加頻繁、對數(shù)據(jù)通信的可靠性要求更高，針對現(xiàn)有數(shù)據(jù)融合算法在這些應(yīng)用中的不足，提出了適用于周期性匯報(bào)式數(shù)據(jù)收集的SFDA算法，它是一種無需在節(jié)點(diǎn)之間建立和維護(hù)結(jié)構(gòu)、采用“多對多”數(shù)據(jù)通信方式的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合算法，對網(wǎng)絡(luò)動態(tài)變化具有很強(qiáng)的適應(yīng)能力，并能夠提供高可靠性的數(shù)據(jù)通信。仿真實(shí)驗(yàn)結(jié)果表明，SFDA在網(wǎng)絡(luò)動態(tài)適應(yīng)性方面具有較大的優(yōu)勢，額外的能耗代價(jià)也較小，能夠滿足新應(yīng)用需求。

本文對無結(jié)構(gòu)數(shù)據(jù)融合這類新穎的數(shù)據(jù)融合算法進(jìn)行了探索式的研究，還有許多內(nèi)容需要進(jìn)一步探討，也有較多問題亟待解決。下一步工作主要包括以下幾個(gè)方面：1)針對不同形狀的網(wǎng)絡(luò)部署區(qū)域、不同的柵格形狀等情況進(jìn)行研究，以增強(qiáng)算法的適用性；2)通過定量的方法確定相關(guān)參數(shù)如柵格邊長的最佳取值，以優(yōu)化算法的性能；3)針對另外一些應(yīng)用中可能出現(xiàn)的節(jié)點(diǎn)分布不均勻、節(jié)點(diǎn)失效概率不同或節(jié)點(diǎn)異構(gòu)等情況，擴(kuò)展算法以提高算法的健壯性和擴(kuò)大算法的應(yīng)用范圍；4)研究提出節(jié)點(diǎn)數(shù)據(jù)傳輸?shù)脑敿?xì)調(diào)度方法。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8):102-114.

[2] 馬祖長, 孫怡寧, 梅濤.無線傳感器網(wǎng)絡(luò)綜述[J].通信學(xué)報(bào), 2004,25(4): 114-124.MA Z C, SUN Y N, MEI T. Survey on wireless sensor network[J].Journal on Communications, 2004, 25(4): 114-124.

[3] KRISHANAMACHARI B, ESTRIN D, WICKER S. The impact of data aggregation in wireless sensor networks[A]. Proceedings of International Workshop of Distributed Event Based Systems[C]. Vienna,Austria, 2002. 575-578.

[4] RAJAGOPALAN R, VARSHNEY P K. Data-aggregation techniques in sensor networks: a survey[J]. IEEE Communications Surveys &Tutorials, 2006, 8(4): 48-63.

[5] INTANAGONWIWAT C, GOVINDAN R, ESTRIN D. Directed diffusion for wireless sensor networks[J]. IEEE/ACM Transcations on Networking, 2003, 11(1): 2-16.

[6] KULIK J, HEINZELMAN W R, BALAKRISHNAN H. Negotiation-based protocols for disseminating information in wireless sensor networks[J]. Wireless Networks, 2002, 8(1): 169-185.

[7] HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[A]. Proceedings of International Conference on System Sciences[C]. San Francisco: IEEE Computer Society, USA, 2000.3005-3014.

[8] YOUNIS O, FAHMY S. HEED: a hybrid, energy- efficient, distributed clustering approach for ad hoc sensor networks[J]. IEEE Transcations on Mobile Computing, 2004, 3(4): 366-379.

[9] KRISHNAMACHARI B, ESTRIN D, WICKER S. Modeling data centric routing in wireless sensor networks[A]. Proceedings of IEEE International Conference on Information Communications[C]. New York: IEEE Computer Society, USA, 2000. 1-18.

[10] LINDSEY S, RAGHAVENDRA C. PEGASIS: power-efficient gathering in sensor information systems[A]. Proceedings of IEEE Aero-space Conference[C]. Montana: IEEE Aerospace and Electronic Systems Society, USA, 2002. 1125-1130.

[11] TABASSUM N, URANO Y, HAQUE A. GSEN: an efficient energy consumption routing scheme for wireless sensor network[A]. Proceedings of IEEE International Conference on Networking[C]. Washington: IEEE Computer Society, USA, 2006. 117-122.

[12] OKEKE B C, LAW K L E. Multi-level clustering architecture and protocol designs for wireless sensor networks[A]. Proceedings of International Conference on Wireless Internet[C]. Hawaii, USA,2008. 1-9.

[13] CHAO C M, HSIAO T Y. Structure-free data aggregation in sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(8):929-942.

[14] FAN K W, LIU S, SINHA P. Design of structure-free and energy-balanced data aggregation in wireless sensor networks[A]. Proceedings of IEEE International Conference on High Performance Computing and Communications[C]. Washington: IEEE Computer Society, USA, 2009. 222-229.