【文章內容簡介】 Routing principle of directional diffusion 除了平面路由協議，同時還存在分層結構的層次路由協議。層次路由協議又稱分簇路由協議，就是采用簇的概念對傳感器節(jié)點進行層次上的具體劃分。若干個距離相近的節(jié)點構成一個簇，而每一個簇會從中選出一個簇頭節(jié)點。同一網絡中簇與簇之間是可以進行網關上的通信。（LEACH）在 LEACH 算法中，首先進行建立階段的簇頭選擇部分。在 WSN 中的全部節(jié)點都可以擔任本輪中簇的簇頭節(jié)點，但是簇頭節(jié)點由誰擔任需要標準衡量的：首先判斷每一個節(jié)點是否在過去的操作中擔任過簇頭節(jié)點，簇頭節(jié)點需要沒有擔任簇頭的剩余節(jié)點中選出。每個節(jié)點不可以重復擔任簇頭節(jié)點，除非全部節(jié)點都已經擔任過簇頭節(jié)點；其次，取決于整個網絡選取簇頭節(jié)點的個數與全部節(jié)點總數的比值，此值在算法執(zhí)行之前已經設置完畢，這兩方面共同決定簇頭節(jié)點的產生。在初始階段 WSN 內的每一個節(jié)點都會隨機生成一個 0 到 1 之間的數，如果閾值 T (n)大于生成的數值，那么此節(jié)點在本輪將擔任簇頭節(jié)點。 T (n)的計算公式如下：公式（21） 這里，P 表示簇頭節(jié)點與網絡區(qū)域內節(jié)點總數之間的商；r 表示當前所處的輪數；G 代表在過去一輪中沒有擔任過簇頭的剩余節(jié)點的集合。當簇頭節(jié)點被選出時，它們會向網絡中的每一個普通節(jié)點發(fā)送公告消息。此時網絡中的普通節(jié)點接到此輪選出所有簇頭節(jié)點發(fā)出的公告消息，它們判斷接收信號的強弱并且結合最小耗能原則，選擇信號最強的簇頭節(jié)點作為自己本輪的簇頭并向其發(fā)送確認消息，確定加入該簇。成為簇內成員后，都有自己的工作時間表，按照 TDMA 開始進入數據傳輸階段。當這一輪所有的節(jié)點都發(fā)送完數據后，簇頭節(jié)點開始處理數據，因為基站較遠，傳輸耗能較多，需對收到的全部數據進行融合、壓縮處理，將優(yōu)化好的信息以最小的能量傳遞給基站。至此一輪全部完成，整個網絡將進入下一輪操作，開始再次選取簇頭節(jié)點[8]。（PEGASIS） PEGASIS(PowerEfficient Gathering in Sensor Information Systems)協議是在LEACH 路由算法的基礎上進行改進的，首先在當前網絡中選擇一個節(jié)點作為鏈首并建立一條相對最優(yōu)的鏈路，鏈首節(jié)點將數據處理后的綜合信息發(fā)送給基站(BS)。由于鏈首節(jié)點的承載大量負擔，所以 PEGASIS 算法采用網絡中全部存在的節(jié)點，讓它們輪流擔任鏈首節(jié)點進而使整個網絡能量達到相對的均衡。此算法可以有效地延長網絡的生命周期，節(jié)點只需跟最鄰近的節(jié)點進行通信。當網絡內所有節(jié)點都與鏈首數據傳送后，全部的節(jié)點會進行新一輪的輪流交替工作。圖23所示，PEGASIS 算法數據傳輸過程，這里的傳輸使用令牌(Token)，首先確定鏈首，這里 C 2被定為鏈首，將 Token 沿著鏈路傳給 C 0, C 0將自己的信息傳遞給C1 ，而 C1 將接到 C 0的信息和自己的信息進行處理，將有效數據傳送給 C 2。另一側同樣過程，Token 發(fā)送到 C 4， C 4將信息傳給 C 3， C 3將自己和 C 4的信息進行處理后發(fā)送給鏈首 C 2。此時 C 2將收集的數據融合整理后傳送給 BS。 圖23 PEGASIA數據傳輸鏈的形成 Fig 23 The formation of PEGASIA data transmission chain 由于這種通信機制可以使網絡能量均勻的分布到每一個節(jié)點成員，并且每個節(jié)點都是以功率的最小值進行數據傳遞，因此能量得到有效地利用，運用PEGASIS 協議時網絡的生命周期比運用 LEACH 協議時延長近一倍左右[9]。 路由協議的比較 在WSN中采用平面路由算法，其中所有的傳感器節(jié)點都要有公平對待，其執(zhí)行的任務和所起的作用是一樣的。當在WSN中采用層次式路由協議時，節(jié)點有兩部，分為簇頭節(jié)點和成員節(jié)點，簇頭節(jié)點先集中成員節(jié)點采集到的信息然后對其進行融合，將最終結果發(fā)送到基站，Ifn成員節(jié)點的任務只是將自己采集到的數據完整的傳送給相應的簇頭節(jié)點。層次式路由協議不在同一平面，簇頭節(jié)點和成員節(jié)點在整個過程中各自的任務和所起到的作用是有很大區(qū)別的。層次式路相對平面路由存在很多優(yōu)勢，概括為以下幾點: (1)能量方面，雖然平面路由已經在節(jié)能上做了大量改進，但其基本思想還是先找到一條或者幾條綜合方面較優(yōu)的路徑，然后通過這些路徑完成任務，導致節(jié)點的能量損耗方面不是很均勻。層次路由協議采用動態(tài)構造，因而消耗能量比較少并且其能量消耗分布較均勻，能有效的延長網絡壽命，平衡網絡負載； (2)開銷，平面路由是通過競爭來安排時間順序，層次路由則是預先確定的，層次路由減少參與WSN路由算法計算節(jié)點數量，減少交換路由信息所需通信的一系列開銷以及維修保護路由表需要的內存開銷； (3)分層路由協議的思想是形成預先特定簇型的模式，通過選舉方式產生一個相對穩(wěn)定的子網絡，減少了WSN拓撲結構的變化及其對路由協議所產生的影響； (4)每個簇頭節(jié)點對其相應簇內的普通節(jié)點進行管理，方便快捷將處理過的數據信息地向基站傳送，如能量情況、安全問題、是否出現事故等。另外地方基站也可以通過簇頭節(jié)點有效地向被監(jiān)測網絡中的普通節(jié)點下發(fā)命令，這是平面路由無法比擬的。 總體來說，判斷一個WSN其路由協議的好壞，主要從節(jié)能方面、網絡生命周期長短、傳輸推遲時間、可延展性等主要性能指標。同時，也觀察到WSN路由協議之間差別很大，網絡中不存在一個通用的路由協議[14]。 表21 無線傳感器網絡中典型路由協議比較 Comparison of typical routing protocol LEACH路由算法描述1. 簇頭選取 在 LEACH 算法中，首先進行建立階段的簇頭選擇部分，在 WSN 中的全部節(jié)點都可以擔任本輪中的簇頭節(jié)點，但是簇頭節(jié)點由誰擔任是存在衡量標準的。首先，判斷每一個節(jié)點是否在過去的操作中擔任過簇頭節(jié)點，簇頭節(jié)點需要未擔任簇頭的剩余節(jié)點中選出。每個節(jié)點不可以重復擔任簇頭節(jié)點，除非全部節(jié)點都已經擔任過簇頭節(jié)點；其次，取決于整個網絡選取簇頭節(jié)點的個數與全部節(jié)點總數的比值，此值在算法執(zhí)行之前已經設置完畢，這兩方面共同決定簇頭節(jié)點的產生。在初始階段 WSN 內的每一個節(jié)點都會隨機生成一個 0 到 1 之間的數，如果閾值 T (n)大于生成的數值，那么此節(jié)點在本輪將擔任簇頭節(jié)點。T（n）的計算公式如公式(21)。2. 簇形成階段當簇頭節(jié)點被選出時，它們會向網絡中的每一個節(jié)點發(fā)送公告消息。此時，網絡中的普通節(jié)點接到此輪選出的所有簇頭節(jié)點發(fā)出的公告消息，它們判斷接收信號的強弱并且結合最小耗能原則，選擇信號最強的簇頭節(jié)點作為本輪自己的簇頭并向其發(fā)送確認消息，確定加入該簇。當普通節(jié)點的確認消息都發(fā)送完畢后，簇頭節(jié)點得到了自己簇內成員名單，由此生成一個 TDMA(Time Division Multiple Access)時間表，這是簇頭節(jié)點制定的通信時間順序表，每個成員在屬于自己的時間段進行信息交流，在不屬于自己的時隙內則不進行工作，節(jié)省節(jié)點能量。此時簇