無(wú)線感應(yīng)器網(wǎng)路上具省能與強(qiáng)健性之資料聚集設(shè)計(jì)

1、無(wú)線感應(yīng)器網(wǎng)路上具省能與強(qiáng)健性之資料聚集設(shè)計(jì)陳建群國(guó)防大學(xué)國(guó)防管理學(xué)院國(guó)防資訊研究所.tw伍臺(tái)國(guó)國(guó)防大學(xué)國(guó)防管理學(xué)院國(guó)防資訊研究所.tw摘要無(wú)線感應(yīng)器網(wǎng)路因感應(yīng)器可使用的資源相對(duì)有限，如何有效的利用能源，已成為近來(lái)被廣為討論的議題。資料聚集（Data Aggregation）技術(shù)將不同來(lái)源的感應(yīng)器所偵測(cè)到的資料，先行經(jīng)過(guò)整合，去除重覆的訊息後，再傳回目的節(jié)點(diǎn)，如此能減少資料傳輸次數(shù)，縮小資料量，不僅可以減少感應(yīng)器能源的消耗，也可以降低資料發(fā)生碰撞的機(jī)會(huì)，進(jìn)而有效的利用頻寬資源。此外，當(dāng)感應(yīng)器網(wǎng)路因移動(dòng)或節(jié)點(diǎn)的加入或分離造成

2、網(wǎng)路拓?fù)浒l(fā)生改變時(shí)，也要能不影響執(zhí)行效能，能適應(yīng)環(huán)境的改變。本文探討有向性散佈繞徑（Directed Diffusion Routing）的資料聚集設(shè)計(jì)機(jī)制，研究其對(duì)於感應(yīng)器網(wǎng)路上省能與強(qiáng)健性效益，並結(jié)合資料聚集推測(cè)指標(biāo)，分析其對(duì)原方法效能上的增益情形。關(guān)鍵字：無(wú)線感應(yīng)器網(wǎng)路、資料聚集、有向性散佈繞徑、省能、強(qiáng)健度壹、引言感應(yīng)器網(wǎng)路是一種特殊的無(wú)線網(wǎng)路架構(gòu)，發(fā)展起源最早可以上溯至50年代美蘇冷戰(zhàn)時(shí)期【6】，但是受限當(dāng)時(shí)設(shè)計(jì)上的軟硬體限制與技術(shù)的無(wú)法配合，使得感應(yīng)器網(wǎng)路發(fā)展受到阻礙。到了80年代，許多的感應(yīng)器網(wǎng)路陸續(xù)的被開發(fā)，但多僅限於軍事上的應(yīng)用。直到90年代以來(lái)，由於微機(jī)電系統(tǒng)(Microe

3、letronics Mechanism System，MEMS)提倡，感應(yīng)器的體積大大的縮小，製造成本降低、處理速度加快、電池儲(chǔ)備能力增加與無(wú)線通信技術(shù)的進(jìn)步，帶動(dòng)感應(yīng)器網(wǎng)路研究的另一波興盛。感應(yīng)器網(wǎng)路由成千上百的感應(yīng)器節(jié)點(diǎn)所組成，每一個(gè)感應(yīng)器具有運(yùn)算（Computing）、存儲(chǔ)（Storage）、感測(cè)（Sensing）、通信（Communication）之功能，能偵測(cè)週遭的事物或環(huán)境，將感測(cè)到的結(jié)果傳送到目的端 ，並具有建置快、成本低、適應(yīng)性高等優(yōu)點(diǎn)，目前已被廣泛的應(yīng)用於動(dòng)植物觀察、軍事情資、環(huán)境偵測(cè)（如潮汐高低、冰河活動(dòng)、森林動(dòng)植物分佈）、醫(yī)療看護(hù)、數(shù)位家庭等領(lǐng)域之中【9】。感應(yīng)器因物理上

