【正文】 早失效，從而使整個(gè)網(wǎng)絡(luò)分割成互不相連的孤立部分．減少了整個(gè)網(wǎng)絡(luò)的生存期。為此，Rahul 等人提出了—種能量多路徑路由機(jī)制。該機(jī)制在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條路徑，根據(jù)路徑上節(jié)點(diǎn)的通信能量消耗以及節(jié)點(diǎn)的剩余能量情況、給每條路徑賦予一定的選擇概率，使得數(shù)據(jù)傳輸均衡消耗整個(gè)網(wǎng)絡(luò)的能量，延長(zhǎng)整個(gè)網(wǎng)絡(luò)的生存期。能量多路徑路由協(xié)議包括路徑建立、數(shù)據(jù)傳播和路由維護(hù)三個(gè)過(guò)程。路30徑建立過(guò)程是該協(xié)議的重點(diǎn)內(nèi)容。每個(gè)節(jié)點(diǎn)需要知道到達(dá)目的節(jié)點(diǎn)的所有下一跳節(jié)點(diǎn)，并計(jì)算選擇每個(gè)下一跳節(jié)點(diǎn)傳輸數(shù)據(jù)的概率。概率的選擇是根據(jù)節(jié)點(diǎn)到目的節(jié)點(diǎn)的通信代價(jià)來(lái)計(jì)算的，在下面的描述中用 表示節(jié)點(diǎn))(iNCosti 到目的節(jié)點(diǎn)的通信代價(jià)。因?yàn)槊總€(gè)節(jié)點(diǎn)到達(dá)目的節(jié)點(diǎn)的路徑很多．所以這個(gè)代價(jià)值是各個(gè)路徑的加權(quán)平均值。由于作者的思想和處理辦法是通過(guò)一本厚達(dá)幾百頁(yè)的書(shū)來(lái)向我們展示的，本人在拜讀了之后，個(gè)人認(rèn)為能量多路徑路由的主要過(guò)程可以簡(jiǎn)潔的描述如下：(1)目的節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播路徑建立消息，啟動(dòng)路徑建立過(guò)程。路徑建立消息中包含一個(gè)代價(jià)域，表示發(fā)出該消息的節(jié)點(diǎn)到目的節(jié)點(diǎn)路徑上的能量信息，初始值設(shè)置為零。(2)當(dāng)節(jié)點(diǎn)收到鄰居節(jié)點(diǎn)發(fā)送的路徑建立消息時(shí)，相對(duì)發(fā)送該消息的鄰居節(jié)點(diǎn)，只有當(dāng)自己距源節(jié)點(diǎn)更近，而且距目的節(jié)點(diǎn)更遠(yuǎn)的情況下，才需要轉(zhuǎn)發(fā)該消息．否則將丟棄該消息。(3)如果節(jié)點(diǎn)決定轉(zhuǎn)發(fā)路徑建立消息，需要計(jì)算新的代價(jià)值來(lái)替換原來(lái)的 代價(jià)值。當(dāng)路徑建立消息從節(jié)點(diǎn) 發(fā)送到節(jié)點(diǎn) 時(shí)，該路徑的通信代價(jià)值為iNj節(jié)點(diǎn) i 的代價(jià)值加上兩個(gè)節(jié)點(diǎn)間的通信能量消耗。即： (31) ),()(, ijiNMetricCostij ??其中， 表示節(jié)點(diǎn) 發(fā)送數(shù)據(jù)經(jīng)由節(jié)點(diǎn) 路徑到達(dá)目的節(jié)點(diǎn)的代價(jià)，ij, j iN表示節(jié)點(diǎn) 到節(jié)點(diǎn) 的通信能量消耗，計(jì)算公式如下：)(ijMetricji31 (32)),(ijNMetric??ijRe?這里 表示節(jié)點(diǎn) 和 直接通信的能量消耗， 表示節(jié)點(diǎn) 的剩余能量，?ijeji ?i iN、 是常量，這個(gè)度量標(biāo)準(zhǔn)綜合考慮了節(jié)點(diǎn)的能量消耗以及節(jié)點(diǎn)的剩余能?量。(4)節(jié)點(diǎn)要放棄代價(jià)太大的路徑，節(jié)點(diǎn) j 將節(jié)點(diǎn) i 加入本地路由表 中jFT的條件是： (33))}C(mini{FTkjij N,kN,j ???其中 為大于 1 的系統(tǒng)參數(shù)。?(5) 節(jié)點(diǎn)為路由表中每個(gè)下一跳節(jié)點(diǎn)計(jì)算選擇概率。節(jié)點(diǎn)選擇概率與能量消耗成反比。節(jié)點(diǎn) 使用如下公式計(jì)算選擇節(jié)點(diǎn) 的概率：j i (34)???jkjijijFTkN,N,C1P(6)節(jié)點(diǎn)根據(jù)路由表中每項(xiàng)的能量代價(jià)和下一跳節(jié)點(diǎn)選擇概率計(jì)算本身到達(dá)目的節(jié)點(diǎn)的代價(jià) 。 定義為經(jīng)由路由表中節(jié)點(diǎn)到達(dá)目的節(jié))(ostj)(stj點(diǎn)代價(jià)的平均值，即： (35))N(Ctj kjjiN,FTk,CP??節(jié)點(diǎn) 將用 值替換消息中原有的代價(jià)值，然后向鄰居節(jié)點(diǎn)廣播該路jNostj由建立消息。在數(shù)據(jù)傳播階段，對(duì)于接收的每個(gè)數(shù)據(jù)分組，節(jié)點(diǎn)根據(jù)概率從多個(gè)下一32跳節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)，并將數(shù)據(jù)分組轉(zhuǎn)發(fā)給該節(jié)點(diǎn)。路由的維護(hù)是通過(guò)周期性地從目的節(jié)點(diǎn)到源節(jié)點(diǎn)實(shí)施洪泛查詢(xún)來(lái)維持所有路徑的活動(dòng)性。Rahul 提出的能量多路徑路由綜合考慮了通信路徑上的消耗能量和剩余能量，節(jié)點(diǎn)根據(jù)概率在路由表中選擇一個(gè)節(jié)點(diǎn)作為路由的下一跳節(jié)點(diǎn)。由于這個(gè)概率是與能量相關(guān)的，可以將通信能耗分散到多條路徑上，從而可實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的能量平穩(wěn)降級(jí)，最大限度地延長(zhǎng)網(wǎng)絡(luò)的生存期。上面只是我個(gè)人從他的書(shū)里整理出來(lái)的一個(gè)簡(jiǎn)潔的可行的能量多路徑路由處理思路，但對(duì)它的一些算法理解還有困難，存在誤解和不足之處，懇請(qǐng)指正。 基于樹(shù)的能量有效路由協(xié)議 利用樹(shù)狀結(jié)構(gòu)來(lái)處理問(wèn)題是一種很多見(jiàn)的思路，針對(duì)無(wú)線傳感器網(wǎng)絡(luò)的能量有效性問(wèn)題，提出了基于樹(shù)的能量有效路由協(xié)議(Treebased Energy Efficient Routing Protocol，TEERP)。在TEERP中，考慮節(jié)點(diǎn)的能量有效性，這主要從兩方面來(lái)實(shí)現(xiàn)：① 選擇最少跳數(shù)的路徑。這對(duì)于功率不可調(diào)整的網(wǎng)絡(luò)，相當(dāng)于選擇了最小能量路徑；②盡量讓剩余能量多的節(jié)點(diǎn)完成分組轉(zhuǎn)發(fā)功能，以提高網(wǎng)絡(luò)的能量均衡性能。首先，定義無(wú)線傳感器網(wǎng)絡(luò)目的節(jié)點(diǎn)只有一個(gè)數(shù)據(jù)匯聚點(diǎn)(Sink)節(jié)點(diǎn)，樹(shù)的建立由Sink 節(jié)點(diǎn)開(kāi)始。 Sink節(jié)點(diǎn)廣播路由請(qǐng)求消息 (RREQ)，RREQ中攜帶廣播ID 、自己距離Sink的跳數(shù)、節(jié)點(diǎn)的能量。節(jié)點(diǎn)在接收到第一個(gè) RREQ時(shí)設(shè)置定時(shí)器，在定時(shí)器超時(shí)時(shí)間內(nèi)，比較新收到的RREQ與當(dāng)前緩存記錄，如果新的RREQ 距離Sink 的跳數(shù)小于當(dāng)前的記錄，則根據(jù)新的RREQ更新緩存中的記錄；如果跳數(shù)相等，則比較發(fā)送RREQ節(jié)點(diǎn)的能量，如果能量大于當(dāng)前緩存記錄的能量，則根據(jù)新的RREQ更新緩存中的記錄，否則丟棄RREQ。33這樣，一直到全網(wǎng)所有的節(jié)點(diǎn)，建立全網(wǎng)的樹(shù)，如圖34所示。Sink 圖 34 樹(shù)結(jié)構(gòu)上述基于樹(shù)的能量路由協(xié)議已經(jīng)很大程度上提高了能量的利用率，同時(shí)延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的生存時(shí)間。但為了保證節(jié)點(diǎn)之間的連通性，節(jié)點(diǎn)之間必須不斷地發(fā)送Hello 消息，這樣做的原因是：盡早發(fā)現(xiàn)失效節(jié)點(diǎn)，及時(shí)恢復(fù)以更好地延長(zhǎng)網(wǎng)絡(luò)的工作時(shí)間。因此，這種處理方法中沒(méi)有引入休眠調(diào)度機(jī)制，而休眠是節(jié)省能量的最有效方式。另外，傳感器網(wǎng)的覆蓋是需要研究的另一個(gè)重要方面，如何在保證覆蓋的前提條件下，最優(yōu)地調(diào)度節(jié)點(diǎn)，引入休眠機(jī)制，并保證網(wǎng)絡(luò)的連通性以建立能量有效的路由是需要不斷研究的一個(gè)重要問(wèn)題。 一種新型集中式能量有效路由協(xié)議本方法是:首先讓基站利用DTRAP(Dynamic Transmission Range Adjustment Protocol)來(lái)估計(jì)節(jié)點(diǎn)的位置。在此對(duì) DTRAP的主要思想作簡(jiǎn)要的介紹。DTRAP 的目的是得到兩個(gè)節(jié)點(diǎn)間的距離，以期用最小的能量進(jìn)行通信，從而節(jié)約能量。每個(gè)節(jié)點(diǎn)維護(hù)兩個(gè)表：MT(Message Table) 和NT(Neighborhood Table)。當(dāng)節(jié)點(diǎn)i收到REQ包，就在 MT中添加一條，當(dāng)i準(zhǔn)備回復(fù)時(shí)，就在NT中把相應(yīng)鄰居節(jié)點(diǎn)的通信狀態(tài)置為REQ，對(duì)方回應(yīng)后，對(duì)方34會(huì)把自己NT 中鄰居節(jié)點(diǎn)的狀態(tài)置為確認(rèn)(ACK)，i 收到回應(yīng)也把狀態(tài)置為(ACK)，這樣雙方就建立了通信。NT中還存有與其余節(jié)點(diǎn)的通信距離。當(dāng)一個(gè)節(jié)點(diǎn) 的鄰居節(jié)點(diǎn)個(gè)數(shù)N 小于下限D(zhuǎn) 時(shí)，它就會(huì)增加它的發(fā)射功率，同時(shí)增時(shí)增大發(fā)射距離Ti，以期得到更多的鄰居。該協(xié)議的工作過(guò)程如下：節(jié)點(diǎn)i廣播一個(gè)Req消息給所有的鄰居，當(dāng)節(jié)點(diǎn)j第一次收到這個(gè)消息(在i的上一輪廣播中， 未收到這條消息，說(shuō)明現(xiàn)在i的發(fā)射范圍剛好能滿足j 的接收信噪比，即這個(gè)發(fā)射能量是i發(fā)向j的最小能量)，而且它的鄰居節(jié)點(diǎn)個(gè)數(shù) 小于jN上限 ，它就把這條消息放在消息表 中，回復(fù) 給i，并把鄰居表HDjMTjACK中i節(jié)點(diǎn)對(duì)應(yīng)的狀態(tài)置為REQ，i收到 后把鄰居表 中j節(jié)點(diǎn)對(duì)應(yīng)jNTj iT的狀態(tài)置為REQ，再回復(fù) 給 j,j收到后把鄰居表 中i節(jié)點(diǎn)對(duì)應(yīng)的狀iACKjN態(tài)置為ACK，至此，i和j點(diǎn)就能互相通信了。因?yàn)橄⒅袔в邪l(fā)射范圍，所以?xún)蓚€(gè)節(jié)點(diǎn)都可以根據(jù)已經(jīng)確定的范圍選擇最小的發(fā)射能量。本能量路由算法是以“輪(round)”為工作時(shí)間單位，每一輪分為兩個(gè)階段：初始化階段和數(shù)據(jù)通信階段。如圖35所示。(1)初始化階段基站根據(jù)DTRAP發(fā)起廣播，確定每個(gè)節(jié)點(diǎn)與基站之間的距離，并確定每個(gè)節(jié)點(diǎn)的方位，從而大致估算出每個(gè)節(jié)點(diǎn)的位置。每個(gè)節(jié)點(diǎn)與基站的距離信息保存在節(jié)點(diǎn)中，當(dāng)在以后節(jié)點(diǎn)作為多跳的簇首直接與基站通信時(shí)，利用這個(gè)距離信息調(diào)整發(fā)射功率，當(dāng)然，基站也利用這個(gè)距離信息選擇不同的發(fā)射功率與不同的節(jié)點(diǎn)通信。然后每個(gè)節(jié)點(diǎn)把自己的能量情況發(fā)給基站，這樣基站就可以根據(jù)能量和位置信息分簇和指定簇首。采用迭代簇分割算法，并采用35簇平衡算法進(jìn)行簇節(jié)點(diǎn)個(gè)數(shù)的平衡，這里不再贅述。最優(yōu)簇?cái)?shù)是總節(jié)點(diǎn)數(shù)目的35% 。在節(jié)點(diǎn)之間相互通信時(shí)采用TDMA的方式，避免沖突。所以初始化的最后一項(xiàng)任務(wù)就是給每個(gè)簇指定節(jié)點(diǎn)與簇首通信的TDMA時(shí)隙。每個(gè)節(jié)點(diǎn)指定不同的時(shí)隙。為了避免簇間射頻干擾，本文采用CDMA編碼方式，每個(gè)簇分配一個(gè)特定的擴(kuò)頻碼。最后基站把簇首信息，TDMA時(shí)隙信息，CDMA編碼信息廣播出去。整個(gè)網(wǎng)絡(luò)就可以開(kāi)始工作了。36NYY N節(jié)點(diǎn)發(fā)生移動(dòng)YN基站根據(jù) DTRAP 確定節(jié)點(diǎn)的位置，基站和節(jié)點(diǎn)保存位置信息節(jié)點(diǎn)將能量信息發(fā)給基站基站利用迭代簇算法分簇，確定簇首，并平衡簇節(jié)點(diǎn)個(gè)數(shù)基站給每簇分配一個(gè) CDMA 擴(kuò)頻碼，給每簇內(nèi)所有節(jié)點(diǎn)分配不同的時(shí)隙基站廣播簇首信息，CDMA 擴(kuò)頻碼信息，時(shí)隙信息，節(jié)點(diǎn)接受并保存節(jié)點(diǎn)與簇首根據(jù) DTRAP 確定彼此距離每個(gè)節(jié)點(diǎn)在自己的時(shí)隙中發(fā)送數(shù)據(jù)和能量信息給簇首簇首收到數(shù)據(jù)簇首對(duì)收到的數(shù)據(jù)融合保存節(jié)點(diǎn)死一輪是否結(jié)束一跳簇首把數(shù)據(jù)和各節(jié)點(diǎn)的能量信息發(fā)給二跳簇首，融合，再發(fā)到多跳簇首，直到基站一輪通信結(jié)束節(jié)點(diǎn)能量是否大于閾值 圖35 路由的建立和工作過(guò)程流程圖37(2)數(shù)據(jù)通信階段數(shù)據(jù)通信階段包括三個(gè)主要的任務(wù)：數(shù)據(jù)匯集(Data Gathering)；數(shù)據(jù)融合(Data Fusion)；路由。每個(gè)節(jié)點(diǎn)先根據(jù)DTRAP協(xié)議確定好自己與簇首之間的距離，然后把自己的數(shù)據(jù)發(fā)給簇首，簇首在接收到所有數(shù)據(jù)后進(jìn)行數(shù)據(jù)融合。融合后的數(shù)據(jù)再發(fā)給二跳簇首，直至N跳簇首直接發(fā)給基站。多跳簇首在每次接收到數(shù)據(jù)后也進(jìn)行數(shù)據(jù)融合。(3)新一輪(round)的初始化每一輪通信結(jié)束后，簇首變?yōu)槠胀ü?jié)點(diǎn)。由于在數(shù)據(jù)通信的過(guò)程中，各節(jié)點(diǎn)都把自己的能量信息發(fā)給了簇首，所以在一輪結(jié)束后，簇首會(huì)把各節(jié)點(diǎn)的能量信息發(fā)給基站。這樣，基站在新一輪進(jìn)行分簇時(shí)不再需要各個(gè)節(jié)點(diǎn)自己把能量發(fā)給基站。如果在某一輪通信中，有新的節(jié)點(diǎn)加入，它與基站通信以登記自己的存在，確定通信距離和位置，在下一輪的簇劃分中就可以被基站考慮進(jìn)去了。如果有節(jié)點(diǎn)發(fā)生移動(dòng)，它與簇首之間的距離就會(huì)發(fā)生變化，在這一輪結(jié)束后，簇首把發(fā)生過(guò)移動(dòng)的節(jié)點(diǎn)的ID發(fā)給基站，基站重新確定它們的位置。如果有節(jié)點(diǎn)斷開(kāi)了連接，簇首也會(huì)把這個(gè)信息告知基站?？傊?，每一輪結(jié)束后基站都能得到網(wǎng)絡(luò)的最新拓?fù)浜湍芰啃畔?，然后根?jù)這個(gè)信息進(jìn)行重新分簇。本協(xié)議在充分考慮了實(shí)際應(yīng)用情況的條件下，有一定突破，不需要節(jié)點(diǎn)知道自己的準(zhǔn)確位置，而是利用DTRAP自行估計(jì)。性能也較前幾種有很大提高。 當(dāng)然，以上的幾個(gè)能量路由協(xié)議都可以通過(guò)NS進(jìn)行仿真來(lái)分析比較其實(shí)際性能，進(jìn)一步驗(yàn)證理論的正確性。我們主要可從系統(tǒng)的總能量消耗、系統(tǒng)存活時(shí)間、成功發(fā)送的數(shù)據(jù)量、存活的節(jié)點(diǎn)數(shù)四個(gè)方面進(jìn)行，下面我參考了別人38的仿真結(jié)果來(lái)表明新型集中式能量路由協(xié)議的優(yōu)勢(shì)和進(jìn)步。 圖 36(a) 平均能量耗散的比較 圖 36(b) 系統(tǒng)存活時(shí)間的比較39 圖 36(c) 基站收到消息數(shù)的比較 圖 36(d) 平均能量耗散（第 50 輪時(shí)）的比較40 圖 36(e) 節(jié)點(diǎn)存活個(gè)數(shù)的比較上述五個(gè)圖的測(cè)試網(wǎng)絡(luò)由500個(gè)節(jié)點(diǎn)組成，隨機(jī)分布在 100 m 100m 的范圍內(nèi)，基站位于75 m(距離最近的節(jié)點(diǎn))遠(yuǎn)處。每個(gè)節(jié)點(diǎn)具有 2J的初始化能量，每輪的數(shù)據(jù)幀數(shù)為40，幀長(zhǎng)度為500 byte，其中幀頭25 byte。試驗(yàn)中，我們隨機(jī)選擇了5O個(gè)不同的網(wǎng)絡(luò)拓?fù)洹?shí)驗(yàn)①把能量耗散作為輪(round )數(shù)的函數(shù)，如圖36(a)所示。本協(xié)議比LEACH—C減少了25% 的能量消耗，只比BCDCP 的能量消耗增加了 4%。實(shí)驗(yàn)②把存活的節(jié)點(diǎn)個(gè)數(shù)作為輪(round) 數(shù)的函數(shù)，如圖36(b)所示。LEACH—C中節(jié)點(diǎn)存活了65輪，BCDCP中節(jié)點(diǎn)存活了 105輪，本協(xié)議中節(jié)點(diǎn)存活了100輪，比BCDCP有少許降低。試驗(yàn)③把基站收到的消息數(shù)作為輪(round)的函數(shù)，如圖36(c)所示。由41于LEACH—C在第65輪后節(jié)點(diǎn)大量死亡，所以收到消息數(shù)遠(yuǎn)遠(yuǎn)小于本協(xié)議。本協(xié)議在100輪后節(jié)點(diǎn)開(kāi)始大量死亡，比BCDCP早5輪，收到消息數(shù)稍稍小于BCDCP。在試驗(yàn)④ 、 ⑤中，我們比較路由協(xié)議在網(wǎng)絡(luò)半徑增加的情況下的性能，見(jiàn)圖36(d) ，圖36(e)。實(shí)驗(yàn)④把能量耗散作為網(wǎng)絡(luò)區(qū)域面積的函數(shù)，圖 36(c)表示在第5O輪時(shí)的能量消耗情況。由于在網(wǎng)絡(luò)半徑增加的情況下，節(jié)點(diǎn)間的距離增加，DTRAP 估計(jì)節(jié)點(diǎn)位置的準(zhǔn)確性增加，從而性能提高?？梢钥闯鲈诿娣e大于0．9m 2時(shí)，本協(xié)議的性能已經(jīng)超過(guò)BCDCP。在充分考慮實(shí)際應(yīng)用情況的條件下，新型集中式能量路由協(xié)議突破了LEACH—C和BCDCP條件的限制(需要節(jié)點(diǎn)知道自己確切位置且是靜止的)，不需要節(jié)點(diǎn)知道自己的準(zhǔn)確位置，而是利用DTRAP自行估計(jì)。而且由于DTRAP可以感知節(jié)點(diǎn)的移動(dòng)，本協(xié)議還可以應(yīng)用在動(dòng)態(tài)網(wǎng)絡(luò)中。42第四章 路由算法的能量?jī)?yōu)化及分析方法