第15章-物聯(lián)網(wǎng)通信技術(shù)(曾憲武)LXX2014.7

第15章WSN的拓?fù)淇刂?5.1功率控制15.2層次型拓?fù)浣Y(jié)構(gòu)控制15.3啟發(fā)機(jī)制本章小結(jié)15.1功率控制

15.1.1基于節(jié)點(diǎn)度的算法

“度”是圖論中的一個(gè)概念，是指圖中的某個(gè)頂點(diǎn)與其相連接的邊的個(gè)數(shù)。WSN可以抽象為一個(gè)圖，WSN中的節(jié)點(diǎn)是所抽象的圖的一個(gè)頂點(diǎn)。因此，一個(gè)節(jié)點(diǎn)的度數(shù)是指所有距離該節(jié)點(diǎn)一跳的鄰居節(jié)點(diǎn)的數(shù)目。基于節(jié)點(diǎn)度的算法的核心思想是給定節(jié)點(diǎn)度的上限和下

限需求，動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的發(fā)射功率，使得節(jié)點(diǎn)的度數(shù)落在上限和下限之間。基于節(jié)點(diǎn)度的算法利用局部信息來調(diào)整相鄰節(jié)點(diǎn)間的連通性，從而保證整個(gè)網(wǎng)絡(luò)的連通性，同時(shí)保證節(jié)點(diǎn)間的鏈路具有一定的冗余性和可擴(kuò)展性。1.本地平均算法

本地平均算法的步驟如下：

(1)開始時(shí)所有節(jié)點(diǎn)均具有相同的發(fā)射功率TransPower0，每個(gè)節(jié)點(diǎn)定期廣播一個(gè)包含自己ID的LifeMsg。

(2)如果節(jié)點(diǎn)接收到LifeMsg消息，則發(fā)送一個(gè)LifeAckMsg應(yīng)答消息。該消息中包含應(yīng)答的LifeMsg消息中的節(jié)點(diǎn)ID。(3)每個(gè)節(jié)點(diǎn)在下一次發(fā)送LifeMsg時(shí)，首先檢查已經(jīng)收到的LifeAckMsg消息，利用這些消息統(tǒng)計(jì)出自己的鄰居數(shù)NodeResp。

(4）如果NodeResp小于鄰居數(shù)下限NodeMinThresh，那么節(jié)點(diǎn)在這次發(fā)射時(shí)將增大發(fā)射功率，但發(fā)射功率不能超過初始發(fā)射功率的Bmax倍，其發(fā)射功率為TransPower={min［Bmax，Ainc×(ModeMinThresh－

NodeResp)］}×TransPower0(15.1.1)

同樣，如果NodeResp大于鄰居節(jié)點(diǎn)的上限NodeMaxThresh，則需要減小發(fā)射功率為

TransPower={min［Bmin,Adec×(1-(ModeMaxThresh－NodeResp))］}×TransPower0(15.1.2)

在上兩式中，Bmax、Bmin、Adec、Ainc為四個(gè)可調(diào)參數(shù),它們會(huì)影響功率調(diào)節(jié)的精度和范圍。2.本地鄰居平均算法

本地鄰居平均算法(LMN)與本地平均算法(LMA)類似，唯一的區(qū)別是在鄰居數(shù)NodeResp的計(jì)算方法上。在LMN算法中，每個(gè)節(jié)點(diǎn)發(fā)送LifeAckMsg消息時(shí)，將自己的鄰居數(shù)放入消息，發(fā)送LifeMsg消息的節(jié)點(diǎn)在收集完所有的LifeAckMsg消息后，將所有鄰居的鄰居數(shù)求平均值后作為自己的鄰居數(shù)。這兩種算法通過計(jì)算機(jī)仿真后，其結(jié)果為：兩種算法的收斂性和網(wǎng)絡(luò)的連通性是可以保證的，它們通過少量的局部信息達(dá)到了一定程度的優(yōu)化效果。這兩種算法對(duì)無線傳感

器節(jié)點(diǎn)的要求不高，不需要嚴(yán)格的時(shí)鐘同步。15.1.2基于鄰近圖的算法

1.鄰近圖

圖可用G=(V,E)來表示。式中，V表示圖中頂點(diǎn)的集合，E表示圖中邊的集合。E中的元素邊可表示為l=(u,v)，其中u,v∈V。

由圖G=(V,E)導(dǎo)出的鄰近圖G‘=(V,E’)是指，對(duì)于任意

一個(gè)頂點(diǎn)v∈V，給定其鄰居判別條件q，E中滿足q的邊l∈E。典型的鄰近圖模型有RNG(RelativeNeighborGraph)、GG(GabrielGraph)、YG(YaoGraph)以及MST(MinimumSpanningTree)等?；卩徑鼒D的功率控制算法如下：

所有節(jié)點(diǎn)都采用最大功率發(fā)射時(shí)形成的拓?fù)鋱D為G，按照一定的規(guī)則q求出該圖的鄰近圖G′，G′中的每個(gè)節(jié)點(diǎn)以自己所鄰接的最遠(yuǎn)通信節(jié)點(diǎn)來確定發(fā)射功率。

