時間：2022-10-21 11:11:48
導語：在路由協議的撰寫旅程中，學習并吸收他人佳作的精髓是一條寶貴的路徑，好期刊匯集了九篇優秀范文，愿這些內容能夠啟發您的創作靈感，引領您探索更多的創作可能。
關鍵詞：物聯網；無線傳感器網絡；路由協議；能源利用率
中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2016）03-00-04
0 引 言
無線傳感器網絡（Wireless Sensor Networks， WSN）作為物聯網的重要組成部分，具有廣闊的應用前景[1]。傳統網絡主要應用于用戶間的數據通信和資源共享， 相比之下，WSN應用范圍更加廣泛，例如環境監測、敵情偵查等。對于WSN路由協議，應用場景的不同會導致它們之間存在某些差異。本文主要從原理、特點以及優缺點三個方面對目前具有代表性的WSN路由協議進行分析，并對其特性進行歸納總結。
根據WSN中傳感器節點的特性以及節點間數據傳輸的特征，可以將WSN路由協議分為以數據為中心的路由、層次路由、地理位置路由以及基于網絡流量和服務質量的路由[2]。
1 以數據為中心的路由
傳統網絡中的路由協議通常是通過地址找到相對應的資源，即以地址為中心；而對于WSN，傳感器節點的部署卻無規律。在這種情況下，節點的具體編號對用戶來說并不重要，用戶只需要得到融合后的、有價值的數據即可，即WSN主要以數據為中心。以數據為中心的路由協議包括Flooding、Gossiping、SPIN、Directed Diffusion和Rumor。
1.1 Flooding路由協議
Flooding協議（洪泛路由協議）是一種傳統的廣播式路由協議[3]。當環境中的某一傳感器節點監測或接收到數據時，無條件的將數據轉發給自己的鄰居節點。Flooding協議原理如圖1所示。
Flooding協議最突出的特點在于節點對數據進行“無條件轉發”，直到數據傳遍整個網絡或是達到規定的跳數上限為止。這一特點使得該協議容易實現，并且能較好地適應網絡拓撲結構的改變。因此，它具有較強的魯棒性，可以應用于軍事領域或者惡劣環境。但該特點也給Flooding協議帶來了一個致命的弱點，即信息爆炸問題。圖1中同一個數據包被3次發送給E節點，這對于E節點來說，極大地浪費了能量。圖2所示為其重疊問題示意圖，其中深色部分為A、B節點所能感知到的區域的重疊部分，如果重疊區域有事件發生，那么該事件信息將被發送給C節點兩次。重疊問題普遍存在而且很難避免，并且會隨著節點分布密集程度的增大而變得愈發嚴重。
目前來講，Flooding協議過于浪費網絡資源和節點能量，因此很少被直接運用，一般將其作為衡量標準去評價其他路由算法。
1.2 Gossiping路由協議
Gossiping協議在Flooding協議的基礎上演變而來。改進之處在于數據包被隨機轉發給某幾個相鄰節點，并非所有相鄰節點，這可以在一定程度上控制信息內爆問題。但是由于節點轉發數據包時隨機選取的相鄰節點可能并不是所有相鄰節點里面距離該節點較近的幾個點，很可能使得數據到達目的節點的時延增大，或是出現跳數已達最大但數據仍未傳送到目的節點所導致的信息傳送失敗問題。
1.3 SPIN路由協議
SPIN（Sensor Protocol for Information via Negotiation）協議基于Flooding協議，改進之處在于節點之間通過協商（Negotiation）的方式緩解數據冗余問題。該協議包含以下三種數據包類型： 消息廣播包（ADV）、 數據請求包（REQ）和數據包（DATA）。
圖3所示為SPIN協議原理，其中S節點有新數據時則向其所有相鄰節點ADV消息，假設A和C有該數據，則它們不回復給S任何消息；假設B沒有該數據，則B需要回復REQ數據包，S收到REQ數據包后將原始數據DATA發送給B節點。B接收到DATA后與自己的數據進行融合并對B的相鄰節點重復該過程。
該路由協議的核心基于元數據（Metadata）的協商（Negotiation）過程。協議中采用“三次握手”機制，即節點只對回復REQ信息的節點發送原始數據，這相比給所有相鄰節點發送原始數據而言，大大減少了冗余數據的傳輸。
該協議仍然有一些不足之處。若某一個節點收到多個相鄰節點的REQ消息，這時需采用“退避算法”，該方法可能會增加時延，也可能會有某些節點對許多消息都“感興趣”，那么它將接收大量數據，這些節點的能量容易耗盡。
1.4 DD路由協議
DD協議（Directed Diffusion定向擴散路由協議）中路徑的建立過程需要經歷以下三個階段：
（1）“興趣擴散”階段，匯聚節點（Sink）采用周期性洪泛方式廣播自己的“興趣”，即自己要接收何種類型的消息；
（2）“梯度建立”階段，興趣擴散路徑即為數據傳輸路徑，只是傳輸方向相反；
（3）“強化路徑”階段，即從“梯度建立”階段所得到的路徑中選取合適路徑進行數據傳輸。
DD協議實現過程如圖4所示。
當加強路徑中的某一段出現故障時，原加強路徑上的節點會啟動新的加強過程，從而建立新的加強路徑。“加強路徑”的修復如圖5所示。
DD協議中路徑加強機制可以顯著提高數據的傳輸速率，但加強路徑上的節點會消耗大量能量，為了確保能量均衡消耗，需要周期性替換加強路徑，這將增加網絡維護的難度。當某一加強路徑出現故障并且暫未更新加強路徑時，多次失敗的發送過程也會增大端到端時延并耗費部分節點的能量[4]。
1.5 Rumor路由協議
對于某些節點較少、需要傳輸的數據量較少或是已知事件發生區域的WSN來說，運用上面提及的幾種路由協議將會帶來一些不必要的開銷。Rumor協議（謠傳路由協議）能夠在一定程度上緩解這種問題，減少網絡中的冗余數據量。該協議中引入（Agent）消息概念，消息由感知到信息的傳感器節點產生[5]。Sink節點產生查詢消息、源節點產生消息，兩者均在網絡中隨機傳播，到兩者傳播路徑出現交點為止，即構成一條完整的數據傳輸路徑。Rumor路由協議原理如圖6所示，實線為消息傳播路徑，虛線為查詢消息傳播路徑，兩條路徑在B點處會合，從而形成一條完整的傳輸線路。
Rumor協議使用單播隨機轉發方式能夠在一定程度上減少網絡的開銷，但由于每個傳感器節點需要維護的列表數目增加了，維護的難度也就增大了。協議中采用的隨機轉發方式無法保證數據傳輸的路徑是最短路徑，因此無法保證數據傳輸的時效性，并且容易出現環路。
2 層次路由
層次路由也叫集群結構路由，它通過引入簇的概念實現網絡內節點的分層管理。簇頭和簇成員各司其職，共同完成數據的傳輸。
2.1 LEACH協議
LEACH協議（Low-energy Adaptive Clustering Hierarchy，低功耗自適應集簇分層型協議）通過特定的簇頭選舉算法確定哪些節點為某一個特定周期內的簇頭，簇頭通過廣播方式告知其它節點自己是簇頭。非簇頭節點選擇加入某個簇之后，會被分配固定的時間片用于發送消息，簇頭負責對后續的消息發送過程進行管理。
該協議通過對傳感器節點的分層管理，優化網絡體系結構，并且利用簇頭節點的信息融合能力減少網絡中的冗余數據。不足之處在于，通過簇頭選舉算法選舉產生的多個簇頭并不一定能夠遍及整個網絡，因此可能導致某些節點無法接收和發送數據。
2.2 TTDD路由協議
TTDD協議（Two-Tier Data Dissemination）相比其他WSN路由協議而言可以很好地處理Sink節點移動問題。傳輸數據前先以源節點為中心建立網格，最接近網格交叉點的節點負責轉發數據。Sink節點在其所處網格區間通過洪泛方式發起查詢請求，距離Sink節點最近的轉發節點作為直接轉發節點并向其上游節點傳送查詢消息，直到查詢消息傳送到源節點為止。查詢消息走過的路徑即為數據傳輸路徑，但兩者傳送方向相反。該協議中定義了初級（PA）和直接（IA），以便Sink節點在等待數據時可以繼續移動。
TTDD適用于節點分布較為密集的網絡，機制的存在使得Sink節點即使是在等待查詢數據時仍然可以繼續移動，這更貼近實際的網絡環境。但網格尺寸的確定對整個算法的效率來講影響較大，因此劃分合適大小的網格對于該算法來講較為重要。
3 地理位置路由
對于WSN網絡來講，短距離、少跳數的傳輸通常情況下能夠縮短傳播時延并節省能量[6]。節點可以利用一些地理位置信息選擇合適的發送路徑，從而提高網絡性能。地理位置路由協議主要包括GPSR協議和GEAR協議。
3.1 GPSR路由協議
GPSR協議（Greedy Perimeter Stateless Routing）要求節點知道自己的地理位置，想要發送數據的節點利用貪婪算法選取轉發節點。
貪婪算法的示意圖如圖7所示，B節點有數據需要發送，B的鄰居節點C比B節點離目的節點A更近，因此B將數據轉發給C。C再根據貪婪算法重復此過程，當數據包傳送到目的節點A時此次傳送過程才結束。由圖7貪婪算法示意圖不難發現， B-C-D-E-A的傳送距離比實線標出的線路更短，但是由于F點相比E點距離D點更近，因此D點選擇把數據發送給F點。貪婪算法所產生的“局部優化”問題，可能會增加數據的傳播時延。
GPSR協議中不需要花費大量精力去維護網絡拓撲結構，它既能支持靜態WSN，又能支持動態WSN。但貪婪算法的使用可能導致協議實現過程中出現路由空洞問題，這時需要采用其他算法以達到整個路由算法收斂的目的，因而會在一定程度上增加傳播時延[7]。
3.2 GEAR協議
GEAR協議（Geographic and Energy Aware Routing）與GPSR協議都需要將目標區域分割成若干個子區域，但GEAR協議中消息是向子區域的中心位置發送。GEAR協議與GPSR協議不同之處在于，節點需要知道自身剩余能量，并根據位置和剩余能量兩個要素按照一定權重計算代價。代價計算見公式（1）所示：
估計：F（Ni，R）=α?D（Ni，R）+（1-α）?LE（Ni）
實際：F（Ni，R）=α?EC（Ni，R）+（1-α）?LE（Ni） （1）
說明：Ni為具有轉發需求節點的鄰居節點，R為目標區域的中心位置。若N不知道Ni的實際代價時使用估計代價。D（Ni， R）代表Ni和R的距離； LE（Ni）表示Ni的剩余能量；EC（Ni，R）表示Ni到R的能量損耗；α代表權重。
GEAR協議利用位置信息避免了查詢消息的內爆問題，同時它在選擇轉發路徑時考慮了節點到達指定區域的代價，這其中涉及消息傳送過程消耗的能量以及節點剩余能量，以此達到均衡消息的目的。但由于使用了貪婪算法，該協議在實現過程中較容易出現路由空洞問題。
4 基于網絡流量和服務質量的路由
對于WSN這個特殊的網絡，傳輸路徑的選擇需要參考網絡流量或是QoS性能指標，這時需要使用基于網絡流量和服務質量的路由協議。例如基于QoS的SAR協議和SPEED協議。
4.1 SAR協議
SAR協議（Sequential Assignment Routing）是首個在WSN中做到保證網絡服務質量的路由協議[8]。在該協議中，Sink節點的所有一跳鄰居節點都以它為根創建生成樹，見圖8第一部分；其他節點重復此過程，多個生成樹的疊加可以得到圖8中第二部分。在路徑匯總圖中，有多條可達Sink節點且具有不同QoS參數的路徑可供選擇。節點發送數據時，按照QoS以及能量剩余情況選擇合適路徑進行傳輸。
SAR協議在保證QoS的基礎上，通過維護傳感器節點和Sink節點間的多條路徑，使得某個節點或某條路徑出現故障時，網絡仍可以正常運行，從而增強網絡的健壯性。不足之處在于節點需存儲大量冗余路由信息，不僅浪費資源還導致路由信息維護的難度增大。
4.2 SPEED協議
SPEED協議是一種QoS協議，它通過設定一個速度門限對下一跳節點進行挑選，實現擁塞控制功能[8]。當節點準備發送數據包時，通過節點自身、鄰居節點和目的節點三者的距離關系劃分出一個轉發結點候選集合，選取轉發速度高于規定的門限值的節點構成轉發節點集合。如果轉發節點集合為空，可以通過調整門限值重新選取。
協議中對鄰居節點的篩選過程，有利于保證傳輸的實時性，并使整個網絡的傳輸負荷處于動態平衡狀態，調節節點的能量消耗[9]。因SPEED協議同時也是與地理位置相關的路由協議并使用了貪婪算法，因此很難避免路由空洞問題[10]。
5 結 語
本文主要針對目前存在的典型WSN路由協議，從原理、特點和優缺點進行分析，以便為日后的WSN路由協議研究提供一些參考。
參考文獻
[1]周雅琴，譚定忠.無線傳感器網絡應用及研究現狀[J]. 傳感器世界， 2009，5（5）：35-40.
[2]畢俊蕾.基于分簇的WSN路由算法的研究與設計[D].開封：河南大學，2008.
[3]黃化吉，馮穗力，秦麗姣，等.NS網絡模擬和協議仿真[M].北京：人民郵電出版社，2010.
[4]彭海英，唐伶俐，唐紅.無線傳感器網絡中DD 路由協議的改進研究[J].計算機工程與應用，2007，43（14）：127-130.
[5]夏靜，莊雷，白雨.無線傳感器網絡謠傳路由研究及改進[J].微計算機信息（測控自動化），2007，23（7-1）：152-153.
[6]顧一中.無線傳感器網絡地理位置路由相關技術研究[D].南京：南京理工大學，2008.
[7]唐國明，謝羿，唐九陽，等.一種基于左、右手法則的GPSR分區邊界轉發路由協議[J].計算機應用研究， 2011，28（3）：1099-1101.
[8]趙強利，蔣艷凰，徐明.無線傳感器網絡路由協議的分析與比較[J].計算機科學， 2009，36（2）：35-41.
關鍵詞： 動態路由；OSPF；自治系統配置命令；鏈路
中圖分類號：TP3 文獻標識碼：A 文章編號：1009-3044（2013）34-7697-02
21世紀是網絡的世界，我們每個人都在不知不覺中融入這個網絡世界。而路由器在網絡中發揮著越來越重要的作用，其主要負責在網絡層間按傳輸數據分組的，并確定網絡上數據傳送的最佳路徑。世界各地的個人和企業單位接入到Internet的自治系統有大有小，小型自治系統因其網絡結構簡單往往采用靜態路由技術即可完成自治系統內的路由尋址，然而大、中型自治系統的網絡拓撲結構往往更加復雜，采用依靠人工分配的靜態路由技術存在很大的困難，因此根據合理的路由尋址算法設計的動態路由技術隨之誕生，而OSPF動態路由技術因其功能強大、可拓展性強和網絡性能優越在動態路由技術中格外優秀，被廣泛應用于各大、中型自治系統中。
1 OSPF的基本概念
開放最短路徑優先協議（Open Shortest Path First）簡稱OSPF，它是路由選擇協議中非常重要的一種協議，這是一種典型的鏈路狀態（Link-state）路由協議，是由Internet工程任務組開發的內部網關（IGP）路由協議，其主要用在一個路由域內。路由域是指一個網絡自治系統（Autonomous System），所謂自治系統是指一組路由器都使用同一種路由協議交換路由信息，網絡中每個路由器都有一個唯一的標識，用于在鏈路狀態數據庫（LSDB）中標識自己。LSDB描述的是整個網絡的拓撲結構，包括網絡內所有的路由器，作為一種鏈路狀態的路由協議，OSPF將鏈路狀態廣播數據包LSA（Link State Advertisement）傳送給在某一區域內的所有路由器，OSPF協議使用最短路徑優先算法，利用LSA通告得來的信息計算每一個目標網絡的最短路徑，以自身為根生成一個樹，包含了到達每個目的網絡的完整路徑。
OSPF的路由標示是一個32位的數字，它在自治系統中被用來唯一識別路由器。默認地使用最高回送地址，若回送地址沒有被配置，則使用物理接口上最高的IP地址作為路由標示。OSPF在相鄰路由器間建立鄰接關系，使它們能利用HELLO包維護關系并交換信息。OSPF使用區域來為自治系統分段，區域0是一個主干區域，每一個OSPF網絡必須具有，其他的區域通過區域0互連到一起。
2 OSPF的特點
OSPF路由協議主要用在大型自治系統內，這是一種鏈路狀態的路由協議，，而距離矢量路由協議RIP（Routing Information Protocol）則主要用在小型自治系統內，兩個路由協議都具有重要的作用，RIP作為靜態路由協議，具有適于小型網絡，管理員可手工配置，精確控制路由選擇，改進網絡性能等優點，但它特別不適合于大型網絡自治系統。而OSPF路由協議與RIP相比，具有如下優點：1、RIP路由協議中用跳（HOP）來表示到達目的網絡所要經過的路由器個數，RIP跳數最高為15，超過15跳的路由被認為不可達，而OSPF不受路由跳數的限制，它只受限于帶寬和網絡延遲，因而OSPF更適合應用于大型網絡中。2、RIP在規劃網絡時是不支持可變長子網掩碼（VLSM），這將導致IP地址分配的低效率，而OSPF路由協議支持VLSM，現在IPV4資源短缺，我們在劃分大型網絡的子網時，往往采用VLSM，這樣劃分子網效率更高，更節約IP資源，所以OSPF更適合大型網絡。3、RIP必須每30秒就要周期性的廣播整個路由表，才能使網絡運行正常，如果RIP用在大型網絡中，它會產生很多廣播信息，而這些廣播會占用較多的網絡帶寬資源，較頻繁的更新有可能導致網絡擁塞，其結果就是RIP用在大型網絡中收斂速度較慢，甚至無法收斂。而OSPF使用組播發送鏈路狀態更新，在鏈路狀態變化時才進行更新，這樣提高了帶寬的利用率， 收斂速度也大幅提高，能夠在最短的時間內將路由變化傳遞到整個自治系統。4、RIP沒有網絡延遲和鏈路開銷的概念，擁有較少跳數的路由總是被選為最佳路由，即使較長的路徑有低的延遲和開銷，并且RIP沒有區域的概念，不能在任意比特位進行路由匯總。而在OSPF路由協議中，往往把一個路由域劃分為很多個區域area，每一個區域都通過OSPF邊界路由器相連，區域間可以通過路由總結（Summary）來減少路由信息，從而減小路由表，提高路由器的運算速度。
OSPF路由協議擁有很多優點，特別適合用于大型網絡，提高網絡的運行速度，但它也有缺點：①使用OSPF路由協議，需要網絡管理員事前先進行區域規劃和路由器各端口IP屬性的設置，所以配置相對于靜態路由RIP來說顯得較為復雜，對網絡管理員的網絡知識水平要求較高。②對路由器的CPU及內存要求較高。
3 OSPF配置命令及配置實例
在思科路由器中配置OSPF路由協議主要使用以下命令：①route ospf 進程號，其中進程號要求范圍為1～65535，進程號只在路由器內部起作用，不同路由器的進程號可以不同。②network address 子網掩碼的反碼 area 區域號，區域號要求在0～4294967295內的十進制數，也可以是帶有IP地址格式的X.X.X.X，當網絡區域號為0時或0.0.0.0時為主干域，不同網絡區域的路由器通過主干域學習路由信息。③show ip route，查看路由信息表，④show ip route ospf 查看OSPF協議路由信息。
某學校采用四臺思科3550路由器把整個學校劃分為3個區域，四臺路由器通過使用OSPF協議實現互通。路由器R1的S0端口IP為192.200.10.5/30，E0端口IP為192.1.0.129/26；路由器R2的S0端口IP為192.200.10.6/30，E0端口IP為192.1.0.65/26；路由器R3的E0端口IP為192.1.0.130/26；路由器R4的E0端口IP為192.1.0.66/26。R1的S0端口和R2的S0端口劃入區域0；R1的E0端口和R3的E0端口劃入區域1；R2的E0端口和R4的E0端口劃入區域2。各路由器配置如下：
R1：
interface Ethernet 0
ip address 192.1.0.129 255.255.255.192
interface serial 0
ip address 192.200.10.5 255.255.255.252
route ospf 500
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.128 0.0.0.63 area 1
R2：
interface Ethernet 0
ip address 192.1.0.65 255.255.255.192
interface serial 0
ip address 192.200.10.6 255.255.255.252
route ospf 600
network 192.200.10.4 0.0.0.3 area 0
network 192.1.0.64 0.0.0.63 area 2
R3：
interface Ethernet 0
ip address 192.1.0.130 255.255.255.192
route ospf 700
network 192.1.0.128 0.0.0.63 area 1
R4：
interface Ethernet 0
ip address 192.1.0.66 255.255.255.192
route ospf 800
network 192.1.0.64 0.0.0.63 area 2
在上述配置中首先對每臺路由器接口進行配置，接口配置完后可以使用router ospf 100命令啟動一個OSPF路由選擇協議進程，期中“100”為進程號，每臺路由器進程號可不同，最后使用network將相應的網段加入OSPF路由進程中，則此接口所對應的網段就加入到OSPF進程中。
綜上所述，OSPF作為一種鏈路狀態的路由協議，具有收斂快，支持變長網絡掩碼，支持CIDR，配置命令簡單易學等。所以在大型或復雜網絡中應用OSPF協議可以極大的提高網絡的運行效率。
參考文獻：
[1] 謝希仁.計算機網絡[M].5版.北京：電子工業出版社，2008
[2] 思科網絡技術學院.思科網絡技術學院教程.
[3] 思科網絡技術學院.思科網絡技術學院教程（第三，四學期）.
關鍵詞：傳感器節點
匯聚節點 能量 簇頭 路由協議
中圖分類號：TP316.4
文獻標識碼：
A
文章編號：1002-2422(2010)03-0002-03
1WSN路由協議介紹
1，1協議分類
劃分路由協議種類有不同的標準。按是否需要外界輔助的地理信息準則，可劃分為基于地理位置信息的協議和非基于地理位置信息的協議；按照網絡中數據發送模式，路由機制可以相應地采用適合周期性地發送數據連續模式、事件驅動模式、請求驅動模式、事件驅動和請求驅動混合模式的協議；按照網絡路由是否動態生成，可劃分為表驅動路由協議和按需路由協議等。
下面介紹各個協議的工作方式。
SPIN采用廣告、請求、數據三種消息類型。節點A在發送DATA數據包之前，會對外采用泛洪方式廣播ADV包，若某個節點B希望接受要傳來的數據，向A回復BEQ數據包。A將向B發送數據包。
GPsR對節點位置進行了統一編址。選擇鄰居節點中離數據包目的節點更近的點作為轉發節點。當數據到達沒有比當前節點更接近目的節點的區域(空洞)，數據無法傳輸。可利用平面圖解決空洞問題。
DIRECTED DIFFUSION路由過程分為請求、梯度建立和路徑加強三階段。請求含有目標區域、數據發送速率等參數。節點接收到請求后，若當前請求緩存中沒有相同的請求記錄，加入新記錄。記錄中包含了相鄰節點數據發送率，稱“梯度”。當請求擴散整個網絡后，選擇“梯度”最大的路徑將反向把數據快速路由。模擬過程如圖1所示。
GEAR發出請求后，數據擴散過程包括目標域傳送和域內傳送。若在目標區域傳輸遇到空洞現象，則根據開銷函數選擇開銷最小的鄰居作為下一跳節點。在域內傳送階段，主要是通過兩種方式(泛洪、區域遞歸)使數據在域內擴散。
LEACH隨機選擇簇頭，普通節點按接收到信號強弱加入簇層。簇層內節點單跳與簇頭通訊，簇頭與匯聚節點通訊。TEEN劃分出多級簇層結構。子簇頭單跳和父簇頭通訊。PEGASIS在網絡中節點中采用算法構造一個數據鏈，各個節點向靠近唯一網絡簇頭的鄰居發送、接收其他節點傳來的數據。
1，2路由協議決策要考慮的準則
設計協議要考慮多種因素，包括數據通訊量、帶寬、網絡負載情況、網絡拓撲結構動態變化、網絡節點增加、數據融合、可靠性等。圖2中，數據從A傳送到節點c。若要求傳送及時，路由可采用A－B－C路徑，減少了傳送中繼節點；若要求以負載平衡達到節能目的，路由應該根據實際負載情況采用負載相對較小的路徑；若要求對不同節點的數據進行融合，可以選擇A－E－F－G－H－C融合更多節點的數據；若要求可靠性，路由可以同時選擇這兩條路徑。若被監測區域內的節點位置發生無規律變化。路由應該具備適應網絡拓撲結構不斷發生變化的能力；若要采集詳盡數據而添加節點，協議還應具備支持更多節點協同工作的能力。
1，3路由協議的性能參數
(1)數據通訊量
把一塊數據路由到觀察者，不同算法會使得該數據的通訊量大小不一致。協議會在不同的程度上產生該數據塊副本。通訊量越大，網絡能耗越大。
(2)延遲
延遲指觀察者對網絡發出請求到接收到數據所歷經的時間。
(3)可擴展性
在某些特殊的實際應用中，被監測區域需要大量節點。這樣就要求路由協議能夠協同大量節點同時工作。
2路由協議的路由通訊量分析
LEACH通過劃分簇層和數據融合技術減少數據通訊量。TEEN采用相似的層次通訊方式，并使用軟門閥值和硬門閥值控制數據傳輸的次數。PEGASIS通過有效的鏈式數據聚合和數據融合技術，減少了的數據收發次數和數據通訊量。圖3是兩者之間以及和FLOODING洪泛協議通訊量比較。
SPIN采用基于數據描述的協商機制進行數據的轉發，從而避免了產生要轉發數據的大量副本。
DIRECTED DIFFUSION采用請求驅動的數據傳送模式和局部的數據聚集、融合，減少網絡數據通訊量。圖4是這兩種協議間以及和FLOODING之間通訊量大小示意表示。
GPSR將數據發送給符合要求的下一跳鄰居。針對某個特定節點A，在網絡拓撲結構不發生變化的情況下，發送數據的路由比較固定。GEAR考慮到匯聚節點的地理位置信息，并將其添加到數據包的地理信息字段，數據傳輸到特定方向。
3路由協議的路由延遲分析
DIRECTED DIFFUSION在數據傳輸階段采用一條“梯度”最大路徑。數據傳輸時間短。LEACH采用劃分簇層方式減少路由中間的傳感器數量，也具備短延遲特性。TEEN協議延遲也比較小，和LEACH同屬于層次式路由協議。GPSR只依賴直接相鄰的節點進行路由。因為使用接近最短歐式距離的路由，因此數據傳輸延遲短。GEAR采用了域內和位置區域地理位置劃分，這樣減少了路由上的跳數，數據能及時到達匯聚節點。
PEGASIS數據延遲和簇頭位置有很大的關系。普通節點距簇頭的地理位置比較遠，會明顯增加數據傳輸的延遲。SPIN采用三種消息模型來信息擴散整個網絡。解決了FLOODING中的“信息內爆”和“信息重疊”問題，但此消息模型導致延遲增加。
圖5給出了層次性協議在相應延遲示意比較。表2作了路由延遲分析的總結。
4路由協議的可擴展性分析
某些協議，因節點大量增加導致網絡數據通訊量過大、路由數據的延遲過長等等而不適用于網絡。
TEEN不斷加入節點形成新簇層。子簇頭數據會向父簇頭傳送，不必像LEACH協議一樣要求普通節點必須具備和匯聚節點直接通訊的能力。
DIRECTED DIFFUSION也具備良好可擴展。“梯度場”的建立確保了數據傳輸的及時性。備用路徑保證了路由的暢通性、可靠性。
GPSR有可達路由只要求保持網絡連通性。GEAR具備好的可擴展性，但需要GPS定位信息的支持。即使增加節點，在地理位置和“兩個階段”的支持下，不會影響協議。
PEGASIS可擴展性差。當大量節點涌入到網絡中，要構造的數據鏈長度會急劇增加。將數據傳送到簇頭，不僅耗費大量能量還增加延時時間。
SPIN可擴展性差。當產生或收到數據的節點的所有相鄰節點都不需要該數據時，將導致數據不能繼續轉發。可能導致相當部分網絡不能接收到該數據。此外，匯聚節點對任何類型的數據都需要時，周圍的節點會能量耗盡。表3給出了協議總結。
【關鍵詞】ZigBee網絡 路由協議 性能
隨著信息技術和移動通信技術的快速發展，讓無線通信技術在各行各業得到了廣泛的應用。組網靈活、使用方便是無線傳感器網絡在實際應用中表現出來的主要特點。ZigBee協議的出現，可以讓傳統無線協議對無線傳感器的適應問題得到有效解決。
1 ZigBee協議的概述
ZigBee技術不僅功耗、成本和速率均比較低，而且便于操作使用。而IEEE 802.15.4標準具有數據傳輸率低、成本少、功耗低等特性，其最終目標就是為家庭或個人范圍內各種設備之間的低速互連提供一個統一的標準。為了保證所制定出的應用層與網絡層的規范能夠匹配IEEE802.15.4標準，ZigBee規范成為ZigBee聯盟中不可缺少的因素。在與之有關的LR-WPAN網絡中，IEEE802.15.4標準編制了以下兩種要素：
（1）系統的媒體接入控制子層；
（2）系統的物理層協議規范。
ZigBee聯盟在這一前提下，所構建的應用層與網絡層協議相關的規范構成了ZigBee協議。簡言之，ZigBee協議是為適應IEEE802.15.4標準而構建的網絡層與應用層協議規范。其中，協議規范可以由以下幾方面因素組成：
（1）應用支持子層；
（2）應用架構；
（3）ZigBee設備對象和廠商所定義的應用對象。
分層結構是這一協議所采用的主要結構。數據實體和管理實體這兩種服務實體在這種結構的每一層都有所涉及。數據傳輸服務是數據實體所承擔的主要形式。管理實體提供的服務中并沒有涉及到數據傳輸服務。服務接入點是為上層提供接口的重要工具。服務原語命令是服務接入點實現自身功能的保障性因素。圖1中的內容就是協議層之間的服務接口。
2 ZigBee網絡拓撲
ZigBee網絡拓撲結構主要由以下幾種結構組成：
（1）星型結構；
（2）樹形結構，
（3）網狀結構。
如圖2所示。
從圖中所示的內容來看，中心協調器和終端節點是星型網絡中的主要器件。這種中心協調器采用的是FFD節點，可以在整個網絡的維護和建立過程中發揮出自身的功能。RFD和FFD是終端節點主要組成部分，一般的情況下，在中心協調器覆蓋范圍以內的區域是這兩大節點的主要分布區域，@種便利性可以讓這些節點與中心協調器進行有效通信的能力得到有效提升。兩個不同設備之間進行通信的過程，也是兩設備將各自所要傳送的數據包向中心協調器進行傳送的過程。可以說，中心協調器發揮的是一種中轉作用。對中心協調器的中轉功能進行發揮的網絡系統又被稱為主從網絡。同步與控制的簡單性特點是星型網的主要特點，這種網絡體系目前僅能在一些擁有較少節點數量的場合中得到應用。網狀網絡是一種由多個FFD組合而成的骨干網絡，各節點之間的通信完全對等，在整個通信范圍內，各節點都可以與其它節點進行通信。如果其中一條路徑發生故障，那么還可以選擇其他一條或若干條路徑。然而，正是因為兩個節點之間的路徑較多，所以顯得冗余非常高。一般情況下，路由功能的實現，是網狀網絡構建過程中所遵循的一個重要原則，此種有助于網絡層找到最佳的信息傳遞路徑，事實上屬于一種多信道通信。樹狀拓撲結構主要由以下三個部分組成：
（1）中心協調器；
（2）路由節點；
（3）終端節點。
在實際應用過程中，連接路由節點和終端節點的功能是該結構的主要功能。在路由節點成為中心協調器子節點的情況下，這一結構會借助一系列的終端節點與路由節點相連。終端節點不能涵蓋自身的子節點，但路由節點與中心協調器可以涵蓋自身的子節點。在樹狀拓撲結構中，各個節點只具備一種功能，就是實現子節點與父節點之間的通訊。在這樣的情況下，如果要將一個節點中的數據傳輸到另一個節點，這種樹狀結構會讓信息順著樹的路徑進行輸送。網絡覆蓋范圍大是這一網絡結構的主要特點。由于信息路由通道在該系統中存在單一性，隨著網絡覆蓋范圍增加，信息的傳輸時延也會有所增加，并且時間同步也會越來越繁瑣。
3 ZigBee網絡路由協議的性能
3.1 路由協議的基本思想
低成本、低功效和高可靠性是ZigBee網絡路由協議的主要設計目標。樹路由和按需距離矢量路由相結合的路由算法的構建，為上述目標的實現提供了幫助。在對ZigBee網絡中使用的AODVjr與自組網中所應用的AODV協議進行對比分析以后，我們可以發現，AODVjr可以被看作是AODV的一種簡化版本。在ZigBee網絡中，節點之間存在一種類似于父子關系的從屬關系。在依托路由算法進行路徑選擇的過程中，節點會在接收到分組信息以后對信息進行判斷，如果發現其中的內容與自己無關，會把該信息傳送給其父節點或其他子節點。為了對路由效率進行進一步的提升，AODVjr也會為一些具備路由功能的節點搜尋路由，也就是說，在傳輸信息的過程中，在不遵從父子從屬關系的情況下，通過直接傳遞的方式將信息傳送到其通信范圍內的其他具備同樣功能的節點的措施，是一些具備路由功能的節點進行信息傳輸的主要措施，而針對那些不具備路由功能的節點，則只能借助樹路由來對控制分組與數據分組進行傳輸。
3.2 ZigBee的路由過程
在zigBee網絡路由協議中，節點既具備路由表能力，又具有路由發現表能力，表1所示的內容為路由發現表的格式
從階段網絡層的數據幀獲取情況來看，在網絡層從更高層接受數據幀的情況下，廣播發送是節點進行數據傳送的主要方式。在接收節點為路由器或協調器的情況下，如果數據幀的目的節點是該節點的子節點，這一數據幀會被直接傳送到目的地址之中。如果網絡層接收的是來自低層的數據幀，數據幀的目的節點成為了系統對數據幀的發送方式進行確定的主要方式。在對一些具備路由功能的節點進行確定的過程中，系統會對目的地址在路由表中的地址加以核查，在節點目的地址的路由條目不確定的情況下，首先針對數據幀頭系統需要對幀控制域中的路由發現標志進行核查，如果路由發現標志值為0，或者此節點缺少路由功能，則可采取樹路由的方式傳輸數據幀；倘若該發現路由標志值為1，則該節點可根據路由發現的發起方式及條件來發起路由發現。針對目的地址的路由條目明確的節點，必須借助已有路由表條目進行路由傳輸。
如果網絡層接收到來源于低層的數據幀，則是否需要轉發該數據幀主要取決于該數據幀的目的節點是否是本地節點。在終端設備成為目的節點以后，設備在應用過程中出現的休眠問題會給信息的傳輸效率帶來不利的影響。間接傳遞方式的應用，就成為了對休眠效應的不利影響進行規避的有效方式。數據幀頭中的Discover Route字段決定著如何選取ZigBee網絡層的具體路由方法。
3.3 路由選擇
在節點的職能定義和工作狀態存在一定差異性的情況下，路由策略選擇就成為了zigBee網絡路由協議性能的一種表現。路由選擇策略主要由以下幾種策略組成。
（1）抑制路由發現，這一性能是建立在已經存在的路由表基礎之上的；
（2）使能路由的發現，即路由表中存在該路由地址，則按路由表執行，否則路由器進行初始化路由發現處理。如果路由表中的節點不具備初始路由的發現能力，系統會對樹形路由進行運用；
（3）強制路由發現功能，在這一功能的作用下，不論相應的路由表是否存在，節點都會在對AODVjr路由算法進行強制應用的情況下進行初始化路由發現。可以說，數據驅動思想是與數據的傳輸種類和傳輸需要之間存在著一定的聯系；
（4）樹路由發現功能，即只應用樹狀路由方式發起路由發現，且不遵從現有的路由表。所謂的數據驅動思想就是指針對不同類型及需求的數據傳遞，可以采取多種路由方式。如果需要傳遞大量的數據，那么可以對使能路由發現功能加以選取，發現并構建最佳路徑。如果需要傳遞控制數據或突發型數據，則可以對樹路由發現功能與抑制路由發現功能加以選取，這兩種路由發現功能能夠實現快速響應，而且不需要構建路由表。如果需要更新路由表內的信息，那么可以對強制路由發現功能加以選取，以此來對路由表進行更新，對路由表加以重新構建。
4 結論
ZigBee結束對進場通信市場所表現出的低成本、低速率和低功耗的問題進行了有效解決。這一技術的應用，對低端無線傳感器和控制網絡設計的優化有著一定的促進作用。ZigBee通過結合ZigBee規范與IEEE802.15.4標準，可以有效的實現數以萬計的微波傳感器之間進行協同通信。在當下ZigBee快速發展、不斷優化的新時代下，ZigBee技術勢必會為無線接入技術領域注入全新的活力，必將使人們的生活模式及工作模式發生翻天覆地的改變，促進社會以及經濟建設更快、更好地發展。
參考文獻
[1]張習勝.ZigBee無線網絡協議的路由算法分析與實現[J].電子元器件應用，2010（07）：53-56.
[2]關學忠，張新城，孟伸伸.基于ZigBee技術的無線傳感器網絡路由算法的性能分析[J].自動化技術與應用，2017（03）：36-39.
作者簡介
李玉林（1981-），男，湖南省永興縣人。碩士學位。現為湖南機電職業技術學院講師。主要研究方向為計算機網絡管理。
Abstract: Ad hoc network is a MANET, mobile nodes must have the routing function, so the routing protocol selection is critical. This paper introduces the DSDV, DSR and AODV routing protocols. We obtain the throughput, packet loss and delay performance analysis chart by NS simulation. It gives the advantages and disadvantages of these types of routing protocols and the future direction of development of routing protocols.
關鍵詞： Ad hoc網絡；NS模擬；DSDV；DSR；AODV
Key words: Ad hoc network；NS simulation；DSDV；DSR；AODV
中圖分類號：TP393文獻標識碼：A文章編號：1006-4311（2011）17-0146-02
0引言
移動Ad hoc網絡是一種自組網，不需要固定的基礎設施，能夠快速地自動組網。與有中心網絡相比，Ad hoc網絡靈活、健壯、投資少，特別適合于作戰指揮、搶險救災以及應付突發事件和執行臨時任務的場合。在Ad hoc網絡中，因為自組網中節點的傳輸范圍有限，源端向目的端發送數據時，通常需要其它節點的輔助，所以路由協議是自組網中不可缺少的一部分。路由協議的功能是根據路由策略和路由表進行數據分組轉發和路由維護。Ad hoc網絡在通信中，節點是移動的，而且傳輸能力有限，大多采用多跳轉播通信，而多跳路由帶寬受限，設備功率低，網絡的拓撲結構動態變化，易受攻擊等挑戰。
1Ad hoc路由協議及典型的路由算法
目前，Ad hoc網絡的路由協議大致可以分為主動路由協議、按需路由協議和混合路由協議。主動路由協議又稱為表驅動路由協議，在這種路由協議中，即使沒有傳輸需求，兩節點之間的路由也預先建立。這種方法不適合大規模網絡，許多不用的路由仍需維持，而且還有周期性的路由信息更新。而按需路由協議，是一種當需要發送數據時才建立路由。不需要時，釋放路由。然而，當一個鏈路失效或節點斷開，要重建路由而引起延時和開銷更嚴重。下面介紹幾種典型的路由算法。
1.1 主動路由協議――DSDV目的節點序列距離矢量路由協議（DSDV，Destination-Sequenced Distance-Vector Routing）是基于Bellman-Ford算法，在DSDV中，每個移動節點都需要維護一個路由表。路由表包括目的節點、跳數、下一跳節點和目的地序號，其中目的地序號由目的節點分配，主要用于判別路由是否過時，并可防止路由環路的產生。每個節點周期性必須與鄰節點交換路由信息，當然也可以根據路由表的改變來觸發路由更新。對路由表進行更新主要有以下兩種方式：①全部更新：拓撲更新消息中將涵蓋整個路由表。此種方式大多運用在有相對快的網絡變化的狀況下；②部分更新：在更新消息中只是涵蓋了變化的路由部分。這種方式大多應用在有相對較慢的網絡變化的狀況。在DSDV中只要從源到目的的路由存在，這種路由協議的所需時延較小，缺點是路由協議的開銷較大，因為動態的拓撲結構變化，使得路由信息更新復雜，不適合大規模的網絡。
1.2 按需路由協議――DSR動態源路由協議（DSR，Dynamic Source Routing Protocol）是一種基于源路由的按需路由協議，它使用源路由算法而不是逐跳路由的方法。DSR主要包括兩個過程：路由發現和路由維護。當節點S向節點D發送數據時，它首先檢查緩存是否存在未過期的到目的節點的路由，如果存在，則直接使用可用的路由，否則啟動路由發現過程。路由發現過程是：源端節點廣播路由請求給其鄰居節點，鄰居節點收到路由請求分組后，輪流把自己的地址添加道路由請求分組，并轉發補充了的路由請求分組，這個過程一直持續到有一個路由請求分組到達目的端節點。若發現自己的地址在記錄中，就停止廣播，每個節點都有一個路由緩存，存貯最近轉發來的路由請求，同時查詢接收的是否為統一個請求，這樣可以保證每個節點之轉發一次。當路由請求到達目的節點時，節點要返回一個路由應答分組，通知節點已收到該路由請求。目的節點通過反向路由來發送路有應答消息。那么源端與目的端有多條路由。DSR把這些路由緩存在路由緩存器中備用。
這樣做DSR不需要周期性的發送路由發現報文，但發送每個報文都要攜帶完整的路由消息。降低帶寬的利用率。DSR的優點：①節點僅需要維護與之通信的節點的路由，減少了協議開銷；②使用路由緩存技術減少了路由發現的耗費；③一次路由發現過程可能會產生多條到目的點的路由。DSR的缺點：①每個數據報文的頭部都需要攜帶路由信息，數據包的額外開銷較大；②路由請求消息采用洪泛方式，相鄰節點路由請求消息可能發生傳播沖突并可能會產生重復廣播；③由于緩存，過期路由會影響路由選擇的準確性。
1.3 按需路由協議――AODV Ad hoc按需距離矢量路由協議（AODV, Ad hoc on Demand Distance Vector）是DSDV算法的改進，但它與DSDV的區別在于它是按需路由協議。為了找到通往目的節點的路由，源端將廣播一個路由請求分組，鄰居節點依次向周圍節點廣播此分組直到該分組被送到一個知道目的節點路由信息中間節點或目的節點本身。一個節點將丟棄重復收到的請求分組，路由請求分組中的序列號用來防止路由環路，并能判斷中間節點是否響應了相應的路由請求。當節點轉發路由請求分組時，它會將其上一個節點的標志ID記入路由表，從而能夠構建一條從目的節點到源節點的反向路由。當源端移動時，它會重新發起路由發現算法；如果中間節點移動，那么與其相鄰的節點會發現鏈路失效并向其上一個節點發送鏈路失效消息并一直傳到源節點，而后源節點根據情況重新發起路由發現過程。
2Ad hoc網絡中的路由協議的NS模擬
本模擬在windows XP環境下，采用Cygwin和ns-allinone-2.28搭建模擬平臺。在此環境下，對Ad hoc網絡中的路由協議DSDV、DSR和AODV進行模擬分析，并對其進行性能比較，并以圖形形式顯示。
2.1 搭建實驗網絡拓撲模擬工具采用NS2網絡模擬器，無線模擬開始時，需要定義每個網絡功能組件的類型，包括天線的類型、電磁波的傳輸模式和移動節點使用的Ad hoc路由選擇協議等。網絡初始拓撲結構見圖1，該模型由6個無線移動節點構成，3個源節點（節點0，1和2）和3個目的節點（節點3，4和5）。節點0開始向節點3發送CBR數據包，使用的是DSDV路由協議；節點1開始向節點4發送CBR數據包，使用的是DSR路由協議；節點2開始向節點5發送CBR數據包，使用的是AODV路由協議；傳輸的分組大小均是512比特，傳輸速率是600 Kbps，開始傳輸時間為1.4s，傳輸距離是195米，模擬的時間是80s。
2.2 性能分析在相同的網絡環境下，分別用3種Ad hoc路由協議進行模擬，而后對模擬產生的TR數據進行分析，用繪圖工具Xgraph繪制，由于本模擬是從1.4s開始模擬，但是繪制的吞吐量、丟包和延時圖卻是從0s開始。吞吐量實時變化圖如圖2，丟包實時變化圖如圖3，端到端的延時的實時變化圖如圖4所示，黑色是DSR，深灰色是DSDV，淺灰色是AODV。下面進行具體的分析比較3種路由協議下CBR應用的性能。
2.2.1 吞吐量吞吐量能反映網絡占用帶寬的性能。從圖2可知，從1.4s到20s時，AODV的吞吐量最大，DSDV和DSR差不多；20s后，3種路由協議的吞吐量都比剛開始模擬要小一些，呈現不斷降低的趨勢。吞吐量是AODV最好，次之是DSR，DSDV最差。
2.2.2 丟包率丟包率反映的是丟包數目與總發包數目的比值。從圖3可知，從1.4s到20s時，3種路由協議都沒有丟包，但20s后，丟包率都增加，呈現不斷提高的趨勢。其中，丟包最大的是DSDV，然后是DSR，最小的是AODV。
2.2.3 端到端的延時端到端的延時是反映包發送過程中，目的端與源端的時間差。從圖4可知，從1.4s到20s時，3種路由協議端到端的延時一致，呈現不斷提高的趨勢。但20s后，端到端的延時都增加，其中，延時最大的是DSR，然后是AODV，最小的是DSDV。
綜上所述，都是因為DSDV是主動路由協議，而DSR、AODV是需路由協議，DSDV為目的節點只維護一個路由，當此路由失效時將沒有可以替換的路由。如果網絡拓撲結構動態變化的太快，路由信息更新復雜，網絡開銷大，端到端的延時小一些。而按需路由是不用周期的廣播信息，節省網絡開銷，但每次要進行路由發現，端到端的時延大。
3結論
本文詳細分析了當前Ad hoc網絡采用的3種路由協議，并且通過NS網絡模擬器對其中的3種路由算法進行了模擬分析和性能比較。結果表明不同的路由協議都有各自的應用場合和優缺點，目前最為流行的就是將主動和按需路由協議優點的混合式路由協議是一種較好的折衷方案。應用在局部范圍內使用主動路由協議，維護準確的路由信息，并可縮小路由控制消息傳播的范圍，當目標節點較遠時，通過查找發現路由，這樣既可以減少路由協議的開銷，時延特性也得到了改善。這種路由算法吸取了2種路由算法的優點，具有較高的效率和較強的適應性。由于Ad hoc自身復雜多變的動態特性，路由協議的設計目前仍是一個人們關注的熱點問題。
參考文獻：
[1]李平均,谷寧靜.一種基于AODV協議的改進協議Q-AODV[J].微電子學與計算機，2006,23(5）:89-92.
[2]王金龍,王呈貴,吳啟暉等.Ad hoc移動無線網絡[M].北京:國防工業出版社，2004.
[3]葛文英,偉.Ad hoc網絡的按需路由研究[J].軟件技術.2006,(8):41-42.
[4]于斌,孫斌,溫暖等.NS-2與網絡模擬[M].北京：人民郵電出版社，2007.
關鍵詞：無線傳感網絡；RPL；IP；能量路由
中圖分類號：TP393 文獻標志碼：A 文章編號：2095-1302（2014）01-0057-03
0 引 言
低功耗有損網絡路由協議 （RPL）是IETF的ROLL（Routing Over Low power and Lossy networks ）工作組，專門針對低功耗有損網絡LLN（Low power and Lossy network）新提出來的路由協議[1]。低功耗有損網絡是由功率、存儲空間、處理能力等資源受限的嵌入式設備所組成的網絡。它們可以通過多種鏈路連接，比如IEEE 802.15.4、藍牙、低功率Wi-Fi，甚至低功耗電力線通信（PLC）等等。ROLL將LLN網絡的應用主要劃分為四個領域[2]：城市網絡（包括智能電網應用）、建筑自動化、工業自動化以及家庭自動化，并且分別制定了針對四個應用領域的路由需求[3-6]。由于LLN的獨特性，傳統的IP路由協議，比如OSPF、IS-IS、AODV、OLSR，無法滿足其獨特的路由需求，因此ROLL工作組制定了RPL協議，其協議標準RFC6550[1]于2012年3月。
本論文首先介紹了RPL的應用場景及基本原理，并在路徑選擇策略中加入了對節點剩余能量的考慮；最后通過仿真驗證了改進后的路由協議的性能。
1 RPL協議工作原理
RPL是一個矢量路由協議，通過構建有向非循環圖（DAG）來形成拓撲結構，加入DAG中的節點自動形成一條指向根節點的路徑。RPL主要為數據匯聚型的場景設計，即數據流量由葉節點指向根節點。當然RPL也擴展支持多點對點（MP2P）和點對點（P2P）的應用場景。
圖1所示為典型的DAG結構。其中的每一個節點至少有一條指向根節點的路徑。
1.1 DODAG的形成
DODAG（Destination Oriented Directed Acyclic Graph）是面向目的地的有向非循環圖的簡稱，可以視為物理網絡上的邏輯路由拓撲。
RPL中定義了由多種ICMPv6消息來控制拓撲的形成。DIO消息用于通告有關DODAG的參數，例如DODAGID、目標函數（OF）、DODAG版本號等[1]。其中OF規定了拓撲建立及最優父節點的選擇方式，規定了節點級別的計算方法，是路徑選擇的首要參考標準。級別決定了節點在DODAG中的相對位置，主要用于避免回路。DAO消息是用來建立從根節點到葉節點的“向下”的路徑。根據節點的存儲能力，RPL協議中將節點類型定義為可存儲型和非存儲型，兩者的區別在于是否存儲有路由表信息。在圖1中，當D節點要和E節點通信時，如果B節點和C節點是非存儲型，那么必須先追溯到根節點A，查找路由，即路徑為D—C—B—A—B—C—E。若C為可存儲型節點，則只需追溯到共同的祖先節點即可找到路由，即路徑為D—C—E。DIS消息用于向鄰居節點請求DODAG信息。當一個孤立的節點沒有收到任何DIO消息的時候，可通過DIS向周圍節點請求DODAG信息。收到DIS消息的節點會反饋DIO消息給DIS源節點。
如圖1所示，首先A節點通過DIO消息廣播自己創建的DODAG信息，收到DIO消息的節點根據OF來決定是否應該加入該DODAG；加入之后然后再向自己周圍的節點繼續廣播DIO消息；這樣一層一層地建立拓撲結構。當節點加入DODAG之后，就自動創建一條“向上”匯聚到根節點的路徑。“向下”的路徑則由DAO消息完成。
1.2 定時器管理
RPL中使用細流算法[7]來控制DIO消息的發送。細流算法是一個適應性的機制，用來限制控制協議的開銷。與傳統IP網絡不同，LLN網絡有著非常有限的資源，必須盡可能的減少控制協議消息所占的比例，但同時又必須要維護好網絡結構。當網絡改變時，節點會以較高的頻率發送控制包；當網絡趨于穩定時，則控制流的速率減少。算法中定義了控制消息發送間隔參數I，當網絡很穩定時，則I成倍的增加；而網絡有動蕩時，則發送間隔迅速降為最小值，高頻率的發送控制消息以修復網絡。
本文借助Contiki系統中的Cooja模擬器，對RPL協議進行了仿真。圖2所示為節點布局圖，并在圖3中以節點5為例展示了DIO消息的發送控制過程。從圖3中可以看到，當網絡剛形成逐步趨于穩定的時候，DIO消息發送間隔成倍增加；圖3中23：00和01：20附近陡峭的轉折點表明此時監測到節點5和網絡存在不一致性，迅速將控制消息發送間隔調至最小值以迅速修復網絡。
1.3 環路避免機制
RPL中規定，在沿著葉節點到根節點的路徑上，節點級別必須是遞減的[1]，即父節點的級別必須小于子節點的級別。當節點在網絡中位置發生改變時，必須根據父節點重新計算自己的級別。假設節點N的最優父節點為P，P的級別為R（P），那么N的級別R（N）計算公式為：
R（N）=R（P）+ rank_increase
rank_increase為子節點和父節點級別的差值，其算法在OF中有定義。
節點的級別在環路避免中有著重要的意義。RPL協議也通過在包頭上設定標志位來附帶路由控制數據，以避免數據包被循環轉發。
2 考慮節點剩余能量的RPL協議
2.1 RPL協議原始路由方案
目標函數決定了RPL協議的路徑選擇方式。目前RPL的官方文件中，只明確定義了零目標函數（OF0）[8]，即以跳數（HC）為最佳路徑選擇的唯一標準，而其他的目標函數則由開發者根據需求靈活定義。比如對鏈路可靠性要求較高的應用，可將鏈路質量作為路由選擇的首要考慮標準；而對能量受限的環境則可以定義在路徑中盡量避開電池供電節點。在文檔RFC6551[9]中，提出了多種可供開發者參考的路由度量。
在選擇路徑時，若只考慮跳數因素，必然會導致Sink周邊節點數據壓力過大，從而使關鍵節點能量過早消耗而死亡。文獻[10]將網絡的生命長度定義為第一個節點死亡的時間。對于能量受限的低功耗有損網絡，如何平衡能量消耗，延長網絡整體壽命，是協議要考慮的重要因素。
2.2 優化之后的RPL路由方案
目前已有多種針對無線傳感網絡能量優化的路由協議，比如分級能量路由協議LEACH和TEEN，以數據為中心的能量有效路由協議DD和SPIN，還有基于地理位置的路由協議GPSR和GEAR等[11]。 但這些協議都很難實現和RPL協議的融合。RPL協議是通過在container metric中，定義路徑選擇時所考慮的參數，然后再以一定的方式將所需要考慮的參數相結合，從而確定一個合理的路徑選擇方案。
本篇論文中采取的是跳數（HC）和節點能量（EN）相結合的方式。結合方式有兩種[12]，一種是Lex，一種是Add。Lex是指優先考慮跳數，只有在跳數相同的情況下，才考慮節點能量；而Add則是采取兩種參數綜合考慮的方式，按照一定的比例相結合，即：
其中：
本文對這兩種不同的結合方式做了仿真對比。
2.3 RPL協議改進前后的仿真對比
仿真工具采用的是美國UIUC大學開發的針對無線傳感網絡研究的J-Sim平臺，該平臺基于Java語言，和NS2相比具有內存消耗小、仿真速度快、有更好的可擴展性等優點。本文仿真了傳感網絡數據收集的場景。在100×100的區域里，規則的布置有100個節點，圖4所示是網絡節點布局圖和OF0的拓撲結構，其中最左上側的0號節點為數據匯聚節點，右下側的49-99和94-98這11個節點為傳感器數據采集節點。數據從右下側的11個源節點發送到左上側的0號節點。由于該網絡具有對稱性，1和10對稱，2和20對稱等，對稱節點的能量消耗基本一致。本文中重點仿真了具有代表性的1、2、11、12、22這幾個關鍵節點的能量消耗情況。
對于OF0，由于跳數是路徑選擇的唯一標準，節點位置固定的網絡，其拓撲結構也相對保持不變。圖4即為這種情況下的拓撲結構。由圖4中可以看到，節點1和節點10承載了大部分的數據量，幾乎任何從下側或者右側源節點發過來的數據都要經過這兩個節點轉發到Sink節點。而節點11，則只有來自源節點99的數據由它轉發。
圖5所示是系統節點能耗圖。其中圖5（a）為OF0方案下部分節點能量消耗圖。從圖中可以看出，最關鍵的節點1和節點10，能量很快就消耗殆盡。而節點11，則能耗相對較少。這對節點位置固定的網絡是很不利的，會使數據量較大的節點在短期內能量迅速消耗完而死亡，而其他非位置關鍵節點，則一直被閑置。造成網絡能耗分布極其不均勻，能量利用率不高。
接下來可以仿真跳數和節點剩余能量相結合的路徑選擇方式，圖5（b）為跳數和能量按照2∶8的比例加權所得到的能耗結果。從圖5（b）可以看出，節點1、10和11的能耗更為均衡，第一個節點死亡的時間大為延長。跳數和節點剩余能量相結合的路徑選擇方式，能一定程度上改善以跳數為唯一度量所造成了能量消耗不均的情況，從而延長關鍵節點的生命長度。仿真中也能看到，最佳路徑的拓撲圖一直處于動態變化，原先經過節點1和節點10到達匯聚節點的數據，有一部分從節點11分流，從而緩解節點1和節點10的壓力。
（a） HC路徑選擇方案節點能耗 （b） HC+EN路徑選擇方案節點能耗
本文也仿真了跳數（HC）和節點能量（EN）按照Lex的結合方式，即優先考慮最小跳數，當跳數相同的時候再考慮節點能量，以及在Add結合方式下按0.8HC+0.2EN和0.2HC+0.8EN的不同比例相結合的情況對比。最后得出的結論是，兩種不同的結合方式對網絡能耗均衡都有一定程度的改善；而Add的結合方式能耗更為均衡，且剩余能量所占的比例越高，改善的效果越為顯著。圖6所示是在不同路由策略下，關鍵節點能耗的對比情況。
4 結 語
本文描述了RPL協議的基本原理，并且對原路由協議的路徑選擇策略進行了改進，在只考慮跳數的基礎上，加入節點剩余能量的考慮，從而平衡了網絡能耗，延長網絡整體壽命。由于RPL是近幾年新提出的協議，隨著實踐的不斷深入，越來越多的新問題被提出，還有很大的研究空間。RPL協議在物聯網領域有著廣闊的應用前景，值得廣大學者進一步深入研究。
5 致 謝
本論文的工作得到了實驗室項目的大力支持。感謝國家自然科學基金（61271257），北京市自然科學基金（4122034）和教育部博士點基金（20120005110007）對本文研究工作的支持。
參 考 文 獻
[1] WINTER T. RFC6550 RPL： routing protocol for low power and lossy networks [S]. USA： Internet Engineering Task Force， 2012.
[2] VASSEUR J P， DUNKELS A.基于IP的物聯網架構、技術與應用[M]. ，田輝，徐貴保，譯.北京：人民郵電出版社，2011.
[3] DOHLER M. RFC 5548 routing requirements for urban low-power and lossy networks [S]. Internet Engineering Task Force， 2009.
[4] PISTER K. RFC5673 industrial routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force， 2009.
[5] BRANDT A. RFC5826 home automation routing requirements in low-power and lossy networks[S]. Internet Engineering Task Force， 2010.
[6] MARTOCCI J. RFC5867 building automation routing requirements in low-power and lossy networks [S]. Internet Engineering Task Force， 2010.6
[7] LEVIS P. The trickle algorithm draft-ietf-roll-trickle-08 [S]. Internet Engineering Task Force， 2011.
[8] THUBERT P. RFC6552 objective function zero for the routing protocol for low-power and lossy networks （RPL） [S]. Internet Engineering Task Force， 2012.
[9] VASSEUR JP. RFC6551 routing metrics used for path calculation in low-power and lossy networks [S]. Internet Engineering Task Force， 2012.
[10]廖夢澤.無線傳感器網絡生命期最優化[D].上海：上海交通大學，2010.
關鍵詞：移動Ad Hoc；NS2；延時；多路徑路由協議
中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2007)03-10681-03
1 引言
移動Ad Hoc 網絡又稱移動自組網、多跳網絡，它的特點是由結點移動引起的動態拓撲、信道帶寬有限和結點有限的存儲能力。面臨的關鍵挑戰是在動態環境下能在花費最小的情況下傳送信息，另外，對QoS 的支持也是一個重要的研究課題。目前存在的多數協議也都是路由表驅動或是源結點發起的按需路由協議，而且這些協議都是基于盡力服務模型的，無法滿足現近一些需要QoS路由的業務。在有線網的多路徑協議中，已經對QoS路由有很廣泛的研究，但是這些研究并不能適用于Ad Hoc網絡的。其中文獻[1,2,3]詳細闡述了移動Ad Hoc網絡QoS路由協議的發展現狀，文獻[4,5]對移動Ad Hoc網絡中的QoS約束作出了深入解析，文獻[6,7,8]提出一些新的支持QoS約束的移動Ad Hoc路由協議，在本文中，我們將給出一種多路徑QoS路由協議MQDSR，該路由能夠支持QoS約束并提供多路徑路由以減少路由發現過程和路由維護。
2 DSR協議描述
DSR（Dynamic Source Routing）協議是一種基于源路由方式的按需路由協議。在DSR協議中，當發送者發送報文時，在數據報文頭部攜帶到達目的節點的路由信息，該路由信息由網絡中的若干節點地址組成，源節點的數據報文就通過這些節點的中繼轉發到達目的節點。與基于表驅動方式的路由協議不同的是，在DSR協議中，節點不需要實時維護網絡的拓撲信息。
DSR路由協議主要由路由發現和路由維護兩部分組成。路由發現過程主要用于幫助源節點獲得到達目的節點的路由。當路由中的節點由于移動、關機等原因無法保證到達目的節點時，當前的路由就不再有效了。DSR協議通路由維護過程來監測當前路由的可用情況，當監測到路由故障時，將調用新的一輪路由發現過程。文獻[3]中詳細論述了DSR協議的路由發現及路由維護過程。
3 QoS參數的計算
隨著移動通信的不斷發展和多媒體業務的日益普及，在移動網絡上提供QoS保障的研究逐漸成為一個熱點。由于Ad Hoc網絡中結點的移動性和無線傳輸特性，導致對QoS約束的支持遠比有線網中困難。本文中，我們把帶寬的計算和預留作為QoS參數計算的主要問題。在時隙的Ad Hoc網絡中，計算帶寬不僅需要得到路徑上鏈路可用帶寬信息，而且知道如何安排時隙，所以在Ad Hoc網絡中計算帶寬是一件很困難的事情，而且是一個NP-完全問題，在這種情況下，往往用啟發式路由算法來解決這種問題。在我們將要提出的MQDSR中，使用文獻[4]中的啟發式路由算法來計算和預留帶寬。
4 MQDSR協議描述
針對現在移動Ad Hoc網絡中的大多數單路徑協議，我們在DSR路由協議的基礎，提出了一種多路徑的QoS路由協議MQDSR。
4.1 路由的發現過程
當一個源結點需要建立一條路由，但是還沒有目的地的路由信息時，它首先廣播一個QRP(QoS Route Probe)包到它的鄰接結點。當一個結點收到QRP包時，它將對帶寬進行計算，為了使用逐跳的方法計算可用帶寬，中間結點并不使用路由緩存去直接回復QRP包。下面給出了一個中間結點N處理QRP的算法的偽代碼：
IFCheckRedundantPkt(QRP.Source,QPR.QRPSN)||IncludedNodeList(QRP.Node_List,N))
DropAndExit(QRP)
AvailableBandwidth=ComputeBandwidth(QRP,N)
IF AdmissionDecision(AvailableBandwidth, QRP.Bmin)=0)
DropAndExit(QRP)
ELSE
QRP.TTL = QRP.TTLC1
IF QRP.TTL = 0
DropAndExit(QRP)
LogSlotInfo(QRP.Slot_List_Array)
AppendToNodelist(QRP.Node_List, N)
IF N! = QRP.Destination
Forward(QRP)
對于目的結點，當收到第一個QRP包時，它會向源結點發送一個QRR（QoS Route Reply）包，同時保存第一個QRP包記錄的路由，然后，目的結點將等待消息ROUTE_WAIT，同時收集其它的QRP控制包。目的地可能接收多個QRP，每一個都代表著一個從源結點到目的結點的可用的路由，我們采用了備份路由機制，因此可以用一個的選擇算法，在眾多路由當中選取一個最佳的作為首選路由，選取另一條作為備份，該算法如下：
NodeDisjointRoute=FindNodeDisjointRoute()
IF NodeDisjointRoute = 0
LinkMaxDisjointRoute=FindMaxLinkDisjointRoute()
IF LinkMaxDisjointRoute > 1
SelectRoutewithMinHop()
ELSE IF NodeDisjointRoute > 1
SelectRoutewithMinHop()
接著目的結點發送其它的QRR到源結點。因此，我們可以得到兩條源結點到目的結點的路由。
中間結點通過QRR包來進行資源的預留。如果源結點能接收到QRR包，一個端到端的資源預留將完成，同時，它會使用第一條建立的路由立即發送數據包。當接收到第二個QRR包時，這時將有兩條源結點到目的結點的路由，MQDSR協議中采用的簡單的包分配機制，把數據流分配到兩條路由上進行傳送數據，這樣可減少網絡負載。
4.2 路由維護
當一個結點發現它到下游結點的鏈路失效后，它將發送一個MQRP_Route_Error包到源結點。從斷開的結點到源結點之間的路由上的所有結點，當它們收到MQRP_Route_Error包時，將釋放預留的資源，同時丟棄隊列中所有的待發送的QoS請求包。當源結點收到MQRP_Route_Error包時，它將刪所有使用斷鏈的路由條目。如果兩條路由中，僅僅只有一條路由失效，源結點將使用剩下的那條路由繼續發送數據。如果兩條路由都已失效，那么源結點將重新發起一次新的路由發現過程。
5 正確性驗證及復雜性分析
定理1 由MQDSR選擇的路徑是無環的。
證明：假設p是一個以D為目的探測幀，而S(P, D)是路由算法選擇的路由，若S(P, D)中存在一個環路，則說明在路徑S(P, D)上存在一個節點i兩次收到了探測幀p并轉發p。這與DSR協議中規定的一個節點只能轉發一個探測幀矛盾。由于MQDSR遵循了DSR的該機制，因此S(P, D)必定是無環的。證畢。
定理2 在MQDSR協議的路由算法中，時間復雜性為O(2h)式中：h為Ad Hoc網絡中各條路徑中鏈路數量的最大值。
證明：在MQDSR協議的路由算法中，需要發送探測幀來建立路由，成功建立一條路徑需要花費的時間開銷是一個來回的時間。假設消息每經過一條鏈路花費的時間開銷是一個單位，而假設h是被選擇的多路徑中鏈路數量的最大值，則MQDSR協議算法路徑建立的時間復雜性為O(2h)，證畢。
定理3 在MQDSR協議的路由算法中，消息的復雜性為O(3h)。式中：h為Ad Hoc網絡中各條路徑中鏈路數量的最大值。
證明：在MQDSR協議算法中，主要使用兩個報文Route Request和Route Reply來發現路由，由于本協議路徑數目為2，則每次連接的成功建立會有最多3個報文。假設h為Ad Hoc網絡中各條路徑中鏈路數量的最大值，則每個報文最多會經歷h跳的轉發，所以報文消息復雜性為O(3h)。證畢。
6 訪真實驗與分析
以下仿真是在NS2中進行的，仿真環境及模型如下：
MAC層協議采用的是IEEE 802.11。無線電傳播模型是Two-Ray Ground Reflection Model，載頻是914MHz，帶寬為2M，天線采用OmniAntenna。
運行場景：采用NS的setdest隨機產生。50個節點在一個1000×1000的矩形區域按照random waypoint模型移動。每個節點隨機的向一個目的地運動，到達后，停留一段時間，繼續朝另一個方向移動，移動速度為3m/s到18m/s不等。
數據場景：信源用的是CBR（恒定比特率），包長512bytes。30個信源在仿真的過程中，在不同的時間開始發送數據包。
以下是實驗中，不同結點移動速率下的DSR和MQDSR的對比圖：
圖1顯示了，在不同的節點移動速度級別下，MQDSR與DSR的分組投遞率的變化情況以及之間的差異。從中可以看出，當節點移動速率越高時，兩個協議的性能總體上都有所下降，但另一方面，QMDSR比DSR有更好的分組投遞率，這是因為在DSR中，有較多的路由重建過程，網絡中產生了更多的數據包的沖突，而在MQDSR中，我們有兩條路徑可用，既使在其中一條無效的情況吧，還能用另外一條路徑繼續發送數據，所以在MQDSR協議的網絡擁有更好的吞吐量性能。
圖1 分組投遞率隨節點移動速率的變化情況
圖2中顯示了端到端的延時隨節點移動速率的變化情況，相比之下，MQDSR比DSR擁有更少的延時，這是因為，在DSR中路由重建較頻繁產生了大量的延時，而數據包的等待也會產生大量的延時，但是在MQDSR中，因為我們有兩條路徑可用，既使在其中一條無效的情況吧，還能用另外一條路徑繼續發送數據，所以延時相對較少。
圖2 端到端的延時隨節點移動速率的變化情況
圖3顯示了路由控制負載情況，我們可以看到在節點低速率情況下，MQDSR比DSR的負載要稍大，這是因為MQDSR在建立多路徑路由過程中，需要較多的控制報文，但是，隨著移動節點移動速率的增加，MQDSR的控制負載相對較少，這是因為DSR協議將比MQDSR產生更多的路由重建過程，而在MQDSR協議僅當兩條由源結點到目的結點的路由同時失效后，才會重新發起路由發現過程。
圖3 路由控制負載隨節點移動速率的變化情況
7 結束語
移動Ad Hoc網絡是一門新興研究領域，具有很高的實用價值，并具有極其廣泛的應用前景。其中路由協議是移動Ad Hoc網絡的核心技術之一，同時也是熱門研究的對象。本文針對Ad Hoc網絡中DSR路由協議進行了分析，結合多路徑路由算法思想，提出了多路徑QoS路由協議MQDSR，并進行了仿真實驗，仿真結果表明MQDSR路由協議在動態環境中擁有較好的性能。本論文中并沒有討論能量受限的問題，以及結點移動的預測問題，在今后的研究當中，能量，移動預測等也是路由協議中重要一環。
參考文獻：
[1] 孫寶林, 李臘元. Ad Hoc網絡QoS多播路由協議[J]. 計算機學報,2004,27(10):1402-1407.
[2] 李臘元，李春林. 計算機網絡技術[M]. 北京:國防工業出版社，2004.
[3] 肖小玲，李臘元，張翔. 移動Ad Hoc網絡QoS路由協議研究，計算機工程與應用，2006.01.
[4] C.R.Lin and J. S. Liu Bandwidth routing in ad hoc wireless networks. In IEEE Globecom, 1998.
[5] C.-R. Lin and J. S. Liu. "QoS Routing in Ad Hoc Wireless networks," IEEE Journal on Selected Areas in Communications, 1999,17(8):1426-1438.
[6] K.N.S.Chen.Distributed quality-of-service routing in ad hoc networks.IEEE Journal on Selected Area in Communications, 1999,17(8):1488-1505.
[7] R.Sivakumar, P.Sinha, and C.Bharghavan, V.a core-extraction distributed ad hoc routing algorithm.Selected Areas in Communications, IEEE Journal on, 1999,17(8):1454-1465.
關鍵詞：傳感器；無線傳感器；網絡路由協議；平面路由協議；層次路由協議
一、引言
近年來，隨著現代化科技的蓬勃發展，無線傳感器技術也越來越受到人們的關注和重視。無線傳感器網絡，主要由傳感節點、終端節點和觀察對象等三個部分組成。就目前來看，無線傳感器網絡在醫療監護、社區監控、礦井生產及軍事偵探等多個領域的應用正日趨廣泛。無線傳感器網絡路由協議，作為無線傳感器網絡中的關鍵技術，通過對其基本特征和設計要求，以及平面路由協議和層次路由協議等兩大分類的認識和了解，對于無線傳感器技術的發展和變革有著不容忽視的促進作用。
二、無線傳感器網絡路由協議
1.無線傳感器網絡路由協議的特點
無線傳感器網絡路由協議，主要是用來處理網絡中的傳輸數據，在無線傳感器網絡中充當著極為重要的角色。通過對無線傳感器網絡路由協議的分析，認為其具有以下幾點鮮明特點和局限性。
（1）終端節點的特點。傳感器的節點數量相對較大，促使其能夠作用于計算子系統、通信子系統、傳感子系統和能量供應子系統等多個方面，不過同時也加大了建立全局地址的難度，而且各節點的傳輸能力、處理能力和存儲能力也極為有限。
（2）傳感器定位特點。在無線傳感器中，由于終端節點的數量龐大，且通常是數據聚集的主要地方，因此，在進行傳感器定位上，主要工作是由終端節點來完成的。
（3）傳感器網絡特點。根據不同的應用場景，傳感器網絡的作用類型也不同。呈現功能多樣化的特點。
2.無線傳感器網絡路由協議的設計
（1）注重路由算法節能。在無線傳感器網絡路由協議的設計上，降低路由算法的耗能，在網絡周期運行、通信功能等方面起著決定性的作用。通過降低算法能量消耗，能夠有效延長網絡的生命周期。
（2）注重路由算法擴展。隨著無線傳感器的應用日趨廣泛，終端節點的數量也在不斷增加，給網絡造成了一定程度的繁冗。為此，在設計時注重路由算法擴展性的提高，能夠有效地融合新節點，從而提高網絡處理數據的能力，延長使用壽命。
（3）注重路由算法容錯。注重路由算法容錯能力的提高，能夠保證在分層結構的終端節點失效時，最大限度減輕簇頭的高負載，以免整個網絡陷入癱瘓。
3.要求數據融合
通過強化數據的融合，能夠減少無線傳感器在采集和傳遞數據方面造成的大量冗余信息，確保網絡系統的簡潔和信息的精確。
4.無線傳感器網絡路由協議的類別及分析
根據不同的角度，無線傳感器網絡路由協議可以劃分的類別也不同。通過路由發現策略，可以分為主動路由和被動路由，而從邏輯結構出發，則可以劃分成平面路由協議和層次路由協議等兩種。
（1）平面路由協議。
擴散法。即傳統的網絡路由協議，是通過源節點將網絡數據副本傳輸給相鄰節點，相鄰節點又將其發送給下一相鄰節點，以此來達到數據擴散并最終將數據傳輸給目標節點的方法。具有簡單實現、降低網絡拓撲信息以及路由算法消耗的能源，且能夠適用于要求較高的場合等優勢，但從另一個角度來看，這種擴散法很可能會造成信息爆炸、重疊發送信息及盲目使用資源等現象。
SPIN協議。是基于節點間的協商制度和資源自適應機制研發出來的通信路由協議，用于處理擴散法中的缺陷。通過在傳輸數據過程中，節點與節點之間的協商，能夠保證傳輸的數據的可靠性和可用性。
定向擴散。是采用梯度的形式，對節點傳輸數據方向進行搜索，以此來獲得匹配數據的新協議。運行的終端節點主要用命名機制來描述數據，并通過向所有節點發送被命名數據的任務描述符，從而實現數據的采集。相對來說，這種定向擴散協議，在節能和擴展方面具有更大的優勢。
（2）層次路由協議。
LEACH協議。通過采用聚類的形式發展起來的LEACH路由協議，能夠不斷隨機循環執行聚類首節點重構過程，以此來實現無線傳感器網絡中能量負載均衡分配。其重構過程主要分為類準備階段和就緒階段等兩部分。通過延長就緒階段的時間，同時縮短類準備階段的用時，能夠有效地節省資源，進而提高整個網絡生存的時長到15%。
PEGAGIS協議。是基于LEACH協議設計的，并在假定終端節點的同構和靜止的前提下，通過終端節點發送能量遞減的測試信號來找出相鄰最近節點。從而明確各節點之間的位置關系，并通過選擇所屬聚類來完成到sink的鏈路優化。不但促使整個網絡的生存時間是LEACH的兩倍左右，同時由于融合數據降低了收發次數，進而節省了系統能源。不過對于鏈中遠距離的節點，則較為容易引起數據延遲。
TEEN協議。該協議的主要特點是實時性，是基于LEACH的聚類結構及其運行模式，采用硬、軟閾值來發送檢測數據的協議。新硬閾值是由監測數據首次超過設定硬閾值時確定的。當節點發送的硬閾值變化幅度大于軟閾值界定范圍，則節點重新采集數據設定硬閾值。同時，節點能夠通過調節軟閾值大小，有效平衡監測精度與系統能耗。TEEN協議的實時性，促使其能快速反應并處理突發事件，但受其自身限制，該協議并不適合持續采集數據的應用環境。
通過對無線傳感器網絡路由協議相關知識點的分析和思考，能夠進一步加深人們對無線傳感器網絡的研究，推動該技術在國內相關領域的普及和發展。
參考文獻：
【關鍵詞】無線傳感網絡 分簇 多跳路由算法 移動性
1 引言
傳感器在計算和無線通訊中廣泛使用，如監測外部環境，把感知的數據轉化為用戶可以理解的信息。傳感網絡的應用是目前國際科學研究的熱點。隨著社會的發展，在很多的移動環境應用了無限傳感器，如海洋的監測、移動車輛的監測、動物的監測等，因此研究移動環境下的無線傳感器網絡越來越重要[1-2]。
傳感器網絡的移動性帶來了許多問題。如傳感器節點在成功部署之后由于節點的移動隨時變換位置，很容易造成拓撲的變化；通信鏈路建立之后，節點移動很容易偏離最初的位置，從而導致連接斷裂、路由中斷；節點移動造成數據延遲發送；節點的移動造成路由建立的頻率增大，從而增大能量的消耗，縮短了網絡生存時間。因此針對移動環境設計支持移動性的路由協議十分必要。
基于分簇的路由協議有很多。LEACH[3]的成簇思想貫穿于其后發展出的很多分簇路由協議中，如TEEN[4]、PEGASIS[5]、APTEEN[6]都基于分簇的路由協議，但在移動性的支持上存在不足，尤其當網絡規模增大時，缺陷就更加明顯。M-LEACH[7]是基于LEACH提出的支持簇頭和成員節點的移動協議，簇頭選取時考慮了節點剩余能量、位置及節點的移動速率，但沒有在簇的建立階段解決移動性問題。EMHR[8]算法是簇頭在數據傳輸時可以通過多跳傳輸，根據權值確定下一跳簇頭，這樣EMHR協議在網絡拓撲結構中平衡負載和降低簇頭能量消耗，此協議主要是針對靜態網絡。
分簇技術可以避免感知節點之間的信息傳輸，通過簇頭數據融合，減少數據冗余，減少發送數據量，降低能耗，更好地支持移動性。多跳傳輸技術是動態自組織，利用網絡中的節點動態建立和維持網絡連接。由于多跳技術的獨特性，無線傳感網絡多跳技術得到了極大的關注，大量信息表明多跳路由協議的能耗遠低于單跳路由協議。針對現有分簇路由中存在的缺陷，本文提出新的支持移動的簇頭多跳路由算法，以降低能耗。
2 EM-CHMR算法
基于LEACH-M算法，在感知節點移動且基站（BS）不移動的環境下，根據節點的移動信息進行分簇，分簇成功之后建立高效的多跳路徑，筆者提出能有效地支持移動性的簇頭多跳路由策略（EM-CHMR，Energy-efficient Mobile Cluster Head Multi-hops Routing protocol）。此路由策略中，簇首向基站傳輸數據引入了多跳路由機制，讓距基站較近的簇首適當承擔一些數據中繼轉發任務，把直接長距離通信變成間接的多次短距離通信，在支持移動下保證轉發簇首有充分的能量來進行數據轉發。
2.1 分簇的模型
簇頭多跳的簡單模型如圖1，模型中距離BS較遠的簇頭可以通過建立多跳路徑與BS通信，這樣可以降低自身的能量消耗。同時距離BS較近的簇頭不需要再進行多跳，可以直接與BS進行通信。模型中感知節點和簇頭都可以進行移動，但是BS是固定位置不移動；每個節點的移動速度大小都限制在一定范圍內；節點同構，且初始能量相同；傳感器節點得到的信息，可以使用GPS或其他位置檢測方案；傳感器節點的發射功率可以進行調節。
路由算法中利用文獻[9]提出的能量消耗模型，節點發射kbit數據到距離為d的位置消耗的能量為：
其中，Eelec表示發端電路運算和處理每比特數據的能耗；εfs和εmp為放大器的系數；d0為臨界距離。
2.2 簇頭的選取
簇頭選取算法是基于M-LEACH協議提出的，網絡模型是一個均勻的網絡，簇頭的數量確定方式與M-LEACH相同。根據簇頭數量把整個區域劃分為子區域，然后為每個區域選取簇頭。首先按照剩余能量利用閾值Eselect進行篩選，避免節點剩余能量不足造成早死現象。為了讓簇頭均勻分布并對整個傳感網絡實現完全覆蓋，把整個區域分成M個子區域，在每一個子區域中選取一個簇頭。假設第j子區域節點數Nj，每個節點坐標為（xi，yj），速度為vi。簇頭的最佳位置S0計算方式如下：
移動方向用θi（0O≤θi≤180O）表示，意為節點i的移動方向和連接節點指向最佳位置的直線形成的夾角（速度和直線的最小夾角）。最佳選擇則是節點移動方向是S0，即夾角越小越好。角度則是處理后的角度，其中θt是角度閾值。
如果簇頭移動速度過快則容易造成簇的破壞，移動速度慢則適合整個網絡的移動速度。式（4）表示節點i處理后的速度，其中vt是速度閾值，vi為節點i的速度。
節點i為簇頭的代價函數為：
由式（5）看到，、和變小時值也變小，則是節點i的速度因子，因此最小的節點為簇頭最理想的節，若存在多個節點，取最小值。
2.3 簇的形成
簇的形成階段，就是在感知節點選擇簇頭鍵入，并在其中形成簇。簇頭和感知節點的移動使得節點與簇頭位置關系的變化很難計算。為了降低復雜性，把速度大小和速度方向一起分析，利用速度和角度得到速度因子。
其中，vi根據閾值計算，θi是感知節點移動方向與連接感知節點、簇頭間直線所形成的夾角，θ0是簇頭移動方向和連接簇頭、感知節點的直線所形成的夾角。可以看出，移動因子不是兩個速度的矢量和，而是要考慮到兩個速度的移動方向變化，才能夠簡單高效地對節點移動性進行評估。
基于EECS[10]協議，本文提出新的通信代價函數：
其中E=En_init/En_current，w是具體環境決定的權值，CHi是區域i的簇頭，BS為基站，d是距離，f是兩者之間的通信代價，EX為期望。Si為感知節點。Cost（i，j）表示成員節點i到簇頭j的通信代價，在簇的形成過程中，每個成員節點選取通信代價最小的簇頭加入簇區域。
2.4 多跳路徑建立
在數據傳輸中選擇下一跳的簇頭，對簇頭能量消耗有重要的影響。如果BS在簇頭傳輸的有效范圍內，簇頭將直接與BS進行通信，否則通過其他簇頭進行多跳傳輸。
為了多跳能量消耗，計算通過簇頭跳一次的情況，即從簇頭i到j再到BS。設簇頭i和j的距離為d（i，j），j和BS的距離為d（j，S）。根據無線通信能量消耗模型，總的能量消耗模型ET為：
可看出能量消耗的影響因素為d（i，j）和d（j，S），所以，簇頭i發送消息經過n個簇頭到BS的能量消耗為：
式（10）充分體現了距離對簇頭能量的消耗的影響，因此可用距離的平方和作為權值函數的一個重要因素。
由于無線傳感器網絡中節點是移動狀態，尤其在簇頭多跳網絡中，簇頭的移動很容易對多跳路徑造成破壞，因此在多跳路徑建立過程中要選取一條比穩定且受速度影響較少的路徑。在簇頭多跳路徑中簇頭的移動可以縮短整個路徑的距離，也有可能使得路徑遭到破壞。
由圖2看到簇頭H0經過（H1， H2， H3）到達基站BS，（S1， S2， S3）分別為簇頭到直線OS的距離，θ為H3移動方向與S3形成的角度。在多跳路徑中最好的效果是三個簇頭向OS移動，并且三個簇頭和OS的距離波動不要太大，因為波動過大會造成傳輸距離加大。因此要（0， S1， S2， S3， 0）（前后兩個0分為H0和BS到OS的距離）的方差來衡量節點的波動，它們的期望衡量嚴重偏離OS的大小。由于節點的移動造成簇頭位置的不斷變化，為了較好地反應簇頭的移動，要充分考慮簇頭節點的移動速度大小和方向。Si在OS左面值為正，右面值為負。角度則是指向OS的銳角，反向為鈍角。當多跳經過簇頭數為n時，計算（Si+vitcosθ）的期望：
計算對應方差：
其中t是根據輪到時間設定的值，設為半個輪時間。則新的權值函數如下：
Ei_residual是簇頭i的剩余能量，Ei_init是初始化能量。為了控制σ和es值極端情況（只等于0），約束如下：
在簇頭選取成功時，向周圍廣播信息通知普通節點，每一個簇頭會接收到周圍相鄰的信息，信息包括ID、移動信息、剩余能量等。每個簇頭把周圍的信息進行存儲，然后根據收集的鄰居節點找出到BS的所有路徑，利用權值函數（11）進行計算，權值最小的路徑的第二個簇頭作為下一跳節點。利用此算法，簇頭都可以找到下一跳節點。如果某簇頭能量不足作為多跳節點時，就向周圍發送取消作為多跳節點的信息，周圍簇頭把該節點記錄信息取消，從新選取下跳節點。
3 實驗結果
實驗無線傳感器網絡有100個感知節點組成，分布在100m*100m的區域中，基站BS隨機放在此區域中。速度范圍為（0， 2）m/s，速度閾值為0.3m/s，角度閾值為10o，方差和期望的閾值為1，相關參數如表1：
圖3表示隨著時間延長，感知節點逐漸出現了死亡現象，EM-CHMR協議的死亡節點出現較晚，兩種節點死亡數量在300s之后大量出現。在600s之后新協議的存活節點數量明顯高于M-LEACH協議的節點存活數量，表明簇頭多跳網絡較好地均衡了簇之間的能量，降低了感知節點的死亡數量。
圖4展示了能量消耗，可以明顯看出M-LEACH能量已經消耗遠高于EM-CHMR，在900s時M-LEACH能量消耗完畢，而EM-CHMR還有能量剩余，從而有效地延長了網絡生存時間。能量消耗和存活節點數量的變化充分體現了支持移動的簇頭多跳路由協議能夠較好支持移動，平衡節點能量，降低能耗，延長整個網絡的存活時間。
4 結束語
本文針對無線傳感器網絡的移動性，基于LEACH提出了EM-CHMR路由算法，保持了按輪進行分簇，對簇頭節點采用了多跳算法，提出了信息權值函數及建立多跳路徑算法。仿真結果證明該方案支持移動的簇頭多跳路由策略，使得能量消耗均衡地分布在各節點上，保證了數據盡快地傳輸到基站，彌補單跳的不足，從而使網絡壽命得到延長。支持移動的簇頭多跳路由協議的維護機制對簇和路徑的生存時間有很大的影響，因此，為了使移動傳感網絡中更好地降低能耗，還需要在路由維護機制方面展開更深一步的研究。
參考文獻：
[1] AKYILDIZ L F， SU WEILIAN， CIRCI E. A survey on Sensor networks[J]. IEEE Communications Magazine， 2002，40（8）： 102-114.
[2] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer Networks， 2008，52（12）： 2292-2330.
[3] HEINZELMAN W R ， CHANDRAKASAN A， BALAKRISHNAN H. Energy-efficient communication protocol for wireless micro-sensor networks[C]. Proceedings of the 33rd Annual Hawaii International Conference on System Sciences（HICSS）， Maui， HI， 2000： 1-10.
[4] MANJESHWAR A， AGRAWAL D P. TEEN： a routing protocol for enhanced efficiency in wireless sensor networks[C]. Parallel and Distributed Processing Symposium， Proceedings 15th International， 2001： 2009-2015.
[5] LINDSEY S， RAGHAVENDRA C S. PEGASIS： power efficient gathering in sensor information systems[C]. Aerospace Conference Proceedings， 2002： 1125-1130.
[6] MANJESHWAR A， AGRAWAL D P. APTEEN： a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks. Parallel and Distributed Processing Symposium[C]. Proceedings of the International， 2002： 195-202.
[7] LAN TIEN NGUYEN， DEFAGO X， BEURAN R， et al. An Energy Efficient Routing Scheme for Mobile Wireless Sensor Networks[C]. Proceedings of the 2008 IEEE international symposium on wireless communication systems （ISWCS）， 2008： 568-572.
[8] HUANG WEN WEN， PENG YA LI， WEN JIA， et al. Energy-Efficient Multi-hop Hierarchical Routing Protocol for Wireless Sensor Networks[C]. 2009 International Conference on Networks Security Wireless Communications and Trusted Computing， 2009： 469-472.