基于資源調度的靜態路由算法（ＳＣＩＲＳ）設計

摘要：文章首先介紹資源調度的靜態無線傳感器路由算法基于的兩個假設。在兩個假設條件的基礎上，介紹了所設計的基于資源調度的靜態路由算法（SCIRS: Static Clustering with Intra-cluster Resources Scheduling）的運行機制，包括集中式網絡拓撲計算、網絡拓撲形成和簇內調度傳輸。對基于資源調度的靜態路由算法（SCIRS）作一個定性的分析之后，最后給出這個路由的一個改進算法，即低耗能靜態分簇路由算法（LESCS：Low-energy Static Clustering Scheme）。

關鍵詞：路由算法；能量均衡消耗；資源調度

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)25-1519-04

The Design Based on Static Clustering with Intra-cluster Resources Scheduling

LI Hua-ying

(Jiangxi Province the University of Nanchang Army Department of Institute of Culture， Nanchang 330103， China)

Abstract: This paper firstly introduces the two assumptions the resource scheduling of static wireless sensor routing scheme based. Based on these two assumptions， introduces the operating mechanisms of the SCIRS(SCIRS:Static Clustering with Intra-cluster Resources Scheduling)， After imbibing the results of the previous research， this paper proposes one routing schemes， which are Static Clustering with Intra-cluster Resources Scheduling(SCIRS)， to solve performance deterioration caused by unbalanced energy consumption. The starting point for design， application， operation mechanism and analysis details of these two schemes are also elaborated in relevant sections of the paper.

Key words: routing scheme; balanced energy consumption; resource scheduling

1 引言

基于資源調度的靜態路由算法(SCIRS)和動態路由或者分布式計算路由相比，其整個路由算法在執行過程中，將耗能大的網絡分簇和網絡拓撲計算等任務用資源幾乎不受限制的基站來執行。從而避免了傳感器網絡使用傳感器節點進行網絡拓撲計算和路由發現等導致的過大能量開銷。也由于使用集中式網絡拓撲計算，從而不需要傳感器節點在路由發現過程中不斷的發現新路由而導致的能量開銷。這樣的靜態網絡可靠性高，網絡結構簡單。最大可能的減少了高效率網絡的建立過程的信息傳輸過程。這種路由算法是建立具備如下兩個假設的基礎。

2 資源調度的靜態無線傳感器路由算法基于的兩個假設

2.1 假設所有傳感器節點分布的位置信息可被分布區域附近的基站知道

也就是說，無線傳感器節點分布區域附近的基站可以記錄整個無線傳感器網絡的所有節點的位置信息。在大多數應用中，無線傳感器網絡所采集的數據要求和位置信息相關聯。例如，分布在山區高速公路上的交通檢測傳感器網絡中，當有某一個傳感器節點檢測到道路情況異常時，需要將發生道路異常的區域的位置信息或者位置信息對應代碼和發生異常情況的狀態信息整合在一起，作為一個數據包發送出去，通知遠程道路檢測系統。擁有智能家庭網絡的房子中，某一個壓力傳感器檢測到房子的某一面墻壁受到的壓力遠大于其他正常水平時，也需要將承受大壓力的墻壁的位置信息，在大多數情況下也就是傳感器自身的位置信息，和壓力信息等一些目標物體的狀態信息做一個數據整體發送到中央監控系統上用于觸發整個房子的安全系統。散布在動物生態棲息區的傳感器也需要將自身的位置信息和檢測到的動物種類和數量等信息一起發送到科研人員的終端上，才能幫助科研人員分析動物的棲息等生活習性。由此可見，在大多數應用中，無線傳感器網絡節點的位置信息和無線傳感器節點檢測到的數據一樣重要。