4、的特性，諸如運(yùn)算能力、記憶體大小、傳輸有效範(fàn)圍、資料傳輸頻寬等先天限制下，能使用的資源相當(dāng)有限【2】，而且多被用於險(xiǎn)惡危險(xiǎn)的環(huán)境中擔(dān)任偵察工作，不易進(jìn)行能源替補(bǔ)；在此前提之下，如何使資源達(dá)到最有效的安排應(yīng)用，延長(zhǎng)感應(yīng)器的使用壽命，已成為感應(yīng)器網(wǎng)路上相當(dāng)重要的研究課題。一個(gè)簡(jiǎn)單的想法，便是藉由減少資料處理（傳送、接收、運(yùn)算、存儲(chǔ)等）所耗損的能量，以增加感應(yīng)器的使用時(shí)間，諸如經(jīng)由編碼壓縮資料【12】、增加資料關(guān)係度【7】、資料整合再傳【1】等等。資料聚集技術(shù)【3】【5】【14】能解決上述的感應(yīng)器在能源使用上所遇到的難題。資料聚集將每個(gè)感應(yīng)器所偵察到的資料，先行經(jīng)過(guò)篩選去除重覆的資訊，會(huì)整後由感應(yīng)器

5、節(jié)點(diǎn)傳送到匯集點(diǎn)（Sink Node）上【11】。換言之，也就是透過(guò)減少資料的傳送量與傳送次數(shù)，縮減感應(yīng)器不必要的傳送次數(shù)，以節(jié)省能源的耗損，延長(zhǎng)感應(yīng)器壽命。除此之外資料聚集的採(cǎi)用，也可以降低資料碰撞（Data Collision）次數(shù)，避免網(wǎng)路擁塞（Network Congestion）發(fā)生機(jī)會(huì)。貳、文獻(xiàn)探討由於感應(yīng)器的感測(cè)範(fàn)圍有相互重疊的部份，同一個(gè)事件可能觸發(fā)多個(gè)感應(yīng)器進(jìn)行資料回報(bào)，當(dāng)資料不經(jīng)先行的過(guò)濾處理，將造成重覆資料的回傳。聚集技術(shù)將不同節(jié)點(diǎn)所傳來(lái)的資訊，先行送往資料聚集點(diǎn)（Aggregator Node）處理，去除掉重覆的部份後再傳送到終端，如此可以降低傳送次數(shù)與減少封包傳送量，

6、不僅能節(jié)省能源，有效利用頻寬，並且只傳送扼要的訊息，減少使用者對(duì)於訊息的分析時(shí)間。感應(yīng)器所感測(cè)到的資料在不經(jīng)處理的情況下便傳送到使用端，將對(duì)終端造成大量的處理負(fù)荷。為了提高來(lái)源資料的正確性與節(jié)省使用者的處理時(shí)間，將感測(cè)資料加以結(jié)合，僅回傳扼要的資料是必要的。如下圖一顯示出感應(yīng)器網(wǎng)路資料聚集處理方式與沒有進(jìn)行資料聚集處理時(shí)的差別。 來(lái)源1來(lái)源2來(lái)源3來(lái)源1來(lái)源2來(lái)源3（一）未經(jīng)過(guò)資料聚集處理的訊息傳送（二）經(jīng)過(guò)資料聚集處理的訊息傳送聚集點(diǎn)聚集點(diǎn)匯集點(diǎn)匯集點(diǎn)圖一 感應(yīng)器網(wǎng)路資料聚集處理示意圖根據(jù)無(wú)線訊號(hào)傳輸?shù)奶匦?，兩?jié)點(diǎn)間的傳輸耗能與距離的成二次方比，而與資料量的大小成正比【10】，資料聚集將來(lái)源

7、感應(yīng)器所回報(bào)的資料，先經(jīng)過(guò)處理去除其中重覆的部份，以減少傳送時(shí)的資料量，同時(shí)也能降低不必要的傳送次數(shù)，避免通道發(fā)生壅塞；又由於回傳訊息次數(shù)減少，將使節(jié)點(diǎn)在回傳訊息發(fā)生碰撞機(jī)會(huì)減低，能提高回報(bào)資料的正確性。研究【3】中，證實(shí)感應(yīng)器網(wǎng)路上使用資料聚集方法回傳資料能達(dá)到以下效能： -（1）其中ND代表以資料中心導(dǎo)向（Data-centric）協(xié)定在最佳情況的所需的傳輸次數(shù)；NA為位址中心導(dǎo)向（Address-centric）協(xié)定在最佳情況下所需的傳輸次數(shù)，d為來(lái)源節(jié)點(diǎn)與匯集點(diǎn)間的最短距離，k為來(lái)源節(jié)點(diǎn)的數(shù)目。由上述可知，當(dāng)來(lái)源節(jié)點(diǎn)數(shù)很多時(shí)，使用資料聚集方法比不採(cǎi)用時(shí)，在最佳的情況下可以提高k倍的效能

