1、文章一Multipath Minimum Energy Routing in Ad Hoc NetworkAd Hoc網(wǎng)絡(luò)如何達(dá)到節(jié)能目的是一個重要問題，本文在網(wǎng)絡(luò)層設(shè)計了一種多信道最小能量路由算法（MultipathMinimum Energy Routing mechanism，簡稱MMER）。將Ad Hoc網(wǎng)絡(luò)看成是一系列的節(jié)點和鏈路，鏈路由一個能量代價函數(shù)相聯(lián)系。我們研究如何利用多信道分流流量來使鏈路的能量代價總合最小。假設(shè)Ad Hoc網(wǎng)絡(luò)有N個節(jié)點和L條鏈路組成。網(wǎng)絡(luò)中有W對源-目標(biāo)節(jié)點對，記為：1,2,W。每一對w=(s,d)，Pw為該對的通道集合，rw為源到目的節(jié)點的數(shù)據(jù)包傳送速

2、率，Xwp為Pw中一條信道p的傳送速率，有鏈路Lij上的傳送速率是所有使用這一信道的源-目的節(jié)點對在上面?zhèn)魉退俾士偤希好織l鏈路都有個能連代價函數(shù)，表示從節(jié)點i到j(luò)的數(shù)據(jù)流量導(dǎo)致的能量損耗，它包括了發(fā)送能量、接受能量和數(shù)據(jù)鏈路層控制能量。總的能量損耗為我們的目標(biāo)是依賴于MAC層協(xié)議，不同的MAC層協(xié)議會由于不同的控制報文和轉(zhuǎn)發(fā)機制導(dǎo)致不同的能量損耗。例如在802.11網(wǎng)絡(luò)中，RTS、CTS、ACK報文會消耗相當(dāng)一部分能量。我們主要研究基于802.11的網(wǎng)絡(luò)之中的能量損耗。下面介紹802.11的能量損耗模型，尤其要提到分布式協(xié)調(diào)函數(shù)（Distributed Coordination Functio

3、n，簡稱DCF）。基于DCF有兩種訪問方法：一種叫基本訪問方法，另一種叫RTS/CTS訪問方法。基本訪問方法只有數(shù)據(jù)幀和ACK幀，會產(chǎn)生“隱藏終端問題”，為此我們用RTS/CTS訪問方法。這種方法在傳輸龐大數(shù)據(jù)幀前優(yōu)先使用小的RTS、CTS幀。RTS/CTS訪問方法首先由發(fā)送方監(jiān)聽信道，如果信道空閑，就發(fā)送RTS報文，否則就觸發(fā)滯后計時器等到信道空閑。接收方在收到RTS后發(fā)送CTS，發(fā)送方在收到CTS后立刻傳輸數(shù)據(jù)幀。如果在一段時間內(nèi)沒有收到CTS，發(fā)送方會重發(fā)RTS。收到數(shù)據(jù)幀后，接收方會回復(fù)ACK幀，如果發(fā)送方?jīng)]有收到ACK幀，會重復(fù)執(zhí)行以上步驟。有兩種原因?qū)е聢笪膩G失。一種是信道錯誤從而

4、影響所有報文，另一種是報文之間發(fā)生碰撞。RTS的順利傳輸能保證后續(xù)的CTS、數(shù)據(jù)幀、ACK都順利傳輸。具體過程如Fig.1所示狀態(tài)S0表示發(fā)送方發(fā)送RTS，Prc表示RTS碰撞的概率，S1表示沒有發(fā)生RTS碰撞，Pre表示導(dǎo)致信道錯誤的RTS錯誤概率，S2表示接收方順利接收到RTS并發(fā)送CTS，Pce表示CTS錯誤概率，S3表示發(fā)送方順利接收CTS并發(fā)送數(shù)據(jù)幀，Pde是數(shù)據(jù)幀錯誤概率，S4表示接收方順利接收數(shù)據(jù)幀并發(fā)送ACK，Pae表示ACK錯誤概率，S5表示發(fā)送方順利接收到ACK。在下面的分析中，我們將RTS、CTS、DATA、ACK包含物理層幀頭的幀大小稱為Nr、Nc、Nd、Na，設(shè)發(fā)送1