關于無線傳感器網絡節點實用的位置信息大概分為絕對位置信息和相對位置信息。絕對位置信息一般可以通過GPS等定位手段得到。相對位置信息可以通過傳感器節點之間的相對位置或傳感器節點和基站之間的相對位置來計算得到。通過GPS得到的位置信息，一般是通過專有的GPS芯片來接受衛星信號，然后計算出準確的位置信息。其特點是精確度高，成本高，適合檢測區域較大的無線傳感器應用。相對位置信息可以通過接收來自不同基站的參考信息，然后通過計算信號接收的時間差和方位差就可以得到傳感器節點自身的相對位置信息。在大多數的無限傳感器應用中位置信息都至關重要，并且可以通過不同途徑獲得不同精確度的位置信息，所以假設本文要討論的資源調度的靜態無線傳感器路由算法是在基站可以獲知所有傳感器節點位置信息的基礎上設計的。

2.2 假設所有節點在散布到目標檢測區域后位置上沒有改變或改變很小

在大多數的應用中，無線傳感器網絡的節點都是能量等資源有限的獨立節點，幾乎不會裝備用來改變位置的動力裝置。但是在一些場合下，不可避免的存在一些外界因素導致的傳感器節點的位置變化。例如溫度傳感器節點會在一些特定情況下隨著附著的被檢測物體一起移動而導致位置的細微變化。所以當這些節點被分配到目標檢測區域后，幾乎是不移動的或者說位置信息幾乎是不改變的。如果傳感器節點被安置于某一固定地點后，在其有效生存時間內不移動或者只有很小的移動，就可以等效為網絡的拓撲結構在大部分時間內都是不發生變化的。

在第二假設基礎上，可以利用集中式網絡拓撲計算算法來計算出一個近似最佳的網絡拓撲結構。

3 集中式網絡拓撲計算（網絡的分簇）

資源調度的靜態無線傳感器路由算法在所有傳感器節點被安置在被檢測目標區域以后，會通過基站所掌握的信息計算出一條近似最佳路由。

集中式網絡拓撲計算將網絡拓撲的計算任務分配給具有較強信息處理能力、資源不受限制的終端，大多數情況下會是被安置在被檢測目標區域的基站。其一般過程為，首先基站收集整個網絡的傳感器節點信息，例如每個節點位置信息和每個節點的能量信息。然后根據一定規則計算整個網絡的最佳路由。將網絡的拓撲結構的計算任務分配給基站，可以有效減少網絡拓撲計算階段傳感器節點的能量損耗。

與使用傳感器節點來分布式計算網絡的拓撲結構的路由發現過程相比，集中式網絡拓撲計算可以有效減少網絡節點的能力消耗，并且路由的發現與建立過程耗時短，路由效率高，可靠性好。集中式網絡拓撲計算的缺點是，路由計算的靈活性不夠好，不適合結構或拓撲隨時間變化較大的網絡。這也是為什么無線傳感器節點在散布到目標檢測區域以后幾乎沒有位置上的改變或者改變很小的理由。只有在保證了傳感器節點沒有移動性或者移動性很小的情況下，才可以使由集中式網絡拓撲計算出來的路由性能保持在一個比較理想的狀態下。

在基于資源調度的靜態路由算法(SCIRS)中，已經假設了安置在被檢測目標區域的基站掌握著所有無線傳感器節點的位置信息。所以集中式網絡拓撲計算的工作可以簡化為利用一定規則來計算出一條在這種規則下的最佳路徑。集中式網絡拓撲計算常用的規則有：整個網絡在傳送一定的數據包時耗能最小，網絡傳輸從源節點發送數據到目標節點接受到數據的網絡延遲最小，網絡傳輸從源節點發送數據到目標節點接受到數據的網絡路徑最短（網絡的跳數最短），使網絡中數據在保持一定穩定性或者冗余性的條件下滿足耗能最小，網絡的生存時間（從無線傳感器網絡被安置在被檢測目標區域開始檢測目標到無線傳感器網絡維持的檢測性能已經不能滿足應用的需求之間的時間）最大等。