8、。由於資料聚集所帶來(lái)的效能增效，目前許多無(wú)線感應(yīng)器網(wǎng)路路由方法都加入資料聚集處理技術(shù)，以增加電源的使用效能與延長(zhǎng)網(wǎng)路壽命。在PEGASIS（Power Efficient Gathering in Sensor Information Systems）【15】中，感應(yīng)節(jié)點(diǎn)構(gòu)成鏈狀（Chain-based）架構(gòu)，每一個(gè)節(jié)點(diǎn)只與其相鄰節(jié)點(diǎn)直接進(jìn)行通聯(lián)。資料在相鄰節(jié)點(diǎn)間進(jìn)行蒐整，之後透過(guò)鄰居節(jié)點(diǎn)的轉(zhuǎn)送到達(dá)匯集點(diǎn)。首先，在網(wǎng)路挑選距離匯集點(diǎn)最遠(yuǎn)的感應(yīng)節(jié)點(diǎn)作為起始點(diǎn)，然後利用貪進(jìn)演算法 （Greedy Incremental Algorithm）將距離起始點(diǎn)最近的節(jié)點(diǎn)加入鏈中，以在起始點(diǎn)與匯集點(diǎn)間建立一

9、條最短傳輸路徑。鏈中會(huì)有一個(gè)稱為 Leader的節(jié)點(diǎn)負(fù)責(zé)聚集其它節(jié)點(diǎn)所傳送資料，並將處理後的資料傳送到匯集點(diǎn)上。在 Leader的決定方法上，假設(shè)網(wǎng)路中有N個(gè)節(jié)點(diǎn)，則在資料收集的第k回合，由鏈路中第k mod N之節(jié)點(diǎn)擔(dān)任領(lǐng)導(dǎo)點(diǎn)。此種機(jī)制將能解決負(fù)載不平衡問(wèn)題。但是由於領(lǐng)導(dǎo)點(diǎn)排程上的問(wèn)題，當(dāng)距離匯集點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)擔(dān)任領(lǐng)導(dǎo)點(diǎn)的時(shí)候，會(huì)耗費(fèi)較多的電力傳送彙整資料，如此將使其提前耗盡電源。LEACH（Low Energy Adaptive Clustering Hierarchy）【17】是一個(gè)週期性的資料聚集機(jī)制，在操作上，數(shù)個(gè)相鄰近的感應(yīng)器能夠組成一個(gè)叢集（Cluster），使用機(jī)率法則選出一個(gè)感

10、應(yīng)器擔(dān)任群首（Cluster Head）的角色，負(fù)責(zé)收集同一叢集中其它感應(yīng)器的資料，進(jìn)行資料聚集處理後傳送到匯集點(diǎn)上。由於除了群首外，其它的感應(yīng)器不會(huì)將偵測(cè)到的資料回傳到匯集點(diǎn)上，能減少回傳次數(shù)；又因?yàn)橹馗残缘馁Y料已先經(jīng)由群首處理過(guò)，能減少傳送的資料，使得LEACH能有效的節(jié)省電源的消耗。但是此方法在群首間具有負(fù)載不平衡的問(wèn)題，因節(jié)點(diǎn)密度較高區(qū)域的群首消耗電源相對(duì)較快，而遠(yuǎn)離群首較遠(yuǎn)的節(jié)點(diǎn)，在資料回傳上需耗用較大的能量，如何決定網(wǎng)域中的群首數(shù)目與群首的挑選，便顯得十分重要。在論文【16】中，作者將改良LEACH，提出E-LEACH（Enhanced-LEACH）方法，最大不同的地方在於傳輸前，

11、會(huì)將進(jìn)行回報(bào)的組頭排列成鏈狀架構(gòu)。所有的組頭會(huì)先對(duì)其組員所傳送的資料進(jìn)行資料聚集處理，在將處理後的資料回傳匯集點(diǎn)前，以距離匯集點(diǎn)最遠(yuǎn)的組頭進(jìn)行貪進(jìn)演算法，在所有的組頭與匯集點(diǎn)間建立一條傳輸鏈路，再?gòu)穆窂街械乃薪M頭中選出一個(gè)組頭擔(dān)任“Super Cluster Head”擔(dān)任聚集點(diǎn)，接收所有組頭所傳送來(lái)的資料後，進(jìn)行第二階段的資料聚集後再回傳資料給匯集點(diǎn)。作者以模擬分析結(jié)果顯示E-LEACH較LEACE有更高的省能效益。AFST（Adaptive Fusion Steiner Tree）【8】是一個(gè)具有推論（Heuristic）功能的路由協(xié)定，能根據(jù)傳送時(shí)的資料關(guān)係度、傳輸耗能、資料聚集耗能、