5、bit的能量損耗為Et，接收1bit的能量損耗為Er。發(fā)送一個報文的能量和的均值為接收一個報文的能量和的均值為一個報文傳輸?shù)目偟哪芰烤褪窃O(shè)比特錯誤率（BER）為p0，則一個N bit的報文錯誤概率為BER可以通過網(wǎng)絡(luò)的SNR很容易得到，從而很容易得到RTS、CTS、DATA、ACK的錯誤概率。對于Prc，當(dāng)若干沖突通信報文在RTS+DATA時間段到達(dá)節(jié)點j，會發(fā)生碰撞。N個這樣的報文到達(dá)的概率是沒有一個到達(dá)的概率是所以因此從節(jié)點i到節(jié)點j傳輸一個報文的總能量損耗是鏈路能量代價函數(shù)為下面是具體的MMER流量分配算法。是連續(xù)的凸函數(shù)，有可以證明對于所有節(jié)點對w和所有信道當(dāng)且僅當(dāng)相等并且最小時，速率

6、向量x是最佳的。解決問題的一種標(biāo)準(zhǔn)技術(shù)是梯度投射算法。向量x在梯度相反的地方被迭代修正，以適應(yīng)最佳化的問題。迭代修正公式為是一個正向尺寸，向量向可用空間的投射。這種修正直到所有正向傳輸信道流量相等且最小。這種算法的一個特征是流量分配只需由一對接點來決定而不需要考慮其他節(jié)點。其中，為了實現(xiàn)迭代，我們計算考慮Fig.2中的信道p，每個節(jié)點發(fā)送Xwp給下一跳節(jié)點。設(shè)定其中表示除了Xwp外的沖突通信流量，最后兩條鏈路不會影響Xwp的自沖突。因為，有將（23）、（24）代入（21），可以得到下面是實驗部分。固定模式的仿真實驗，如圖Fig.3所示仿真持續(xù)80s，在10s一個速率為160kbps的CBR連接

7、從節(jié)點0到1，均勻的從(0,2,4,1)和(0,3,5,1)通過，在20s時一個80kbps的CBR從節(jié)點6到節(jié)點2，導(dǎo)致0-2和2-6信道的互相干擾，從而在節(jié)點2處有許多碰撞發(fā)生，0-2和2-6信道的能量損耗增加，必須將一些流量轉(zhuǎn)移到鏈路(0,3,5,1)上。Fig.4顯示了在節(jié)點0處的調(diào)整情況。調(diào)整在34s時完成，傳輸變得穩(wěn)定。移動情況下的仿真試驗。假設(shè)存在30個可移動的節(jié)點，分布在1000m*1000m的空間，設(shè)定節(jié)點最快移動速度為2m/s，仿真結(jié)果從30次實驗的均值得到，每次運行超過500s。我們得到Fig.5。文章二AN ENERGY AWARE ROUTING ALGORITHM

8、FOR AD HOC AND SENSORNETWORKS: CONCEPT AND PERFORMANCEAna M. Bernardos, Paula Tarrío and José R. CasarETSI Telecomunicación, Universidad Politécnica de MadridCiudad Universitaria, 28040Madrid, Spain.abernardosgrpss.ssr.upm.es這里討論了一種區(qū)域路由通信方案，用于Ad Hoc傳感器網(wǎng)絡(luò)，可以使得節(jié)點的能量損耗均值最優(yōu)化，該算法基于以下事