這是一種解決功率分配問題的近似解法。考慮到WSN中兩個(gè)節(jié)點(diǎn)形成的邊是有向的，為了避免形成單向邊，一般在運(yùn)用鄰近圖的算法形成網(wǎng)絡(luò)拓?fù)渲?，還需要對(duì)節(jié)點(diǎn)之間的邊給予增刪，以使最后得到的網(wǎng)絡(luò)拓?fù)涫请p向連通的。2.DRNG和DLSS算法

DRNG(DirectedRelativeNeighborGraph)和DLSS(DirectedLocalSpanningSubgraph)算法是基于鄰近圖的兩種算法。它們最早是針對(duì)節(jié)點(diǎn)發(fā)射功率不一致問題而采用的解決方法。這兩種算法是以經(jīng)典鄰近圖RNG、LMST等理論為基礎(chǔ)，全面考慮網(wǎng)絡(luò)的連通性和雙向連通性而提出的。以下先介紹一些基本定義。（1）有向邊：邊(u,v)和邊(v,u)是不同的，它們的方向不同。

（2）節(jié)點(diǎn)間的距離及通信半徑：用d(u,v)表示節(jié)點(diǎn)

u、v之間的距離，用ru表示u的通信半徑。

（3）可達(dá)鄰居集合及可達(dá)鄰居子圖：可達(dá)鄰居集合

NRu表示節(jié)點(diǎn)u以最大通信半徑可以到達(dá)的節(jié)點(diǎn)的集合。由節(jié)點(diǎn)u和NRu以及這些節(jié)點(diǎn)之間的邊構(gòu)成可達(dá)鄰居子圖GRu。（4）權(quán)重函數(shù)w(u,v)：節(jié)點(diǎn)u和v構(gòu)成的權(quán)重函數(shù)w(u,v)滿足以下關(guān)系:

w(u1,v1)>w(u1,v1)→d(u1,v1)>d(u2,v2)

或者

d(u1,v1)=d(u2,v2)&max{id(u1),id(v1)}>max{id(u2),id(v2)}

或者

d(u1,v1)=d(u2,v2)&max{id(u1),id(v1)}=max{id(u2),id(v2)}

&min{id(u1).id(v1)}>min{id(u2),id(v2)}(15.1.3)在上述兩種算法的執(zhí)行過程中，節(jié)點(diǎn)都需要知道一些必要的信息，因此在拓?fù)湫纬芍耙幸粋€(gè)信息獲得階段。在該階段中，每個(gè)節(jié)點(diǎn)以自己的最大發(fā)射功率廣播HELLO消息，該消息中至少應(yīng)包括自己的ID和自己所在的位置。獲得信息階段完成后，每個(gè)節(jié)點(diǎn)通過接收的HELLO消息確定自己可達(dá)的鄰居集合NRu。在圖15.1.1中，假設(shè)u、v滿足條件d(u,v)≤ru，且不存在另一個(gè)節(jié)點(diǎn)p同時(shí)滿足w(u,p)<w(u,v)，w(p,v)<w(u,v)和d(p,v)≤rp時(shí)，節(jié)點(diǎn)v將被選擇為節(jié)點(diǎn)u的鄰居節(jié)點(diǎn)。因此，DRNG算法為節(jié)點(diǎn)u確定了鄰居集合。