12、網(wǎng)路拓?fù)淝樾闻袛嗍欠襁M(jìn)行資料聚集。AFST演算法分成兩個(gè)階段，在第一階段先將節(jié)點(diǎn)排列成樹狀結(jié)構(gòu)，再進(jìn)行資料來(lái)源節(jié)點(diǎn)配對(duì)，根據(jù)最省能的傳輸方式，使來(lái)源點(diǎn)兩兩成為一組（Matched Pair）, 每一組代表一條邊,每條邊以資料代表度較佳者擔(dān)任資料聚集點(diǎn)；在第二個(gè)階段，則進(jìn)行傳輸電力耗用計(jì)算，將所有的邊分成兩個(gè)集合，使得有進(jìn)行資料聚集處理的邊集合耗能與沒有進(jìn)行資料聚集處理的邊集合耗能之總合最小，得到最佳的資料聚集處理情形，如此一來(lái)，節(jié)點(diǎn)間不必要的資料聚集處理將不會(huì)發(fā)生，能減少不當(dāng)聚集處理所造成的電力消耗。參、有向性散佈繞徑方法Directed Diffusion（有向性散佈）【4】是一個(gè)具有省能、

13、強(qiáng)健性、規(guī)模性的感應(yīng)器網(wǎng)路資料傳送技術(shù)，採(cǎi)用1資料中心導(dǎo)向路由（Data-centric Routing）方法。它包含幾種主要的元件：需求訊息（Interests Message）、資料訊息（Data Message）、梯度（Gradients）與連線的更新（Reinforcement ）。需求訊息定義了使用者所要詢問(wèn)的事情，告訴感應(yīng)器網(wǎng)路想取得的資訊。資料訊息是指感應(yīng)器將符合使用則需求的感測(cè)資料，經(jīng)過(guò)蒐集與處理後，所回報(bào)給使用者的有用資訊，可視為對(duì)於感測(cè)到的實(shí)際現(xiàn)象所做的簡(jiǎn)單描述。在Directed Diffusion中，需求與資料訊息的內(nèi)容是以屬性值組（Attribute-value Pa

14、irs）的方式做為描述。例如，使用者想找某個(gè)人員的位置時(shí)，會(huì)傳出 type=human, location=20,50 的需求訊息，告知感測(cè)節(jié)點(diǎn)所要偵測(cè)的物體種類與位置。梯度是一種傳輸路徑的紀(jì)錄，當(dāng)需求訊息在節(jié)點(diǎn)間傳送的時(shí)候，接收端會(huì)紀(jì)錄來(lái)源端所在，並在兩者間建立一條梯度連線，以做為之後訊息回傳的有效路徑。又由於需求回報(bào)訊息會(huì)沿著不同的路徑回傳給使用者，使用者必需進(jìn)行路徑更新，經(jīng)過(guò)效益評(píng)估運(yùn)算後，從中挑選最佳的路徑，供來(lái)源節(jié)點(diǎn)繼續(xù)進(jìn)行資料回傳，並中斷其它回傳傳路徑。Directed Diffusion上主要元件與運(yùn)行步驟示意如下圖二所示。（三）路徑更新（一）需求傳送（二）資料回報(bào)圖二 Dire

15、cted Diffusion 元件與運(yùn)行步驟示意圖-1感應(yīng)器網(wǎng)路上路由協(xié)定可分成兩大類：第一類為資料中心導(dǎo)向（Data-centric Protocol）,來(lái)源節(jié)點(diǎn)以hop-by-hop方式進(jìn)行資料回傳，回傳路徑上的中介點(diǎn)知道封包的內(nèi)容，去除相同的資料後經(jīng)過(guò)整合再傳回匯集點(diǎn)。第二類是位址導(dǎo)向協(xié)定（Address-centric Protocol）,每個(gè)來(lái)源點(diǎn)直將資料透過(guò)最短路徑回傳給匯集點(diǎn)，以end-by-end的方式回傳資料，不經(jīng)其它節(jié)點(diǎn)傳送與任何資料處理工作。一、運(yùn)行方式Direct Diffusion在運(yùn)作上分成三大階段：第一階段為需求傳送階段，匯集點(diǎn)透過(guò)廣播（Flooding）的方式將

