無線傳感器網(wǎng)絡(luò)概述,鄭巍,無線傳感器網(wǎng)絡(luò)簡介 無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂?無線傳感器網(wǎng)絡(luò)的路由算法介紹,無線傳感器網(wǎng)絡(luò)的概念 無線傳感器網(wǎng)絡(luò)（ wireless sensor network, WSN）：就是由部署在檢測區(qū)域內(nèi)的大量的廉價微型傳感器節(jié)點組成，通過無線通信方式形成一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作的感知，采集和處理網(wǎng)絡(luò)覆蓋區(qū)域中對象的信息，并發(fā)送給觀察者。 傳統(tǒng)網(wǎng)絡(luò)： 人 人 無線傳感器網(wǎng)絡(luò)：人 自然界,與現(xiàn)有網(wǎng)絡(luò)的區(qū)別 無線自組網(wǎng)(mobile ad-hoc network） 1.幾十到上百個節(jié)點 2.無線通信，各個節(jié)點的關(guān)系是對等的 3.首要目標(biāo)是保證高質(zhì)量的傳輸服務(wù)和高帶寬利用 無線傳感器網(wǎng)絡(luò)(WSN) 1.節(jié)點更為龐大，成千上萬，節(jié)點分布更為密集 2.環(huán)境影響和干擾很大，本身能量不足，因此節(jié)點很容易出現(xiàn)故障，影響網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 3.首要目標(biāo)是能源的高效使用。,傳感器節(jié)點的限制 1.電源能量有限 因此多采用睡眠機制 2.通信能力有限 能耗和通信距離的關(guān)系 因此宜采用多跳而盡量少用單跳 無線通信受干擾很大，甚至可能出現(xiàn)頻繁的通信中斷 因此如何設(shè)計網(wǎng)絡(luò)通信機制以滿足傳感器網(wǎng)絡(luò)的通信需求成為傳感器網(wǎng)絡(luò)的關(guān)鍵問題。 3.計算和存儲能力有限 合理的利用資源成為重要目標(biāo),傳感器網(wǎng)絡(luò)的特點 1.大規(guī)模網(wǎng)絡(luò) 2.自組織網(wǎng)絡(luò) 3.動態(tài)性網(wǎng)絡(luò) 4.可靠的網(wǎng)絡(luò) 傳感器網(wǎng)絡(luò)特別適合部署在惡劣環(huán)境或人類不宜到達(dá)的區(qū)域，要求傳感器網(wǎng)絡(luò)的軟硬件有很強的魯棒性和容錯性。 5.應(yīng)用相關(guān)的網(wǎng)絡(luò) 不同的傳感器網(wǎng)絡(luò)有不同的設(shè)計目標(biāo)，和Internet不一樣他們互相之間沒有統(tǒng)一的通信協(xié)議，開發(fā)時更關(guān)心之間的差異。 6.以數(shù)據(jù)為中心的網(wǎng)絡(luò)。 傳感器網(wǎng)絡(luò)關(guān)心的只是整個網(wǎng)絡(luò)獲得的信息，而并不關(guān)心某一個節(jié)點獲得了什么信息，是以事件為中心的。所以說是以數(shù)據(jù)為中心的網(wǎng)絡(luò)。,軍事應(yīng)用 通過飛機或炮彈直接將傳感器節(jié)點撒播到指定區(qū)域，從而能非常隱蔽和近距離準(zhǔn)確的收集戰(zhàn)場信息。為火控和制導(dǎo)系統(tǒng)提供精確制導(dǎo)，利用生物和化學(xué)傳感器探測生化武器的成分。除了探測之外還可以鑒別身份和追蹤目標(biāo)。,環(huán)境和生態(tài)監(jiān)測 這是中科院對雪豹進(jìn)行監(jiān)測拍攝的照片。,醫(yī)療護(hù)理 包括監(jiān)測人體的各種生理數(shù)據(jù)，跟蹤和監(jiān)控醫(yī)院內(nèi)醫(yī)生和患者的行動，醫(yī)院的藥物管理。值得一提的是應(yīng)用在人工視網(wǎng)膜中，替代視網(wǎng)膜的芯片有100個微型的傳感器組成并置入人眼，可以使得失明者或視力極差者能夠恢復(fù)到一個可以接受的視力水平。,建筑物狀態(tài)監(jiān)測 這是利用傳感器網(wǎng)絡(luò)來監(jiān)控建筑物的安全狀態(tài)。,無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù) 1.網(wǎng)絡(luò)拓?fù)淇刂?2.網(wǎng)絡(luò)協(xié)議 3.網(wǎng)絡(luò)安全 4.時間同步 5.定位技術(shù) 6.數(shù)據(jù)融合 7.數(shù)據(jù)管理 8.無線通信技術(shù) 9.嵌入式操作系統(tǒng) 10.應(yīng)用層技術(shù),無線傳感器網(wǎng)絡(luò)拓?fù)淇刂?網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)控制與優(yōu)化有重要的意義： 1.影響整個網(wǎng)絡(luò)的生存時間 2.減少節(jié)點間通信干擾 也就是節(jié)點傳輸半徑控制，即功率控制 3.為路由協(xié)議提供基礎(chǔ),功率控制 1.基于節(jié)點度的算法 (1)本地平均算法 事先知道每個節(jié)點所需鄰居節(jié)點的上限和下限。調(diào)整節(jié)點的發(fā)射半徑，當(dāng)在發(fā)射半徑內(nèi)的節(jié)點數(shù)在上限和下限之間則停止。 (2)本地鄰居平均算法,2.基于鄰近圖的算法 (1)鄰近圖 將無線傳感器網(wǎng)絡(luò)用圖G=(V,E)表示，再根據(jù)一個給定的鄰居的判別規(guī)則，來確定其鄰居節(jié)點。如RNG等 (2) DRNG算法和DLMST算法,層次型拓?fù)浣Y(jié)構(gòu)控制 也就是將無線傳感器網(wǎng)絡(luò)分割為一些子網(wǎng)絡(luò)，也叫分簇，在這些子網(wǎng)絡(luò)中選取一個簇頭，他的作用是與其他簇頭和sink節(jié)點通信，而子網(wǎng)內(nèi)的其他節(jié)點就只與網(wǎng)內(nèi)節(jié)點通信不與網(wǎng)外節(jié)點通信。 (1)LEACH算法 ：將相鄰的節(jié)點動態(tài)地形成簇，并隨機產(chǎn)生簇頭。 (2)GAF(geographical adaptive fidelity)算法： 以節(jié)點的地理位置為依據(jù)的分簇算法。主要思想是將監(jiān)測區(qū)域分成虛擬單元格。,(3)TopDisc(Topology discovery)算法 源于圖論的思想，利用顏色區(qū)分節(jié)點狀態(tài)，解決骨干網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的形成問題(骨干網(wǎng)絡(luò)節(jié)點也就是簇節(jié)點) 三色算法 四色算法,路由協(xié)議,能量感知路由協(xié)議 基于查詢的路由協(xié)議 地理位置路由協(xié)議 可靠的路由協(xié)議 分簇路由協(xié)議,能量感知路由協(xié)議,能力感知路由協(xié)議的幾種策略,1.最大PA路由：從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取PA之和最大的路徑。如圖中的CBA,但此路徑包含了路徑BA所以排除，選擇路徑FE 2.最小消耗路由：從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取節(jié)點耗能之和最少的路徑。如圖中BA 3.最少跳數(shù)路由：選取從數(shù)據(jù)源到匯聚節(jié)點跳數(shù)最少的路徑。如圖中D 4.最大最小PA節(jié)點路由：每條路徑上有多個節(jié)點，且節(jié)點的可用能量不同，從中選取每條路徑中可用能量最小的節(jié)點來表示這條路徑的可用能量。再在其中選最大的。如圖中的D,基于查詢的路由協(xié)議,1.定向擴散路由 興趣擴散階段 匯聚節(jié)點采用洪泛的方式傳播興趣消息到整個區(qū)域或部分區(qū)域內(nèi)地所有傳感器節(jié)點。 數(shù)據(jù)傳播階段 建立源點和匯聚節(jié)點之間的路徑 路徑加強階段 以某一標(biāo)準(zhǔn)在多個路徑之中選一個路徑，成為加強路徑。,定向擴散路由協(xié)議演示圖,基于查詢的路由協(xié)議,2.謠傳路由 其基本思想是：事件區(qū)域中的傳感器節(jié)點產(chǎn)生代理消息，代理消息沿隨機路徑向外擴散傳播，同時匯聚節(jié)點發(fā)送的查詢消息也沿隨機路徑在網(wǎng)絡(luò)中傳播。當(dāng)代理消息和查詢消息的傳輸路徑交叉在一起時，就會形成一條匯聚節(jié)點到事件區(qū)域的完整路徑,謠傳路由演示圖,地理位置路由,1.GEAR（geographical and energy aware routing)路由 根據(jù)時間區(qū)域的地理位置信息，建立匯聚節(jié)點到時間區(qū)域的優(yōu)化路徑，避免了洪泛傳播方式，從而減少了路由建立的開銷。GEAR路由假設(shè)已知事件區(qū)域的位置信息，每個節(jié)點知道自己的位置信息和剩余能量信息，并通過一個簡單的Hello消息知道所有鄰居的位置信息和剩余能量信息。其主要思想為首先匯聚節(jié)點發(fā)出查詢命令，并根據(jù)事件區(qū)域的地理位置將查詢命令傳送到區(qū)域內(nèi)距匯聚節(jié)點最近的節(jié)點，然后從該節(jié)點將查詢命令傳播到區(qū)域內(nèi)的其他所有節(jié)點，再建立路徑。,地理位置路由,地理位置路由,2.GEM（graph embedding）路由 這是一種適用于數(shù)據(jù)中心存儲方式的地理路由。其基本思想時建立一個虛擬極坐標(biāo)系統(tǒng)，用來表示世紀(jì)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。網(wǎng)絡(luò)中的節(jié)點形成一個以匯聚節(jié)點為根的帶環(huán)樹，每個節(jié)點用到樹根的跳數(shù)距離和角度范圍來表示，節(jié)點間的數(shù)據(jù)路由通過這個帶環(huán)樹實現(xiàn)。,地理位置路由,3.邊界定位的地理路由 利用信標(biāo)節(jié)點（即知道自己位置信息的節(jié)點）來確定全局坐標(biāo)系以及確定其他節(jié)點在坐標(biāo)系中的位置。當(dāng)所有節(jié)點的坐標(biāo)位置信息確定后，協(xié)議使用貪婪算法選擇路由。 有三種方式： 1.邊界節(jié)點均為信標(biāo)節(jié)點 2.使用兩個信標(biāo)節(jié)點 3.使用一個信標(biāo)節(jié)點,可靠路由協(xié)議,某些傳感器網(wǎng)絡(luò)應(yīng)用對于數(shù)據(jù)傳輸?shù)目煽啃蕴岢隽吮容^高的要求，因此傳感器網(wǎng)絡(luò)路由中的一個重要方面師研究可靠路由協(xié)議。傳感器節(jié)點由于有限能量供應(yīng)和工作環(huán)境惡劣經(jīng)常面臨失效問題，這也為研究適合于傳感器網(wǎng)絡(luò)的可靠路由協(xié)議增加了困難。目前，可靠路由協(xié)議主要從兩個方面考慮：一是利用節(jié)點的冗余性提供多條路徑一保證通過性的可靠性；二是建立對傳輸可靠性的估計機制，從而保證每跳傳輸?shù)目煽啃浴?可靠路由協(xié)議,1.基于不相交路徑的多路徑路由機制 在傳感器網(wǎng)絡(luò)中，引入多路徑路由是為了提高數(shù)據(jù)傳輸?shù)目煽啃院蛯崿F(xiàn)網(wǎng)絡(luò)負(fù)載的平衡。本算法的基本思想是：首先建立從數(shù)據(jù)源節(jié)點到匯聚節(jié)點的主路徑，然后在建立多條備用路徑；數(shù)據(jù)通過主路徑進(jìn)行傳輸，同時利用備用路徑低俗傳輸數(shù)據(jù)來維護(hù)路徑的有效性；當(dāng)主路徑失敗時，從備用路徑中選擇次優(yōu)路徑作為新的主路徑。,基于不相交路徑的多路徑路由機制演示圖,可靠路由協(xié)議,2.ReInForM路由 ReInForM( Reliable Information Forwarding Multiple paths) 路由時從數(shù)據(jù)源節(jié)點開始，考慮可靠性需求，信道質(zhì)量以及傳感器節(jié)點到匯聚節(jié)點的跳數(shù)，決定需要的傳輸路徑數(shù)目，以及下一跳節(jié)點數(shù)目和相應(yīng)的節(jié)點。其基本過程是：首先，數(shù)據(jù)源節(jié)點根據(jù)傳輸?shù)目煽啃砸笥嬎阈枰膫鬏斅窂綌?shù)目；然后，在鄰居節(jié)點中選擇若干節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點，并給每個節(jié)點按照一定比例分配路徑數(shù)目；最后，數(shù)據(jù)源節(jié)點將分配的路徑數(shù)作為數(shù)據(jù)報頭中的一個字段發(fā)給鄰居節(jié)點。鄰居節(jié)點在接受到數(shù)據(jù)源節(jié)點的數(shù)據(jù)后，將自己視作數(shù)據(jù)源節(jié)點，重復(fù)上述數(shù)據(jù)源節(jié)點的選路過程。,可靠路由協(xié)議,3.SPEED協(xié)議 在有些傳感器網(wǎng)絡(luò)應(yīng)用中，匯聚節(jié)點需要根據(jù)采集數(shù)據(jù)實時作出反應(yīng)，因此傳感器網(wǎng)絡(luò)記誒但到匯聚節(jié)點的數(shù)據(jù)通道要保持一定的傳輸速率。SPEED協(xié)議是一個實時路由協(xié)議，在一定程度上實現(xiàn)了端到端的傳輸速率保證，網(wǎng)絡(luò)擁塞控制以及負(fù)載平衡機制。為實現(xiàn)上述目標(biāo)，SPEED協(xié)議首先交換節(jié)點的傳輸延遲，一得到網(wǎng)絡(luò)負(fù)載情況；然后節(jié)點利用局部地理信息和傳輸速率信息作出路由決定，同時通過鄰居反饋機制保證網(wǎng)絡(luò)傳輸速率在一個全局定義的傳輸速率閾值之上。,分簇路由協(xié)議,路由協(xié)議自主切換,傳感器網(wǎng)絡(luò)中的路由協(xié)議和具體應(yīng)用緊密相關(guān)，沒有一個能適用于所有應(yīng)用的路由協(xié)議。而傳感器網(wǎng)絡(luò)可能需要在相同監(jiān)測區(qū)域內(nèi)完成不同的任務(wù)，此時如果為每種任務(wù)部署專門的傳感器網(wǎng)絡(luò)將增加傳感器網(wǎng)絡(luò)的成本。未來能夠適用于多種任務(wù)，傳感器網(wǎng)絡(luò)需要根據(jù)應(yīng)用環(huán)境和網(wǎng)絡(luò)條件自主選擇適用的路由協(xié)議，并在各個路由協(xié)議之間自主切換。,