上述算法意味著當(dāng)節(jié)點(diǎn)p與u的通信半徑一定時(shí)，如果v到p和u的距離均小于它們各自的通信半徑，且在三角形△vpu中，uv邊的權(quán)最小，則v一定是u的鄰居。圖15.1.1DRNG算法在DLSS算法中，假設(shè)已知節(jié)點(diǎn)u以及它的可達(dá)鄰居子圖

GRu，將p到所有可達(dá)鄰居節(jié)點(diǎn)的邊以權(quán)重w(u,v)為標(biāo)準(zhǔn)按升

序排列，依次取出這些邊，直到u與所有可達(dá)鄰居節(jié)點(diǎn)直接相連或通過其他節(jié)點(diǎn)相連，最后與u直接相連的節(jié)點(diǎn)構(gòu)成u的鄰居節(jié)點(diǎn)集合。從圖論來看，DLSS算法等價(jià)于在GRu基礎(chǔ)上進(jìn)行本地最小生成樹的計(jì)算。當(dāng)節(jié)點(diǎn)u確定了自己的鄰居集合后，將調(diào)整發(fā)送功率，使其通信半徑達(dá)到最遠(yuǎn)的鄰居節(jié)點(diǎn)。更進(jìn)一步，可通過對(duì)所形成的拓?fù)溥M(jìn)行邊的增刪，使網(wǎng)絡(luò)達(dá)到雙向連通。

DRNG和DLSS算法著重考慮網(wǎng)絡(luò)的連通性，充分利用鄰近圖的理論，考慮到傳感器網(wǎng)絡(luò)的特點(diǎn)，它們是同類算法中的典型算法，以原始網(wǎng)絡(luò)拓?fù)潆p向連通為前提，保證優(yōu)化后的拓?fù)湟彩请p向連通的。15.2層次型拓?fù)浣Y(jié)構(gòu)控制

在WSN中，傳感器節(jié)點(diǎn)的無線通信模塊在空閑狀態(tài)時(shí)的能耗與在收發(fā)狀態(tài)時(shí)相當(dāng)，所以只有使節(jié)點(diǎn)通信模塊休眠才能大幅度地降低無線通信模塊的能量開銷?？紤]依據(jù)一定機(jī)制選擇某些節(jié)點(diǎn)作為骨干節(jié)點(diǎn)，激活通信模塊，并使非骨干節(jié)點(diǎn)的通信模塊休眠。由骨干節(jié)點(diǎn)建立一個(gè)連通網(wǎng)絡(luò)來負(fù)責(zé)數(shù)據(jù)的路由轉(zhuǎn)發(fā)，這樣既能保證原有覆蓋范圍內(nèi)的數(shù)據(jù)通信，也能在很大程度上節(jié)省節(jié)點(diǎn)的能量。在這種拓?fù)涔芾頇C(jī)制下，可將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分為骨干和非骨干節(jié)點(diǎn)兩類。骨干節(jié)點(diǎn)對(duì)周圍的非骨干節(jié)點(diǎn)進(jìn)行管理。這類將整個(gè)網(wǎng)絡(luò)劃分為相連的區(qū)域的算法，一般又稱為分簇算法。骨干節(jié)點(diǎn)是簇頭節(jié)點(diǎn)，非骨干節(jié)點(diǎn)為簇內(nèi)節(jié)點(diǎn)。層次型的拓?fù)浣Y(jié)構(gòu)具有較多優(yōu)點(diǎn)：簇頭節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)融合，減少了數(shù)據(jù)通信量；分簇模式的拓?fù)浣Y(jié)構(gòu)有利于分布式算法的應(yīng)用，適合大規(guī)模部署的網(wǎng)絡(luò)；由于大部分節(jié)點(diǎn)在相當(dāng)長(zhǎng)的時(shí)間內(nèi)使通信模塊休眠，所以可顯著延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生命周期。15.2.1LEACH算法

LEACH(LowEnergyAdaptiveClusteringHierarchy)算法是一種自適應(yīng)分簇拓?fù)淇刂扑惴?，它的?zhí)行過程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。LEACH