16、需求訊息告訴網(wǎng)域中的相鄰節(jié)點(diǎn)，相鄰節(jié)點(diǎn)再將訊息傳送給它的鄰居節(jié)點(diǎn)，直到網(wǎng)域中所有的節(jié)點(diǎn)都接受到需求訊息為止。而接收端會(huì)與傳送端建立一條梯度連線，以追蹤訊息的傳遞路徑，以做為事後訊息回報(bào)路徑；第二階段為資料回報(bào)階段，來(lái)源節(jié)點(diǎn)將符合匯集點(diǎn)需求的資訊，沿著先前建立的梯度連線傳送到匯集點(diǎn)上，在回傳同時(shí)，中繼節(jié)點(diǎn)會(huì)進(jìn)行資料處理，將重覆的資訊去除；第三階段為路徑更新階段，當(dāng)匯集點(diǎn)接收到眾多不同路徑回傳的訊息後，會(huì)從中找出訊息品質(zhì)最佳的做為傳輸路由，而當(dāng)回傳訊息的品質(zhì)降低時(shí)進(jìn)行路徑修復(fù)，以維持最佳的傳輸品質(zhì)。由於來(lái)源端可能會(huì)經(jīng)由多條不同的路徑將資料傳送到匯集點(diǎn)上，這樣將影響資料傳送的品質(zhì)。所以匯集點(diǎn)會(huì)進(jìn)行傳

17、輸路徑最佳化（Transmission Path Reinforcement）調(diào)整，也就是選擇傳送耗能上最小的路徑傳輸。之後，這些被還擇的節(jié)點(diǎn)會(huì)依照上述的方法重新建立梯度。當(dāng)有某來(lái)源區(qū)的回報(bào)資料的品質(zhì)下降（例如錯(cuò)誤增加，或延遲增加）時(shí)，中繼節(jié)點(diǎn)可以發(fā)出否定更新（Negatively Reinforce）訊息將傳送路徑中表現(xiàn)不佳的節(jié)點(diǎn)剔除，而選擇其它傳輸表現(xiàn)佳的節(jié)點(diǎn)加到傳送路徑之中，以適應(yīng)動(dòng)態(tài)變動(dòng)的網(wǎng)路環(huán)境。二、網(wǎng)路模式感應(yīng)器網(wǎng)路上有許多種網(wǎng)路情境，不同的網(wǎng)路情境會(huì)造成不一樣的傳輸方式或應(yīng)用結(jié)果，為了讓整個(gè)網(wǎng)路環(huán)境有個(gè)清楚的藍(lán)圖，本研究假設(shè)感應(yīng)器網(wǎng)路的情境如下：（一）網(wǎng)路中的感應(yīng)器節(jié)點(diǎn)分為三類，

18、第一類為來(lái)源節(jié)點(diǎn)，負(fù)責(zé)回傳感測(cè)資訊；第二類為聚集點(diǎn)，將來(lái)源點(diǎn)的訊息進(jìn)行資料聚集處理後傳回使用終端；第三類為匯集點(diǎn)，接收聚集點(diǎn)所回傳的訊息，扮演網(wǎng)路中的使用終端角色。（二）所有的感應(yīng)器節(jié)點(diǎn)都是同性質(zhì)的（Homogeneous）,在傳輸上有能源限制，且不能更換電力裝置。（三）所有感應(yīng)節(jié)點(diǎn)都知道彼此的位置，可以藉由Hop-by-hop方式進(jìn)行連線。（四）所有的節(jié)點(diǎn)具有快取記憶體（Cache），能了解傳輸時(shí)的訊息內(nèi)容。（五）節(jié)點(diǎn)具有運(yùn)算能力，僅會(huì)進(jìn)行網(wǎng)域內(nèi)（In-network）的資料聚集處理與訊息傳輸。（六）所有的感測(cè)節(jié)點(diǎn)與匯集點(diǎn)位置上是固定的，或僅做低速移動(dòng)。肆、資料聚集推測(cè)性指標(biāo)一、問(wèn)題陳述在D