在基于資源調度的靜態路由算法中選用使網絡按地域最平均分簇作為計算網絡拓撲的規則。網絡分簇不均勻是無線傳感器網絡中經常遇到的一個問題。LEACH雖然可以使每個無線傳感器節點都有均等的機會成為網絡中簇的節點，但是LEACH沒有很好的解決網絡平均分簇的問題。有可能在一個很小的區域中出現兩個以上的簇頭，很大的區域可能只有一個或者沒有簇頭的情況[1，2]。當很小的區域中出現多個簇頭時，可以通過協商使兩個以上的簇融合為一個簇，但是協商的過程本身就會使網絡消耗更多的能量，從而導致路由算法性能的下降。

■

圖1基站發送分簇信息廣播

■

圖2 簇頭的選擇

如圖1所示的被檢測目標區域使用按地域平均分簇作為計算網絡拓撲的規則后，可以將網絡分割為如圖所示的網格狀網絡。在基于資源調度的靜態路由算法(SCIRS)中， 在一個小方格區域內的所有節點被劃分為一個簇。然后將每個小區域中最靠近小區域中心的無線傳感器節點選擇為簇頭，如圖2所示。簇頭用于管理簇內其他無線傳感器節點，使簇內所有無線傳感器節點協調工作。然后基站會發送一個至整個網絡所有節點的廣播通知簇的劃分和簇頭的位置信息。

由于在分簇的無線傳感器中簇頭和簇內普通節點的通信比簇內普通節點之間通信更頻繁，所以按地域平均分簇可以保證簇內同樣的通信量下簇內的整體通信耗能接近最小耗能，尤其是可以節約簇頭的通信消耗，延長簇頭的生存時間。簇頭又是決定基于資源調度的靜態路由算法(SCIRS)主要網絡性能的一個重要角色。

基于資源調度的靜態路由算法(SCIRS)將網絡分簇以后簇的組成不再變化，也就是說一旦一個無限傳感器節點被劃分到某一個簇中，直到這個節點消耗完所有能量死亡之前都是為這個簇工作。這也是無限傳感器網絡中靜態路由的一個特點。靜態路由和集中式網絡拓撲計算都會導致路由算法的靈活性比較差。反映在和動態路由和分布式計算網絡拓撲結構的路由算法的特性比較中，就是在網絡運行一段時間以后（一般情況下可能會是網絡生存的后期，或者說網絡性能開始出現下降的階段），如果有一些節點較其他節點提前因為消耗完能量而導致節點失敗時，使用靜態路由或集中式網絡拓撲計算得到的路由的性能會急劇下降。特別是網絡的骨干節點（在大多數情況下可能為簇頭）失敗后，整個網絡的性能下降劇烈甚至到整個網絡不能工作。所以如何克服集中式網絡拓撲計算得到的靜態路由在出現網絡中節點少量失敗時會導致整個網絡的性能急劇下降，是在基于資源調度的靜態路由算法(SCIRS)中要解決的一個重要問題。

4 網絡拓撲形成（簇的形成）

完成了對網絡的分簇過程之后，基于資源調度的靜態路由算法(SCIRS)進入第二個階段，簇的形成。在簇的形成過程中，除了簇頭和普通簇內節點，還有另外一個簇內角色就是網關。簇內網關的作用就是把簇內的要發送的數據收集、融合，然后負責和傳輸路徑上的下一個傳輸簇進行通信傳輸。當網絡中的無線傳感器節點接收到來自基站的含有簇的劃分和簇頭的位置信息的廣播時，除了被選擇為簇頭的節點，其他節點都會選擇離自己距離最近的簇頭向其發送要求加入簇的請求信息。節點向簇頭發送的請求加入簇的信息中會包含自己位置信息和自身可用能量信息。簇頭接收所有要求加入自己所管理簇的請求信息，然后記錄每一個請求節點的位置信息和可用能量信息。然后，簇頭會給每一個加入的節點分配一個編號，并選擇其中的一個節點作為網關。簇內選出來的這個網關，主要負責將簇內其他節點的信息收集起來，然后向臨近的簇發送這些信息。簇內的編號是簇頭用來調度不同的節點為簇間傳輸代理，并且可以保證不同的節點都有相同的概率成為網關。簇頭記錄簇內每一個節點的可用能量信息用來保證不會讓能量過低的節點承擔簇之間的通信任務。