算法中的工作循環(huán)如圖15.2.1所示。在簇的建立階段，相鄰節(jié)點(diǎn)動(dòng)態(tài)地形成簇，隨機(jī)產(chǎn)生簇頭。圖15.2.1LEACH算法中的工作循環(huán)1.簇頭選舉方法

LEACH算法選舉簇頭的過程如下：

節(jié)點(diǎn)產(chǎn)生一個(gè)0~1之間的隨機(jī)數(shù)，若這個(gè)隨機(jī)數(shù)小于閾值T(n)，則發(fā)布自己是簇頭的公告消息。在每輪循環(huán)中，如果節(jié)點(diǎn)已經(jīng)當(dāng)選過簇頭，則將T(n)設(shè)置為0，這樣該節(jié)點(diǎn)不會(huì)再

次當(dāng)選為簇頭。對(duì)于未當(dāng)選過簇頭的節(jié)點(diǎn)，將以T(n)的概率當(dāng)選；隨著當(dāng)選過簇頭的節(jié)點(diǎn)的數(shù)量的增多，剩余節(jié)點(diǎn)當(dāng)選簇頭的閾值T(n)也隨之增大，節(jié)點(diǎn)產(chǎn)生小于T(n)的隨機(jī)數(shù)的概率隨之增大，所以節(jié)點(diǎn)當(dāng)選為簇頭的概率也增大，當(dāng)只剩余一個(gè)節(jié)點(diǎn)未當(dāng)選時(shí)，T(n)=1，表示這個(gè)節(jié)點(diǎn)一定當(dāng)選。T(n)可表示為（15.2.1)式中，P是簇頭在所有節(jié)點(diǎn)中占的百分比，r是當(dāng)選輪數(shù)，rmod（1/P）表示這一輪循環(huán)中當(dāng)選過簇頭的節(jié)點(diǎn)個(gè)數(shù)，G是這輪循環(huán)中未當(dāng)選過簇頭的節(jié)點(diǎn)的集合。節(jié)點(diǎn)當(dāng)選簇頭后，發(fā)布通告消息告知其他節(jié)點(diǎn)自己是新簇頭。非簇頭節(jié)點(diǎn)根據(jù)自己與簇頭之間的距離來選擇加入哪個(gè)簇，并告知該簇頭。當(dāng)簇頭接收到所有的加入信息后，就產(chǎn)生一個(gè)TDMA定時(shí)消息，通知該簇內(nèi)所有節(jié)點(diǎn)。為了避免附近簇的信號(hào)干擾，簇頭可以決定本簇中所有節(jié)點(diǎn)所用的CDMA編碼。這個(gè)用于當(dāng)前階段的CDMA編碼連同TDMA定時(shí)一同發(fā)送。當(dāng)簇內(nèi)節(jié)點(diǎn)收到此消息后，就會(huì)在各自的時(shí)隙內(nèi)發(fā)送數(shù)據(jù)。經(jīng)過一段時(shí)間的數(shù)據(jù)傳輸，簇頭收齊簇內(nèi)節(jié)點(diǎn)發(fā)送的數(shù)據(jù)后，運(yùn)行數(shù)據(jù)融合算法來處理數(shù)據(jù)，并將結(jié)果直接發(fā)送給匯聚節(jié)點(diǎn)。如圖15.2.2所示，經(jīng)過一輪選舉過程，可以看到整個(gè)網(wǎng)絡(luò)覆蓋區(qū)域被劃分成5個(gè)簇，圖中黑色節(jié)點(diǎn)代表簇頭?？梢悦黠@地看出經(jīng)LEACH算法選舉出的簇頭的分布并不均勻，這是需要改進(jìn)的一個(gè)方面。圖15.2.2LEACH算法中的簇的劃分2.LEACH改進(jìn)算法

WSN是由大量節(jié)點(diǎn)組成的大規(guī)模傳感器網(wǎng)絡(luò)，離匯聚節(jié)點(diǎn)很遠(yuǎn)的簇頭能量消耗很快，這樣將影響網(wǎng)絡(luò)的覆蓋范圍和生命周期。另外，LEACH提出的簇頭選舉機(jī)制沒有考慮節(jié)