19、irected Diffusion架構(gòu)之下，並非在所有的情況下，採(cǎi)用資料聚集比節(jié)點(diǎn)直接回傳可以達(dá)到省能的效果。由於使用資料聚集方法時(shí)，必需先將來(lái)源節(jié)點(diǎn)的資料先進(jìn)行彙整，若彙整的資料量大時(shí)，將消耗過(guò)多的能源做運(yùn)算處理，也就是說(shuō)，當(dāng)直接傳送資料的耗能比採(cǎi)用資料聚集後再傳送的耗能來(lái)的低時(shí)，不使用資料聚集的省能效果反而較佳。此外，若資料聚集所回傳的資料的融合率（Fusion Ratio, 融合後的資料量/融合前的總資料量）不高時(shí)，使用資料聚集不但難以達(dá)到省能的效果，反而可能因?yàn)樘幚泶罅抠Y料的融合運(yùn)算，而造成回應(yīng)時(shí)間（Latency）的增加, 與過(guò)多的運(yùn)算能源浪費(fèi)。因此，如何配合感應(yīng)器網(wǎng)路的情境，如傳輸

20、耗能、融合耗能、網(wǎng)路拓?fù)?、資料關(guān)聯(lián)度等等，以推測(cè)性的考量觀點(diǎn)判定是否使用資料聚集方法來(lái)處理回傳的資料，將能提升資料聚集所帶來(lái)的效益。二、相關(guān)研究 近來(lái)有許多推論式資料聚集方法被提出。在文【13】中，利用統(tǒng)計(jì)方法做為評(píng)斷是否回傳感測(cè)訊息的方法，稱為 Statistical Aggregation Method，以減少來(lái)源節(jié)點(diǎn)不必要的資料傳輸，節(jié)省能源的消耗。在判別資料差異度上，由管理者設(shè)立一個(gè)門檻值（Threshold）判斷來(lái)源節(jié)點(diǎn)是否需回傳資料，也就是當(dāng)- （2）-（3）則回傳資料，否則則不進(jìn)行資料回傳。其中為時(shí)間t資料的偵測(cè)資料量的平均值；則代表偵測(cè)資料量的標(biāo)準(zhǔn)差，亦即只有當(dāng)資料量

21、的變化超過(guò)門檻值時(shí)，來(lái)源節(jié)點(diǎn)才會(huì)回報(bào)資訊。不過(guò)這種方法只能觀查到資料量上的變化，在資料質(zhì)上的變化將無(wú)法度量。在【16】提出資料聚集品質(zhì)度（Data Aggregation Quality, DAQ），用以量測(cè)進(jìn)行資料聚集處理後資料品質(zhì)好壞的指標(biāo)，做為評(píng)斷資料聚集協(xié)定QoS的標(biāo)準(zhǔn)。DAQ表達(dá)如下： -（4） 公式（4）中，Ei代表來(lái)源節(jié)點(diǎn)i的偵測(cè)事件；k為進(jìn)行資料聚集的節(jié)點(diǎn)數(shù)；Li為每個(gè)節(jié)點(diǎn)所包含的資料量；Lfusion為資料聚集處理後的資料量；Hfusion為所有感測(cè)範(fàn)圍內(nèi)偵測(cè)事件所成的聯(lián)集數(shù)量，rfusion資料壓縮率。研究中顯示當(dāng)DAQ越高時(shí)，採(cǎi)用資料聚集來(lái)傳送資料達(dá)到省能的效果就越明顯。

22、文章【8】提出能根據(jù)資料關(guān)係度、傳輸耗能、資料聚集耗能、網(wǎng)路拓蹼情形判斷是否進(jìn)行資料聚集的AFST路由設(shè)計(jì)。當(dāng)將資料直接傳送給匯集點(diǎn)所耗的能量比進(jìn)行資料聚集再傳送給匯集節(jié)的還省能的時(shí)候，不使用資料聚集能節(jié)省更多的電力。聚集點(diǎn)在回傳訊息給匯集點(diǎn)前會(huì)先計(jì)算資料聚集淨(jìng)效益E:E=cw（u）+w（v）（1-uv）SP（v, sink）+ qw（u）+ w（v）-cw（u）+ w（v） SP（v, sink） -（5） (1-uv)為資料壓縮率；c為每單位資料的傳送耗能；q為每單位資料聚集耗能；w（i）代表節(jié)點(diǎn)i的資料量；SP（v, sink）代表節(jié)點(diǎn)v到Sink node的最短路徑。所以當(dāng)E小於0時(shí)，