經過網絡拓撲形成這一個階段，網絡中所有傳感器節點都被劃分到不同的簇內。在簇內，節點被分為簇頭，普通簇成員和網關三種類型的角色。簇頭負責管理簇內所有成員和調度簇內節點之間的任務分配。

對于無限傳感器來說，其用來驅動無線通信模塊的能量消耗和維持其他功能模塊的能量相比約相差兩個數量級，其他功能模塊的耗能可以忽略不計。在無線通信模塊的耗能中，包含用于驅動發送電路的能量消耗和用于驅動接受電路的能量消耗。和驅動發送電路的能量消耗相比，接收電路消耗的能量約比發送電路消耗的能量小兩個數量級。所以，在考慮如何節約無線傳感器節點的能量消耗時，首先要考慮的是如何節約無線傳感器節點在無線電發送功能模塊上的能量消耗。由于通過無限鏈路發送的無線電信號在空間的衰減和距離的平方成反比，為了保證發送的信息可以被接受的節點正常接受，發送節點在發送信息時其信號的強度和發送的距離的平方成正比。由此可知，通信距離越遠，發送節點消耗的能量越多。在基于資源調度的靜態路由算法(SCIRS)的分簇網絡結構中，網關負責和相鄰簇的通信，所以消耗能量較其它節點大。于是可以考慮使用簇頭來檢測各個節點能量，然后周期性的調度不同的節點作為網關，負責和相鄰簇之間的通信。這樣就可以將簇間通信這個消耗能量過多的任務分配給簇內所有無線傳感器節點，從而防止簇內各部節點提前失敗的發生。

5 簇內調度

由圖3可以看出來，網關節點負責將收集簇內的信息并且發送到下一跳的節點上。由前面分析可知，無線傳感器節點在驅動其通信模塊時消耗的能量與距離的平方成正比。而接受信息消耗的能量又比發送信息消耗的能量小兩個數量級。所以負責簇間通信的網關節點的能量消耗要大于普通節點發送信息至網關節點時消耗的能量。如果這種網絡結構一致不發生變化的話，網關節點就會由于能量消耗過大提前失敗。從而會導致整個網絡傳輸性能的惡化。而簇頭節點由于負責整個簇的管理，而且也維持正常的和網管節點的通信。所以簇頭節點在一次簇內通信過程中也會比其他非網關節點消耗多一點的能量。由此可以看出，在一次簇內通信中，消耗能量最大的是網關節點，其次是簇頭，然后是普通簇內節點。所以本文嘗試使用簇頭對簇內所有節點進行周期性的調度。將承擔通信消耗能量最大的簇間通信的網關角色分配到簇內不同的節點上。

■

圖3 傳感器網絡的分簇和數據傳輸

簇頭執行每兩次網關節點調度的時間稱為一個回合（round）。在網絡結構上，每兩個回合之間的區別為每個簇內的網關可能是不一樣的節點。由于網絡內的路由信息是由基站在給定條件下作集中式計算出來的信息，網絡中每一個簇只負責將收集到的信息發送到下一跳的簇內，如圖4所示。

圖5是相鄰兩個簇的簇頭進行網關節點調度之后，不同的回合時兩個簇之間通信的拓撲結構示意圖。圖4所示圖中簇1中，node1.5，node1.3為網關，其他節點node1.1、node1.2和node1.4為普通簇內節點。普通簇內節點和簇頭都將采集到的信息發送到網關節點node1.3，網管節點node1.3將來自簇內的信息收集起來并作必要的信息融合，然后將融合后的信息包發送到簇2的簇頭節點node2.3。整個過程如圖4所示。