點(diǎn)的具體地理位置，不能保證簇頭均勻地分布在整個(gè)網(wǎng)絡(luò)中。盡管LEACH算法存在一些問題，但是它仍然是一種經(jīng)典分簇算法用來作為分簇算法的基礎(chǔ)。HEED(HybridEnergy-EfficientDistributedClustering)算法針對(duì)LEACH算法簇頭分布不均勻的問題進(jìn)行了改進(jìn)，它以簇內(nèi)平均可達(dá)能量(AverageMinimumReachabilityPower,AMRP)作為衡量簇內(nèi)通信成本的標(biāo)準(zhǔn)。節(jié)點(diǎn)以不同的初始概率發(fā)送競(jìng)爭(zhēng)消息，節(jié)點(diǎn)的初始化概率CHprob為(15.2.2)式中，CHprob和pmin是整個(gè)網(wǎng)絡(luò)統(tǒng)一的參量，它們影響算法

的收斂速度，通常取pmin=10－4,Cprob=5%,

表示節(jié)點(diǎn)剩余能量與初始化能量的百分比。簇頭競(jìng)選成功后，其他節(jié)點(diǎn)根據(jù)在競(jìng)爭(zhēng)階段搜集的信息選擇加入的簇。15.2.2GAF算法

GAF(GeographicalAdaptiveFidelity)算法是用地理位置為依據(jù)來進(jìn)行分簇的算法。它將監(jiān)測(cè)區(qū)域劃分為虛擬單元格，將節(jié)點(diǎn)按照位置信息劃歸相應(yīng)的單元格。在每個(gè)單元格中定

期選舉出一個(gè)簇頭節(jié)點(diǎn)，若簇頭節(jié)點(diǎn)保持激活狀態(tài)，其他節(jié)點(diǎn)則進(jìn)入睡眠狀態(tài)。GAF算法中，節(jié)點(diǎn)的狀態(tài)標(biāo)記為三種狀態(tài)：睡眠、發(fā)現(xiàn)和激活。傳感器網(wǎng)絡(luò)的初始狀態(tài)是：所有的節(jié)點(diǎn)都處于發(fā)現(xiàn)狀態(tài)。處于發(fā)現(xiàn)狀態(tài)下的節(jié)點(diǎn)之間交換Discover消息，獲取

同一個(gè)虛擬單元格內(nèi)其他節(jié)點(diǎn)的信息。Discover消息包括以下幾個(gè)部分的信息：節(jié)點(diǎn)自身的ID、所在虛擬單元格的ID、節(jié)點(diǎn)狀態(tài)、節(jié)點(diǎn)激活時(shí)間的估值等。節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)換如圖15.2.3所示。只要是節(jié)點(diǎn)處于發(fā)現(xiàn)狀態(tài)，都會(huì)對(duì)應(yīng)一個(gè)發(fā)現(xiàn)狀態(tài)計(jì)時(shí)器。如果節(jié)點(diǎn)處于發(fā)現(xiàn)狀態(tài)的時(shí)間超過設(shè)定值Td，該節(jié)點(diǎn)就廣播發(fā)送Discover消息，并轉(zhuǎn)換到激活狀態(tài)。在沒有超過發(fā)現(xiàn)狀態(tài)計(jì)時(shí)器的設(shè)定值Td之前，如果收到了另外的節(jié)點(diǎn)已經(jīng)成為簇頭節(jié)點(diǎn)的消息后，發(fā)現(xiàn)狀態(tài)計(jì)時(shí)器將關(guān)閉，無線通信發(fā)射模塊也關(guān)閉，節(jié)點(diǎn)進(jìn)入

睡眠狀態(tài)。圖15.2.3結(jié)點(diǎn)狀態(tài)轉(zhuǎn)換圖當(dāng)節(jié)點(diǎn)進(jìn)入激活狀態(tài)后，激活狀態(tài)計(jì)時(shí)器啟動(dòng)計(jì)時(shí)，設(shè)置一個(gè)Ta，若激活狀態(tài)的持續(xù)時(shí)間超過Ta，則轉(zhuǎn)入發(fā)現(xiàn)狀態(tài)。當(dāng)節(jié)點(diǎn)處于睡眠狀態(tài)后，啟動(dòng)一個(gè)睡眠狀態(tài)計(jì)時(shí)器，設(shè)置一個(gè)時(shí)間參數(shù)Ts，一旦睡眠狀態(tài)持續(xù)時(shí)間超過Ts，節(jié)點(diǎn)就轉(zhuǎn)入