23、則進(jìn)行資料聚集處再傳送資料；若E大於0，則不進(jìn)行資料聚集，由最短路徑回傳資料到匯集點(diǎn)。三、結(jié)合推論指標(biāo)的有向性散佈繞徑方法根據(jù)上述論文【8】【13】【16】，我們提出一個(gè)改良的資料聚集推論指標(biāo)，應(yīng)用到Directed Diffusion 上。為了方便效能方析，假設(shè)網(wǎng)路中的節(jié)點(diǎn)排列成如下圖三的網(wǎng)格狀環(huán)境，感測(cè)區(qū)A與感測(cè)區(qū)B中分別由節(jié)點(diǎn)u與節(jié)點(diǎn) v擔(dān)任資料聚集點(diǎn)，負(fù)責(zé)收集感測(cè)區(qū)內(nèi)來(lái)源節(jié)點(diǎn)（如圖三中的SA1,SA2,SB1,SB2）的資料，w（u）與w（v）代表節(jié)點(diǎn)u與v所會(huì)整後的資料量；在第二階資料傳送中，若由v擔(dān)任回報(bào)點(diǎn)，根據(jù)公式（5）當(dāng)資料由u送往v進(jìn)行資料聚集的時(shí)候，所需耗用的能量為 cw（

24、u）+ w（v）(1-uv)+qw（u）+w（v）。ABuvsB2sB1sA1sA2匯集點(diǎn)L hops圖三 採(cǎi)用網(wǎng)格狀感應(yīng)器拓?fù)涞挠邢蛐陨牙@徑傳輸環(huán)境為了做區(qū)別，我們以w（v）= w（u）+w（v）(1-uv)，代表節(jié)點(diǎn)v進(jìn)行資料聚處理後的資料量。若v與匯集點(diǎn)距離L Hops此時(shí)，當(dāng)v將資料傳送到匯集點(diǎn)時(shí)將耗用：L*cw（u）+w（v）(1-uv)+qw（u）+w（v）-（6）相反地，若v不進(jìn)行資料聚集處理，直接由最短路徑將資料傳送回匯集點(diǎn)將耗用能量：L*cw（u）+w（v） -（7）將公式（6）減去公式（7），可以得知當(dāng)uv >q /L* c時(shí)，進(jìn)行資料聚集才符合省能效益。再根據(jù)公式

25、（4），此時(shí)在v進(jìn)行資料聚集的DAQ為：-（8）根據(jù)公式（8），所得到的DAQ數(shù)據(jù)使用者可以自行定出一個(gè)門檻值T，判斷資料由v回傳至匯集點(diǎn)前是否要進(jìn)行資料聚集處理，只有在DAQ > T的情況下才會(huì)進(jìn)行資料聚集處理，如此能進(jìn)一步的減少不必要的資料聚集處理所造成的電源消耗，提升Directed Diffusion的省能效益。伍、效能分析在省能效益分析中，Directed Diffusion在節(jié)點(diǎn)回應(yīng)需求訊息時(shí)，採(cǎi)用資料聚集的方法將重覆資訊去除，減少回報(bào)訊息的資料量，在文章【4】中的模擬實(shí)驗(yàn)中顯示，Directed Diffusion比單純使用Flooding或Omniscient Multi

26、cast有40%以上的省能效益；而當(dāng)原來(lái)的傳輸速度變慢，會(huì)中斷原來(lái)的傳輸路徑，重新挑出最省能的傳輸路徑，這種路徑更新機(jī)制能也能有效的減少能源的耗用。此外，本文在原有的機(jī)制中，增加資料聚集推論指標(biāo)做為判斷資料聚集處理時(shí)機(jī)的依據(jù)，避免不當(dāng)?shù)馁Y料聚集處理所造成的能源消耗，更能進(jìn)一步評(píng)估回傳資料的品質(zhì)好壞，提供使用者正確而可靠的回報(bào)資訊。在強(qiáng)健度分析上，Directed Diffusion利用節(jié)點(diǎn)中的Cache紀(jì)錄過(guò)去的傳輸路徑，當(dāng)各種外部原因造成線路中斷時(shí)，路徑的中界點(diǎn)可以根據(jù)Cache重建傳輸連線，恢復(fù)回傳路徑；當(dāng)回報(bào)訊息的傳輸延遲時(shí)間增加時(shí)，匯集點(diǎn)會(huì)自行中斷原來(lái)的傳輸路徑，再利用Cache中的過(guò)