9、實：每個節(jié)點有一個兩跳范圍的臨近節(jié)點列表，兩個觸發(fā)式目標(biāo)引導(dǎo)一個簡單地分布式推理機制。由于在網(wǎng)絡(luò)中最耗能量的是節(jié)點傳送數(shù)據(jù)時的能量消耗，因此必須使得節(jié)點發(fā)送或接收的狀態(tài)時間最少。這種算法使用TDMA通信機制。首先設(shè)想一個網(wǎng)絡(luò)，給定它的拓?fù)浣Y(jié)構(gòu)。有以下假設(shè)：每個節(jié)點可以唯一確定，并且可以和臨近節(jié)點建立直接連接的鏈路；在一個給定的節(jié)點對中，每個節(jié)點可以是源節(jié)點、目的節(jié)點或者是中間節(jié)點；沒有中心控制機制或者關(guān)于網(wǎng)絡(luò)結(jié)構(gòu)以及其他節(jié)點位置的先驗信息；存在一個發(fā)現(xiàn)鄰居節(jié)點的階段，在該階段中，鄰居節(jié)點允許一個時隙的通信，該過程是分布式的；在發(fā)現(xiàn)階段之后，每個節(jié)點只能在T個時隙之后才能與鄰居節(jié)點通信，從而保持

10、每個節(jié)點盡可能處于空閑狀態(tài)中，這樣每個節(jié)點只在T時間的一小步份時間內(nèi)進行傳送，如圖Fig1所示的例子。W、Y、Z是節(jié)點X的鄰居節(jié)點；所有傳感器是理想的同步的；有些節(jié)點是可移動的，因此任何路由都可能會改變，這意味著當(dāng)某節(jié)點藥通信時必須進行路由發(fā)現(xiàn)，后面會假設(shè)報文隨著路由發(fā)現(xiàn)過程發(fā)送。我們并不是試圖尋找最佳的路由，而是在可能的路由中尋找次佳的路由，保證該路由在最少的時間里可以進行更多的多跳通信。下面是算法的描述：這個算法考慮了多方面的因素制約，包括鄰居節(jié)點和鄰居的鄰居節(jié)點。當(dāng)一個節(jié)點要發(fā)送數(shù)據(jù)，首先查找自己的聯(lián)系表，如果沒有找到，讓自己的路由器進行路由發(fā)現(xiàn)，算法分為兩個階段。1） 初始化階段。鄰居

11、發(fā)現(xiàn)過程：每個節(jié)點在一個時隙內(nèi)尋找自己的鄰居節(jié)點。也可能交換一些例如電池能量等級之類的信息。例如Fig2所示，A的鄰居節(jié)點是B、C、D。路由表修訂過程：每個節(jié)點廣播自己的一跳聯(lián)系表，該過程結(jié)束時，每個節(jié)點擁有一個兩跳范圍節(jié)點的聯(lián)系表。可以參看Fig3。2） 路由階段。在這個階段算法必須在源節(jié)點確定兩件事：決定發(fā)送數(shù)據(jù)的鄰居節(jié)點路由器群和最佳的兩跳路由到達(dá)可能的節(jié)點。接下去的過程分為三個步驟：a) 除去冗余，對可能的路由器進行評估。首先查詢節(jié)點搜索自己的存儲器檢查是否曾發(fā)送過相同的數(shù)據(jù)，以避免重復(fù)的傳送。如果沒有發(fā)過，他會遵循某些原則向自己的聯(lián)系表中的節(jié)點的某些節(jié)點發(fā)送數(shù)據(jù)。如果目的節(jié)點在表中，丟棄其他的節(jié)點；否則，會丟棄以下可能的節(jié)點：數(shù)據(jù)曾經(jīng)到過的節(jié)點、鄰居節(jié)點、當(dāng)前節(jié)點知道曾經(jīng)查詢過的節(jié)點、當(dāng)前節(jié)點的假設(shè)鏈路上節(jié)點的鄰居節(jié)點。b) 對可能的路徑進行評估。選定以下可能的路徑：到達(dá)可能節(jié)點或目的節(jié)點最小時延的路徑；如果可以從假設(shè)鏈路到達(dá)可能節(jié)點或者目的節(jié)點，當(dāng)前節(jié)點通過比較得出最佳路徑。c) 發(fā)送數(shù)據(jù)給可能節(jié)點或目的節(jié)點。最后是仿真實驗和性