發(fā)現(xiàn)狀態(tài)。處于激活狀態(tài)的節(jié)點(diǎn)在Ta超時(shí)之前，定時(shí)向外廣播消息通告自己處于活動(dòng)狀態(tài)，以使其他節(jié)點(diǎn)中處于發(fā)現(xiàn)狀態(tài)的節(jié)點(diǎn)不要進(jìn)入激活狀態(tài)。GAF算法在執(zhí)行中分為兩個(gè)階段：虛擬單元格的劃分和虛擬單元格中簇頭的選擇。在虛擬單元格的劃分階段，依據(jù)WSN節(jié)點(diǎn)的位置信息和通信覆蓋范圍，將節(jié)點(diǎn)的部署區(qū)域劃分為若干個(gè)虛擬單元格，劃分中要保證相鄰虛擬單元格中的所有節(jié)點(diǎn)都能夠相互及直接通信。對(duì)于WSN中的一個(gè)成員節(jié)點(diǎn)，已知整個(gè)監(jiān)測(cè)區(qū)域的位置信息和自身的位置信息，就可以根據(jù)這些信息通過計(jì)算來確定自己處于哪一個(gè)虛擬單元格中。假設(shè)所有的節(jié)點(diǎn)通信半徑是R，虛擬單元格是邊長(zhǎng)為r的正方形區(qū)域，要使相鄰的兩個(gè)虛擬單元格內(nèi)任意兩個(gè)節(jié)點(diǎn)之間能夠直接通信，必須滿足以下關(guān)系：(15.2.3)每個(gè)虛擬單元格產(chǎn)生一個(gè)保持激活狀態(tài)的節(jié)點(diǎn)。如圖15.2.4所示，圖中有三個(gè)虛擬單元格，每個(gè)單元格內(nèi)分布有若干個(gè)WSN節(jié)點(diǎn)。在虛擬單元格中的簇頭選擇階段，剛開始的時(shí)候，所有的節(jié)點(diǎn)都處于發(fā)現(xiàn)狀態(tài)，通過彼此發(fā)送包含自身的ID、位置信息的消息，同一虛擬單元格中的所有節(jié)點(diǎn)都彼此知道對(duì)方的信息，然后依照上述算法順序地進(jìn)行激活、睡眠和發(fā)現(xiàn)狀態(tài)運(yùn)行。圖15.2.4虛擬單元格的劃分（黑色節(jié)點(diǎn)表示處于激活態(tài)）在GAF算法的執(zhí)行過程中，簇頭的能量消耗越大，在本輪簇頭競(jìng)爭(zhēng)中繼續(xù)成為簇頭節(jié)點(diǎn)的概率就越低。通過仿真實(shí)驗(yàn)證明：GAF算法可以延長(zhǎng)網(wǎng)絡(luò)的生命周期，節(jié)點(diǎn)密度越大，即虛擬單元格中的平均節(jié)點(diǎn)數(shù)越大，延長(zhǎng)網(wǎng)絡(luò)生命周期的效果越顯著。15.3啟發(fā)機(jī)制

15.3.1STEM算法

STEM(SparseTopologyandEnergyManagement)算法是較早提出的節(jié)點(diǎn)喚醒算法。在STEM算法中，節(jié)點(diǎn)需要采用一種簡(jiǎn)單而迅速的喚醒方式，保證網(wǎng)絡(luò)通信的暢通和較小的時(shí)延。STEM算法有STEM-B(STEM-Beacon)和STEM-T(STEM-Tone)兩種不同的機(jī)制。1.STEM-B算法