為了避免簇1內網關節點node1.3由于承擔簇間通信而導致能量消耗過快，過一定的時間后，簇1的簇頭node1.5會根據簇內各個節點能量的情況進行簇內網關角色的重新分配。如圖5所示，簇1的簇頭node1.5選擇節點node1.2作為簇內的網關節點。所有簇內節點都會向新的網管節點node1.2發送采集到的信息，然后新的網管節點node1.2會將收集到的信息發送到路由路徑上的下一個簇內的簇頭。

每過一段時間，簇頭都會根據記錄的每個節點的能量情況來選擇網關節點。簇頭使用節點的序列號進行簇頭調度。每調度一次都會增加自己維持的一個序列號。簇頭使用這個序列號對簇內節點的數目求余數，然后選擇對應的節點作為網關。當簇頭通過序列號選擇的節點的能量低于一個預定的閥值時，簇頭就會增加自己維持的序列號，直到找到一個有足夠能量可以承擔網關通信任務的節點。圖6描述了基于資源調度的靜態路由算法(SCIRS)在簇內的網關選擇算法[3-5]。

基于資源調度的靜態路由算法(SCIRS)使用基站集中式網絡拓撲計算得到網絡的分簇信息和拓撲結構。在得到網絡分簇信息和網絡拓撲結構之后，網絡中的無限傳感器節點會加入不同的簇。這些簇由基站指定的簇頭來管理。簇頭會周期性的調用自己所管理簇內的普通節點扮演網關角色。簇頭、網關和普通簇內節點沒有硬件層次上的區別。僅有的區別只在三種節點在網絡數據傳輸中扮演不同的角色。簇頭負責管理簇和協調簇內的節點工作。網關負責收集簇內的數據并將數據發送到路由路徑上的下一跳的簇的簇頭。簇內普通節點在沒有被簇頭分配網關任務時，執行采集數據的任務，并在指定的時間內把采集到的數據發送到簇內的網關節點。

在基于資源調度的靜態路由算法(SCIRS)中，將傳感器節點劃分為三種不同的網絡角色用于平均網絡傳輸導致的能量消耗。選用簇頭來管理簇內節點和簇內節點之間工作的協調。網關用于和臨近的簇之間通信，由于距離相對于簇內通信較大，所以也是一個能量消耗過大的工作。為了平均這種遠距離通信導致的少數節點能量集中消耗，簇頭使用時間觸發的調度機制將網關的角色較平均的分配給簇內的每一個節點。在保證每一個節點都有機會成為網關節點承擔遠距離通信的同時，簇頭的網關調度機制中也加入了防止剩余能量較低的節點被調度為網關執行遠距離通信任務的機制。所有這些機制都是為了最大可能的將網絡的能量消耗均衡在所有節點上。防止由于少數節點能量消耗及過大，提前失敗從而導致網絡性能惡化。

參考文獻：

[1] Akyildiz I F，Weilian S， Sankarasubramaniam Y，et al. A Survey on Sensor Networks[J]. IEEE Communications Magazine，2002，40(8):102-114.

[2] Jamal N，Ahmed E. Routing Techniques in Wireless Sensor Networks: A Survey[J].IEEE Wireless Communications，2004，11(6):6-28.

[3] HAO F， HUANG B， ZHU H， et al. An Efficient Data Dissemination Scheme for Wireless Sensor Networks[C]. 2006 RISP International Workshop on Nonlinear Circuits and Signal Processing(NCSP 2006). Hawaii，USA，2006.

[4] Heinzelman W R， Chandrakasan A， Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]. Proceedings of the 33rd Hawaii International Conference on System Sciences， Hawaii， USA， 2000.

[5] HUANG B， ZHU H， HAO F， et al. An Energy-Efficient Data Dissemination Scheme for Wireless Home Network[M]. Journal of Signal Processing， 2006.

[6] HUANG B， ZHU H， HAO F， et al. Low-Energy Static Clustering Scheme for Wireless Sensor Network[C]. Wuhan: The 2nd International Conference on Wireless Communications， Networking and Mobile Computing (IEEE Conference WiCOM 2006)， China， 2006.