27、去Gradients情況，從中挑選出最佳路徑，使得網(wǎng)路連線根據(jù)網(wǎng)路拓?fù)渥兓龀鲞m當(dāng)?shù)恼{(diào)整，保持連線品質(zhì)。陸、結(jié)論與未來(lái)研究方向資料聚集技術(shù)可以去除感應(yīng)節(jié)點(diǎn)重覆的回報(bào)資料，減少資料傳輸量與傳輸次數(shù)，不僅能使網(wǎng)路節(jié)點(diǎn)間的碰撞發(fā)生次數(shù)減少，更能提升頻寬的使用率，增加網(wǎng)路節(jié)點(diǎn)的使用壽命。Directed Diffusion是一個(gè)具有省能、強(qiáng)健性、規(guī)模性的感應(yīng)器網(wǎng)路繞徑方法，利用資料聚集技術(shù)傳送需求回應(yīng)訊息到集點(diǎn)上，能達(dá)到感應(yīng)器網(wǎng)路整體傳輸上省能與強(qiáng)健度的提升。本研究延伸了推論式資料聚集方法的構(gòu)想，簡(jiǎn)單地設(shè)計(jì)出一個(gè)適合Directed Diffusion的量測(cè)指標(biāo)，在未來(lái)的研究中，我們會(huì)進(jìn)一步利用模擬軟

28、體驗(yàn)證其可行性，以求得精確的省能效益評(píng)估；並且嚐試應(yīng)用到其它的資料聚集方法中，以了解推論指標(biāo)的普遍性效能增益情況。柒、參考文獻(xiàn)1 Asheq Khan, Data Fusion in Sensor Networks, Online Available in The State University of New York, http:/ /qiao/cse620/fall04 /Data_Fusion.ppt , Aug 2004.2 Akyildiz, I.F, Weilian Su, Sankarasubramaniam Y. , and Cayirci, E. , A Survey on

29、 Sensor Networks, in Proc. IEEE Communications Magazine, Vol.40,  Issue 8, Aug. 2002, pp.102-113.3 Bhaskar Krishanamachari, Deborah Estrin , and Stephen Wicker. The Impact of Data Aggregation in Wireless Sensor Networks, In Proc. International Workshop of Distributed Event Based Systems (D

30、EBS), Vienna, Austria, July 2002, pp.1-4.4 Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, John Heidemann, and Fabio Silva, Directed Diffusion for Wireless Sensor Networking, in Proc. ACM/IEEE Transactions on Networking, Vol.11, NO.1, Feb.2002, pp. 2-16.5 Chalermek Intanagonwiwat, Deborah

31、 Estrin , Ramesh Govindan, and John Heidemann, Impact of Network Density on Data Aggregation in Wireless Sensor Networks, In Proc.22nd International Conference on Distributed Computing Systems, Vienna, Austria, July, 2002, pp.5-9.6 Chee-Yee Chong, and Srikanta P. Kumar, Sensor Networks: Evolution, O

32、pportunities, and Challenges, in Proc. Proceedings of the IEEE, Vol. 91, No. 8, Aug. 2003, pp.1248-1250. 7 Himanshu Gupta, Vishnu Navda, Samir R. Das, and Vishal Chowdhary, Efficient gathering of correlated data in sensor networks, in Proc. 6th ACM international symposium on Mobile ad hoc netwo

33、rking and computing MobiHoc '05, May 2005, pp.405-407.8 Hong Luo, Jun Luo, and Yonghe Liu , Energy efficient routing with adaptive data fusion in sensor networks, in Proc. 2005 joint workshop on Foundations of mobile computing DIALM-POMC '05, Sep. 2005, pp.80-88.9 Kay Romer, and Friedemann M

34、attern, The Design Space of Wireless Sensor Networks, in Proc. IEEE Wireless Communication, Vol. 11, Issue 6, Dec. 2004, pp.57 61.10 K. Dasgupta, K. Kalpakis , and P. Namjoshi, An Efficient Clustering-based Heuristic for Data Gathering and Aggregation in Sensor Networks, in Proc. IEEE WCNC 2003.11 K. Vaidyanathan, S. Sur, S. Narravula, and P. Sinha. Data Aggregation Techniques in Sensor Networks, in Proc. Department of Computer Science and Engineering of The Ohio State University,OSU-CISRC-11/04-T