當(dāng)一個(gè)節(jié)點(diǎn)要給另一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，它作為主動(dòng)節(jié)點(diǎn)先發(fā)送一串beacon包。目標(biāo)節(jié)點(diǎn)在收到beacon包后，發(fā)送應(yīng)答信號(hào)并自動(dòng)進(jìn)入數(shù)據(jù)接收狀態(tài)。主動(dòng)節(jié)點(diǎn)接收到應(yīng)答信號(hào)后，進(jìn)入數(shù)據(jù)發(fā)送階段。為了避免喚醒信號(hào)和數(shù)據(jù)通信的沖突，STEM-B算法采用了偵聽信道與數(shù)據(jù)傳輸信道兩個(gè)分離信道。如圖15.3.1所示的是節(jié)點(diǎn)A在一段時(shí)間內(nèi)通信能量的消耗過程。節(jié)點(diǎn)A使用f1和f2兩個(gè)信道，f1信道為偵聽信道，f2為數(shù)據(jù)傳輸信道。節(jié)點(diǎn)A在偵聽信道周期性的偵聽，在t1到t5時(shí)間內(nèi)，A分別與B和C通信。在t1時(shí)刻，節(jié)點(diǎn)A需要和相鄰節(jié)點(diǎn)B通信。于是，A節(jié)點(diǎn)首先在f1信道上發(fā)送一串beacon數(shù)據(jù)包，直到t2時(shí)刻收到來自節(jié)點(diǎn)B的響應(yīng)為止；然后，節(jié)點(diǎn)A在t2~t3時(shí)段內(nèi)通過f2信道發(fā)送數(shù)據(jù)給節(jié)點(diǎn)B，當(dāng)完成通信后，暫時(shí)關(guān)閉f2信道。圖15.3.1STEM-B算法示意圖在t4時(shí)刻，節(jié)點(diǎn)A在f1信道上偵聽到節(jié)點(diǎn)C發(fā)送的beacon數(shù)據(jù)包，于是在t4~t5時(shí)段內(nèi)通過f2信道接收節(jié)點(diǎn)C發(fā)送的數(shù)據(jù)，在t5之后，節(jié)點(diǎn)A關(guān)閉f2信道，并繼續(xù)保持在f1信道上的周期性偵聽，這樣便可以節(jié)省大量的能量。2.STEM-T算法

在STEM-T算法中，節(jié)點(diǎn)周期性地進(jìn)行偵聽，探測(cè)相鄰節(jié)點(diǎn)是否有數(shù)據(jù)要發(fā)送。當(dāng)一個(gè)節(jié)點(diǎn)想與某個(gè)相鄰節(jié)點(diǎn)進(jìn)行通信時(shí)，首先發(fā)送一連串的喚醒數(shù)據(jù)包，發(fā)送喚醒數(shù)據(jù)包的時(shí)間長(zhǎng)度必須大于偵聽的時(shí)間間隔，以確保相鄰節(jié)點(diǎn)能夠收到喚醒包,然后節(jié)點(diǎn)直接發(fā)送數(shù)據(jù)包，所有鄰居節(jié)點(diǎn)都能夠接收到喚醒包并進(jìn)入接收狀態(tài)。如果在一定時(shí)間內(nèi)沒有收到發(fā)送給自己的數(shù)據(jù)包，就自動(dòng)進(jìn)入睡眠狀態(tài)。STEM算法使節(jié)點(diǎn)在整個(gè)生命周期中多數(shù)時(shí)間內(nèi)處于睡眠狀態(tài)，適用于類似環(huán)境監(jiān)測(cè)或者突發(fā)事件監(jiān)測(cè)等應(yīng)用，這類應(yīng)用均由事件觸發(fā)，不要求節(jié)點(diǎn)時(shí)刻保持在激活狀態(tài)。目前STEM算法可以與很多分簇類型的拓?fù)渌惴ńY(jié)合使用，如GAF算法等。值得注意的是，在STEM算法中，節(jié)點(diǎn)的睡眠周期、部署密度以及網(wǎng)絡(luò)的傳輸延遲之間有著密切的關(guān)系，針對(duì)具體的應(yīng)用要求應(yīng)進(jìn)行調(diào)整。15.3.2ASCENT算法

ASENT(AdaptiveSelfConfiguringSensorNetworksTopologies)算法屬于節(jié)點(diǎn)喚醒機(jī)制算法，它著重于均衡網(wǎng)絡(luò)中骨干節(jié)點(diǎn)的數(shù)量，以保證數(shù)據(jù)通信路由的暢通。當(dāng)節(jié)

點(diǎn)接收數(shù)據(jù)時(shí)后，發(fā)現(xiàn)丟包嚴(yán)重，就向數(shù)據(jù)源方向的相鄰節(jié)點(diǎn)發(fā)出求助消息，節(jié)點(diǎn)探測(cè)到周圍的通信節(jié)點(diǎn)丟包率很高或者收到相鄰節(jié)點(diǎn)發(fā)出的幫助請(qǐng)求時(shí)將被喚醒，并主動(dòng)成為激活節(jié)點(diǎn)，以幫助相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包。ASCENT算法包括觸發(fā)、建立和穩(wěn)定三個(gè)階段。如圖15.3.2所示，在觸發(fā)階段，匯聚節(jié)點(diǎn)與數(shù)據(jù)源節(jié)點(diǎn)不能正常

通信，此時(shí)，匯聚節(jié)點(diǎn)向它的相鄰節(jié)點(diǎn)發(fā)出求助信息。圖15.3.2ASCENT算法的三個(gè)階段在建立階段，節(jié)點(diǎn)收到相鄰節(jié)點(diǎn)的求助消息，通過一定的算法決定自己是否為激活節(jié)點(diǎn)，如果成為激活節(jié)點(diǎn)，則向相鄰節(jié)點(diǎn)發(fā)送通告消息，同時(shí)這個(gè)消息也是相鄰節(jié)點(diǎn)判斷自己是否成為激活節(jié)點(diǎn)的因素之一。

在穩(wěn)定階段，當(dāng)數(shù)據(jù)源節(jié)點(diǎn)和匯聚節(jié)點(diǎn)間的通信恢復(fù)正常時(shí)，網(wǎng)絡(luò)中激活節(jié)點(diǎn)的個(gè)數(shù)保持穩(wěn)定。穩(wěn)定階段保持一定時(shí)間后，由于個(gè)別節(jié)點(diǎn)的能量耗盡或外界干擾等因素，網(wǎng)絡(luò)中會(huì)出現(xiàn)通信不暢問題，又需要進(jìn)入觸發(fā)階段。在ASCENT算法中，節(jié)點(diǎn)處于四種狀態(tài)：①睡眠狀態(tài)，節(jié)點(diǎn)關(guān)閉通信模塊，能量消耗最??；②偵聽狀態(tài)，節(jié)點(diǎn)只對(duì)信息進(jìn)行偵聽，不進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)；③測(cè)試狀態(tài)，這是一個(gè)暫態(tài),參與數(shù)據(jù)包的轉(zhuǎn)發(fā)，并且進(jìn)行一定的運(yùn)算，判斷自己是否需要變?yōu)榧せ顮顟B(tài)；④激活狀態(tài)，節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)包的轉(zhuǎn)發(fā)，能量消耗最大。這四種狀態(tài)之間的轉(zhuǎn)換關(guān)系如圖15.3.3所示，其中NT表示節(jié)點(diǎn)的鄰居數(shù)上限，LT表示丟包上限，Ts表示睡眠態(tài)定時(shí)器，Tp表示偵聽?wèi)B(tài)定時(shí)器，Tt表示測(cè)試態(tài)定時(shí)器，neighbors代表鄰居數(shù)，loss代表丟包率，help代表求助消息。狀態(tài)間轉(zhuǎn)換關(guān)系如下：

（1）睡眠狀態(tài)與偵聽狀態(tài)：處于睡眠態(tài)的節(jié)點(diǎn)設(shè)置定

時(shí)器Ts，當(dāng)定時(shí)器超時(shí)后，節(jié)點(diǎn)由睡眠狀態(tài)進(jìn)入偵聽狀態(tài)；處于偵聽?wèi)B(tài)的節(jié)點(diǎn)設(shè)置定時(shí)器Tp，當(dāng)定時(shí)器超時(shí)后，節(jié)點(diǎn)由偵聽?wèi)B(tài)進(jìn)入睡眠狀態(tài)。（2）偵聽狀態(tài)與測(cè)試狀態(tài)：處于偵聽狀態(tài)的節(jié)點(diǎn)偵聽信道，如果發(fā)現(xiàn)當(dāng)鄰居數(shù)小于鄰居上限，并且信道的平均丟包率大于丟包上限，則節(jié)點(diǎn)進(jìn)入測(cè)試狀態(tài)；或者當(dāng)平均丟包率小于丟包上限，但接收到來自