無線傳感器網絡傳輸調度方法綜述

張曉玲，梁煒，于海斌，封錫盛

(中國科學院 沈陽自動化研究所 工業信息學重點實驗室，遼寧 沈陽 110016)

1 引言

集數據采集、處理、無線傳輸等功能于一體的無線傳感器網絡擴展了人們的信息獲取能力，將邏輯上的信息世界與真實物理世界融合在一起，將會改變人類與物理世界的交互方式[1～3]。1999年的美國商業周刊[4]認為無線傳感器網絡是 21世紀世界最具影響的21項技術之一。2003年的MIT新技術評論[5]認為無線傳感器網絡是改變世界的 10大新技術之一。2009年溫家寶總理倡導“感知中國”，進一步推進無線傳感器網絡的研究。由于無線傳感器網絡技術是應用性非常強的技術，國內在開展這方面的研究工作時需要堅持需求牽引且面向具體應用。目前，針對無線傳感器網絡的研究已由基礎研究轉向了應用研究，例如新興的工業無線傳感器網絡、物聯網、智能電網等。然而，應用的多樣性對于無線傳感器網絡的性能提出了更加苛刻的要求。其中，無線傳感器網絡協議棧中的介質訪問控制(MAC，medium access control)子層負責為相互競爭的節點分配無線通信資源，是關系網絡性能的關鍵技術[2]。目前針對不同的應用，研究人員提出了多種MAC協議，可以按照如下依據進行分類：第一，采用分布式控制還是集中式控制；第二，使用單一共享信道還是多個信道；第三，采用固定分配方式還是隨機訪問方式。根據第三種分類方式，可將MAC協議歸納為以下3類。

1) 采用固定分配方式，為每個傳感器節點分配固定的通信時隙和信道，從而避免節點之間的相互干擾；具體的實現方式包括時分多址(TDMA，time division multiple access)方式、頻分多址(FDMA，frequency division multiple access)方式或者碼分多址(CDMA，code division multiple access)方式。

2) 采用隨機競爭方式，傳感器節點在需要發送數據時隨機占用無線資源，重點考慮盡量減少節點間的沖突和干擾。

3) 混合方式，即固定分配和隨機競爭結合的方法。

目前，對于大多數無線傳感器網絡的應用，如現在典型的工業無線傳感器網絡，固定分配方式是較為理想的解決方案。究其原因在于：首先，無線傳感器網絡對于性能具有確定性要求；其次，為了便于管理，現有無線傳感器網絡的拓撲結構相對固定且常為層次性結構；此外，網絡中的數據大多具有周期性特征。固定分配方式的實現依賴于通信資源的分配。通常的研究方式將如何合理分配通信資源以保障應用需求歸結為傳輸調度問題。

本文正是依托于這樣的背景，對保證網絡性能和用戶需求的傳輸調度技術進行詳細歸納，并總結了研究挑戰和未來的研究工作。

2 傳輸調度問題概述

廣義的傳輸調度問題通常包括6個要素：被調度對象、調度目標、調度算法、調度者、調度方案和調度代價。狹義的傳輸調度問題主要針對 MAC層進行研究。6個要素包括[6]：無線通信資源(時間和信道等)是被調度對象；調度目標通常是網絡吞吐量、數據傳輸的實時性和可靠性、能耗、節點公平性等；調度算法實現對無線通信資源的合理有效分配；調度者可以是網絡中的匯聚節點或者是單個節點；調度方案是經過調度算法控制后，節點收發報文的次序、時間及各種服務質量；調度代價包括計算的復雜度和緩存區的資源占用情況等。其中，調度算法(或稱調度規則、調度機制)是連接其余5個要素的紐帶。通常，為了獲得一個滿意的調度方案，通常需要在調度代價和調度目標之間進行折中，因此，傳輸調度問題往往轉化為多目標優化問題。

傳輸調度問題出現的根源在于節點對有限資源的爭用。無線傳感器網絡中，無線通信資源主要包括時隙和信道。因此，無線傳感器網絡的傳輸調度問題主要包括3個方面的研究內容：時隙分配、信道分配以及時隙和信道二維資源的聯合分配。而在每個方面的研究中，需要在滿足空間約束、順序約束、截止期約束、可靠性約束、能量約束等約束條件[7]的基礎上，解決以下 3個層面的問題。

1) 當網絡中的多個節點之間存在沖突和干擾關系時，為節點分配通信的時隙和信道。

2) 當節點上有多個報文需要發送時，為每個報文分配占用時隙和信道的次序。

3) 優化節點的發射功率，控制節點對網絡的干擾范圍，降低傳輸調度的難度。

綜合考慮無線傳感器網絡的應用特點和系統特性，衡量傳輸調度方法的優劣需要考慮以下幾點。

1) 資源有效利用率：傳輸調度算法需要實現對無線信道的有效利用。當一條鏈路處于比較差的信道狀態時，應盡量避免把當前的時隙分配給這條鏈路，以減少時隙浪費。

2) 延時特性：保證數據在截止期前到達接收方。過期的數據被認為是無效數據。

3) 可靠性：保證數據成功到達接收方，可通過合理分配無線通信資源、增加重傳時隙、自適應跳頻等方法實現。

4) 網絡能耗：決定網絡的工作時間，即網絡壽命。

5) 實現復雜度：復雜度關系到傳輸調度算法的可實現性。雖然微電子技術和專用芯片飛速發展，但是復雜的傳輸調度算法將浪費大量的軟硬件資源，可實現性較差；同時，復雜的傳輸調度算法的計算時間較長，不能迅速地做出決策，在網絡動態性強的環境下實現困難。

6) 可擴展性：節點數量的增加對傳輸調度算法的影響較小。

在實際的傳輸調度算法設計中，需要根據應用場合和應用需求偏好，從上述評價指標中選擇關鍵指標。

3 傳輸調度算法的分類

傳輸調度方法存在多種分類方式。根據可分配信道的數量，分為共享信道傳輸調度和多信道傳輸調度；根據對網絡拓撲的依賴程度，分為拓撲相關和拓撲透明傳輸調度；根據被調度對象，分為節點激活、鏈路激活和混合激活傳輸調度；根據調度者，分為集中式傳輸調度、分布式傳輸調度和集中/分布混合式傳輸調度；根據接收者信息是否已知，分為廣播傳輸調度和單播傳輸調度。下面對各種分類方式予以介紹。

1) 共享信道和多信道傳輸調度

共享信道傳輸調度針對網絡中所有節點共享一條信道的情況，主要完成時隙分配，通常包括節點的時隙分配和節點內部任務的時隙分配2項工作，且這2項工作通常需要聯合考慮。然而，將存在沖突關系的節點分配到不同信道傳輸可以很大程度降低干擾，提高網絡的吞吐量。因此，目前大多數網絡的研究集中于對多信道情況下各種技術的探索。傳輸調度方法進而由共享信道傳輸調度衍生為多信道傳輸調度。多信道傳輸調度主要完成信道的調度以及信道和時隙二維通信資源的調度，同樣也包括節點的分配以及節點內部任務的分配2項工作，且這2項工作通常需要聯合考慮。

2) 拓撲相關和拓撲透明傳輸調度

拓撲相關傳輸調度算法依賴網絡的拓撲信息[8,9]，需要準確掌握網絡的拓撲結構信息；而拓撲透明的傳輸調度算法僅依賴于節點數和節點可能的最大鄰居數2個全局參數，與特定的拓撲結構無關，且不受節點移動性的影響。2類傳輸調度方法相比，拓撲相關傳輸調度方法帶寬利用率高，調度結果逼近最優值，但收集網絡信息的開銷較大，且方法受網絡拓撲結構的影響較大，僅適合于靜態網絡；拓撲透明的傳輸調度方法降低了傳輸調度重新計算和重新分配的代價，適合動態性較強的網絡，但帶寬利用率低于拓撲相關的傳輸調度方法，且網絡延時較大。

3) 節點激活、鏈路激活和混合激活傳輸調度

節點激活傳輸調度是指為網絡中的節點分配通信所需時隙和信道等，適合于高負載的廣播和組播通信；鏈路激活是指為網絡中的每條鏈路分配通信所需資源，適合于低負載的單播通信；混合激活是指為網絡中的節點和鏈路都分配資源，適合于既有廣播通信，也有單播通信的網絡。根據網絡的通信方式，3類傳輸調度方法適用于不同的網絡環境。

4) 集中式、分布式和集中/分布混合式傳輸調度

集中式傳輸調度是指網絡中的中心管理節點負責生成全網各個節點的調度方案，并將生成的調度結果分發給每個節點。分布式傳輸調度是指網絡中的各個節點根據局部信息(如兩跳或者三跳范圍內的鄰居節點)，分布式生成調度決策，或者通過協商生成調度決策。集中/分布混合式傳輸調度是由網絡中的部分節點根據局部信息生成調度方案。集中式的傳輸調度的調度結果可以逼近最優結果，但是網絡信息的收集和調度結果的分發過程會帶來比較大的時間和控制開銷；分布式傳輸調度的決策速度快，但相比集中式傳輸調度最優性較差；集中/分布混合式傳輸調度綜合了集中式和分布式傳輸調度的優點。

5) 廣播傳輸調度和單播傳輸調度

從接收者信息是否已知的角度分類，傳輸調度算法分為廣播傳輸調度和單播傳輸調度。廣播傳輸調度是指不需要知道接收者的信息，采用廣播的方式發送數據；單播傳輸調度是指已知接收者的信息，為每個源-目的節點對分配通信所需資源。從實現的功能看，廣播傳輸調度和單播傳輸調度分別對應于節點激活的傳輸調度和鏈路激活的傳輸調度，同樣對應于不同的通信方式。

4 傳輸調度算法的研究現狀

本節以共享信道傳輸調度和多信道傳輸調度的分類方式為主線，綜合傳輸調度和功率控制聯合設計這一研究熱點，闡述無線傳感器網絡傳輸調度方法的研究現狀。

4.1 共享信道傳輸調度

共享信道傳輸調度主要研究時隙的分配，即為網絡中的每個節點或者每項任務分配傳輸數據所需的時隙。根據調度者分類，共享信道傳輸調度又可分為集中式和分布式傳輸調度。

1) 集中式共享信道傳輸調度

早期的集中式共享信道調度主要面向廣播通信的網絡。在網絡組建以及網絡控制階段，節點通常以廣播方式協調各自的行為。廣播傳輸調度因此引起廣大研究者的關注。廣播傳輸調度問題是NP-完全問題，因而大部分算法采用集中啟發式方法，需要掌握全局信息[10,11]。集中式廣播傳輸調度算法一般采用圖論的方法求解，以最大化時隙利用率或最小化超幀長度的方法來達到提高吞吐量和降低延時的目標。Arunabha和Vuong等人[12,13]通過尋找單個時隙內的最大傳輸集來最大化網絡吞吐量，采用令牌深度優先搜索方法實現集中的啟發式廣播傳輸調度； Wang等人[14]采用神經網絡、模擬退火等算法可以得到近優的廣播調度方案，但算法復雜度高，且需要全局精確信息，工程實用性較差。

Ramanathan[10]將上述針對廣播傳輸的調度方法進行了歸納和擴展，比較了時域、頻域和碼域中傳輸調度約束條件的相似性，首次提出了基于TDMA/FDMA/CDMA統一的傳輸調度架構。該架構基于物理空間上足夠遠的節點可以共享時隙、信道或編碼的思想，致力于實現節點的空間復用。首先，利用圖論的方法將網絡模型搭建為有向圖，且假設鏈路是單向非對稱的。同時，根據被著色對象(節點或鏈路)、沖突關系(節點沖突或鏈路沖突)和傳輸方向(發送者和接收者)，將已有的 114種傳輸調度算法的約束歸納為11個原子約束，包括4個基于節點的約束和7個基于邊的約束。圖1所示的11個原子約束中，(1)～(4)為基于節點的約束，(5)～(11)為基于邊的約束，其中，黑點和實線表示相互受干擾的節點和鏈路，空心點和虛線表示對其他節點和鏈路造成干擾的節點和鏈路。通過調整和限制 11個原子約束的組合方法，可以反映不同情況下的傳輸調度問題，同時作者設計了一個適用于時域、頻域和碼域的傳輸調度算法——UxDMA。

面向單播通信的共享信道傳輸調度往往采用集中式最大權鏈路調度算法[15～20]，選擇無沖突鏈路集合中權值和最大的一組鏈路進行傳輸，目的在于保證網絡吞吐量最大。該類算法以 Huanli等人[15]為代表。Yang等人[19]針對Huanli等人為代表的研究未考慮能耗的問題，提出一種基于最大權鏈路調度的最小能量調度 (MES，minimum energy scheduling)算法。MES算法基于隨機流量模型和時變信道模型，以網絡吞吐量和能耗作為優化指標，該算法可以作為能量受限的無線傳感器網絡協議設計的一個標志性算法。Nicholas等人[20]針對已有算法對于數據傳輸實時性、可靠性、公平性等考慮甚少的問題，提出一種簡單易行且靈活的傳輸調度策略，旨在實現平均延時和公平性的折中。

圖1 統一架構的原子約束

上述方法在考慮干擾時均采用協議干擾模型[21]，即如果節點i正在發送數據，則其鄰居節點不能同時收發其他數據。然而，無線傳輸的范圍不可能絕對抵達某個界限，協議干擾模型是對實際無線環境的簡化，因此無法準確的描述無線干擾情況。理論和實驗表明，節點j可以成功接收到來自節點i的數據的條件[22]是：節點i發往節點j的信號的強度與節點j接收到的所有干擾和噪聲的比值大于一定閾值，即信號-干擾噪聲比(SINR，signal to interference plus noise ratio)大于閾值，如式(1)所示。

其中，Pij表示節點i到節點j的傳輸功率；Gij表示節點i到節點j的信號增益；jη表示節點j上的熱噪聲表示網絡中其他節點對節點j的累加干擾；γ0為用戶自定義的閾值，取決于用于要求的QoS，如比特錯誤率(BER，bit error rate)。Gij通過遠域模型Gij=di-jα表示。其中，dij表示節點i和節點j之間的歐幾里得距離；α∈ [ 2,4]表示路徑損耗因子。如果式(1)不能得到滿足，則節點j無法成功接收到來自節點i的數據。

采用SINR干擾模型會給傳輸調度算法的設計帶來新的挑戰[23]：1) 引入SINR干擾作為約束，導致傳輸調度優化問題成為非凸優化問題，且導致大多數的問題成為NP-難問題，因此傳統的凸規劃技術不再適用于求解該類優化問題，需要另辟新的算法求解次優解；2)SINR的計算比較復雜，需要統計和記錄大量的參數，因此采用SINR干擾模型會帶來較大的計算開銷。然而，采用SINR干擾模型可在理論上和實際中獲得較好的網絡性能。Moscibroda等人[24,25]指出，基于SINR干擾模型的傳輸調度算法能夠提高網絡的整體性能，如降低延時等。目前，基于SINR模型的傳輸調度算法成為新一輪的研究熱點[22,26,27]。Goussevskaia等人[22]首次證明得出：基于SINR模型的傳輸調度問題是NP-完全問題，前提是假設節點分布在平面上。該項研究的另一個重大貢獻在于將NP-完全問題中的一個典型實例“分化問題”[28]在多項式時間內化解為傳輸調度問題，從而為證明其他問題的計算復雜度提供了方法參考，如證明功率控制和傳輸調度聯合問題的復雜度。Brar等人[26]基于SINR模型，提出一種多項式時間的啟發式傳輸調度算法。并給出了節點均勻隨機分布情況下該算法相對于最優算法的近似因數。Bjorklund等人[27]針對傳統同步時分多址（STDMA）調度方法的最優解無法求得，導致啟發式算法的性能不容易衡量的問題，以最小化超幀長度為優化目標，基于SINR干擾模型，利用列生成方法集中求解節點激活傳輸調度和鏈路激活傳輸調度這2個問題。

綜上所述，集中式傳輸調度算法需要中心節點收集全局信息來生成全網調度，其帶寬利用率高，但存在單點故障問題。此外，集中式傳輸調度算法不能很好地適應網絡的動態變化，且需要浪費大量資源交互網絡拓撲的變化信息，在節點快速、頻繁移動時可能導致傳輸調度算法失效，網絡癱瘓[29]。

2) 分布式共享信道傳輸調度

早期針對廣播通信的分布式共享信道傳輸調度方法，通常以最小化超幀長度和最大化時隙利用率為目標[30～34]，且所得超幀長度與網絡規模成正比。其中，最典型的算法包括Funabiki等人[30]提出的一種結合最小化超幀長度和最大化時隙利用率的算法。該算法在最小化超幀長度過程中，首先根據節點的兩跳鄰居數將全網的節點排序，然后依次給每個節點分配一個未被任意一個兩跳鄰居節點使用的最小時隙號。分配完成后，最大時隙號就是該網的最小超幀長度。在最大化時隙利用率過程中，按照相同規則為全網節點排序，依次為各節點分配最小時隙號，且允許節點使用多個未被兩跳鄰居節點使用的時隙。

為了適應網絡的動態性、降低傳輸調度重新計算帶來的協議開銷，Chlamtac等人[35]面向單播通信，提出一種不依賴網絡拓撲結構、僅依賴全局網絡參數(最大節點數和節點的最大鄰居數)的分布式傳輸調度方法，即拓撲透明傳輸調度方法。Chalamtac等人利用高斯域原理進行求解，保證網絡中的每個節點在一個超幀周期內至少成功傳輸一次，且根據節點的流量要求動態增加節點的時隙數。然而，文中并沒有對算法進行優化，算法的性能較差。基于Chalamtac等人的思想，Ju等人[36]以最大-最小吞吐量為優化目標，利用編碼理論提出一種新的拓撲透明的傳輸調度解決方案。該方案不需要額外的控制參數，僅需要預估的節點數和最大鄰居數作為參數。該算法在吞吐量和延時這2個方面的性能優于Chalamtac等人提出的算法。但算法的性能取決于節點數和鄰居數的估計精度，因此算法的頑健性得不到保證。李衛等人[37]在螺紋協議T-TSMA[38,39]的基礎上，提出一種根據當前網絡拓撲和負載量，有效利用節點已分配和未分配時隙進行報文傳輸的調度方案(TTHM，topology transparent hybrid MAC protocol)。該算法不受最大節點密度的限制，便于分布式應用。

為了滿足用戶對QoS的要求，研究者們于80年代初開始研究基于預約的傳輸調度方法，即采用分布式競爭接入和預約調度結合發送數據的方法。基于預約的傳輸調度方法的主要目標是最大化網絡壽命和協議的可擴展性，以及要求協議適應網絡的變化。這些變化主要包括網絡規模、拓撲、節點密度、節點加入和離開等。其他網絡性能，如吞吐量、延時、可靠性和帶寬利用率也是需要考慮的指標。典型的解決方案可以歸納為2類：基于控制信道預約的方法和基于控制時隙預約的方法。其中，基于控制信道預約的方法將信道劃分為控制信道和數據傳輸信道；基于控制時隙預約的方法將時隙劃分為控制時隙(或稱預留時隙)和數據傳輸時隙。上述2類方法中，節點利用控制信道或者控制時隙預約數據傳輸所需的時隙，并利用預約成功的時隙進行數據傳輸。

基于控制信道和數據傳輸信道的方法中，控制信道用于節點交換傳輸調度請求、預約數據傳輸所需時隙以及解決隱藏終端和暴露終端沖突問題；數據傳輸信道用于節點傳輸數據。典型的研究包括IBM 托馬斯?沃森研究中心的 Cidon等人[8]于 1989年提出的分布式動態傳輸調度算法。該算法給出了該類傳輸調度的基本控制架構，主要解決多跳傳輸且網絡動態性較強情況下的時隙分配問題。算法的基本思想是將信道劃分為控制信道和數據傳輸信道。網絡中的每個節點根據一跳的鄰居信息分布式執行時隙分配算法。同時，針對控制開銷不容忽視且固定優先級導致的不公平分配等缺陷，作者提出了優先級輪詢算法和鄰居等待算法。其中，優先級輪詢算法在每個時隙開始，動態更換節點的優先級，保證網絡中的每個節點在每個傳輸調度周期內都有機會傳輸數據；鄰居等待算法在一個調度周期內，要求已分配時隙的節點等待其鄰居節點全部被調度完成后，才可以再次參與分配過程，通過減少每個時隙的控制開銷以降低整體控制開銷。

Zhu等人[9]提出的 5階段預留協議(FPRP，five-phase reservation protocol)適用于規模較大且節點動態性較強的網絡。FPRP方法是一種通過5次握手，完成兩跳范圍內高概率、無沖突的分布式預約的廣播傳輸調度機制。FPRP方法中的超幀結構如圖2所示，該超幀結構與D-TDMA[40]方法所設計的超幀結構相似。Zhu等人[41]提出的E-TDMA算法是FPRP算法的改進版本，可以保證實時業務無沖突的發送，同時也能避免延時抖動，但控制開銷較大、實現復雜且效率不高。電子科技大學通信抗干擾技術國家級重點實驗室的郭偉等人[42]受文獻[9]和文獻[41]的啟發，結合無線傳感器網絡的能量約束，提出了一種基于預約調度的 MAC協議——SSMAC。一方面解決了隱藏終端和暴露終端問題；另一方面在考慮節能的同時，降低了節點的接入延時，提高了報文的傳輸成功率且保證了延時、延時抖動、可用帶寬和分組丟失率等 QoS指標。Phua等人[43]針對工業無線傳感器網絡中干擾周期性變化的特點，提出一種基于鏈路狀態的傳輸調度(LSDS，link state dependent scheduling) 協議，其超幀結構如圖3所示。LSDS協議只將信道的質量簡單標記為“好”和“壞”，不能準確反映信道的實際質量。該算法雖然適用于干擾和衰減呈周期性變化的網絡，但以隨機方式建立調度使得其不適用于實時性、可靠性等要求較高的場合。

目前，部分學者對于匯聚傳輸的調度問題提出了分布式解決方案。Gandham等人[44]給出了對于節點數據為N的網絡，通過傳輸調度最多只需要3N個時隙就能完成一次全網數據的匯聚傳輸，并提出了相應的算法。該算法雖然由各個節點自主決定傳輸時隙的分配，但是每個節點需要掌握網絡拓撲中的分支總數、各分支長度、節點和各分支之間的傳輸干擾關系等多種信息，在計算復雜度上已經接近于集中式傳輸調度。孫利民等人[45]針對無線傳感器網絡匯聚傳輸的實時性，提出一種基于 TDMA的分布式節點調度算法。利用該算法進行一次全網數據收集，基本可以在 1.6～1.8倍網絡節點數個時隙內完成，并且能夠有效避免各節點之間的數據碰撞。另外，該算法調度時只需要各節點掌握一跳鄰居信息，而在傳輸過程中節點最多只要緩存2個報文，因此滿足無線傳感器網絡分布式、節點存儲空間受限的要求。該算法在實時性和復雜度方面更具優勢，但對網絡局部區域突發性信息傳輸的實時性支持不夠，也無法為多種不同級別的數據傳輸提供不同的實時性保證。

圖2 FPRP和E-TDMA超幀結構

圖3 LSDS超幀結構

Yi等人[46]提出的一系列考慮SINR模型的分布式動態隨機調度 (DRS，dynamic randomized scheduling)算法。DRS首次嘗試分布式求解基于SINR模型的傳輸調度問題。該類算法以最大化吞吐量為優化目標，不需要知道節點的位置信息，控制開銷較小，可以較好地適應網絡拓撲和負載的動態性，但算法計算復雜度高，不適合應用于規模較大的網絡。

綜上所述，分布式共享信道傳輸調度算法不需要收集全局的網絡信息，克服了算法受網絡規模限制的缺陷，網絡動態適應性較好，但控制開銷較大、實現復雜、最優性相比集中式較差。

4.2 多信道傳輸調度

Kyasanur等人[47]指出采用多個信道傳輸可以有效避免沖突。圖5和圖6所示分別為單信道和多信道情況下的干擾問題。圖4中，節點3有數據收發時，干擾同一路徑上的節點1，2，4，5，8以及路徑2上的節點9和節點10。采用多信道后，干擾范圍內的節點通過采用其他信道進行傳輸，從而在一定程度上避免了干擾。圖5中，節點3和節點4利用1號信道傳輸時，節點1，2，5，8，9，10可同時利用其他信道進行傳輸，最大程度實現了并行傳輸。

Shin等人[48]證明了最優的多信道傳輸調度是NP-難問題，且歸納出多信道傳輸調度的一般解決方案是在滿足接口約束和信道約束的條件下，為節點分配盡可能多的信道。目前多信道傳輸調度的研究內容主要包括2個方面：信道調度以及時隙和信道聯合調度。信道調度主要研究如何為網絡中的節點分配通信所需信道。目前存在2類方法：動態信道分配法和半靜態信道分配法。其中，動態信道分配法要求節點頻繁改變通信所用的信道，如為每條鏈路分配信道且每發送1次數據改變1個信道。這種多信道調度方法要求快速的信道切換速度，而現有的硬件技術中信道切換時延為毫秒級，因此無法滿足實時切換的要求。半靜態信道分配法是根據負載量和網絡拓撲的顯著變化而改變信道。因此在網絡環境和負載量相對穩定的條件下，信道切換不頻繁。信道和時隙聯合調度主要研究如何為網絡中的節點分配通信所需的時隙和信道，目前這方面的研究比較初步。

圖4 單信道無線傳感器網絡路徑內和路徑之間的干擾

圖5 多信道無線傳感器網絡路徑內和路徑之間的干擾

下面以調度者為分類依據，總結多信道傳輸調度的研究現狀。

1) 集中式多信道傳輸調度

針對圖著色算法無法滿足多信道調度中的接口約束、信道約束、網絡連通約束和帶寬約束，Raniwala等人[49]以最大化網絡總吞吐量為優化目標，以信道數量、接口數量、網絡連通要求和流量限制為約束條件，提出基于網絡負載量變化的多信道啟發式調度 (LACA，load-aware channel assignment)方法。LACA算法以預估的網絡負載量的期望值為輸入，將具有沖突關系的鏈路分組后，采用迭代方法按序為網絡中的每個節點分配通信所需信道。該算法將單信道的IEEE 802.11標準擴展到多信道的應用場合，采用集中式的求解方法，且要求網絡拓撲固定不變。但由于LACA算法側重于滿足流量約束，在迭代過程中僅以流量為反饋量修正信道調度結果，因此算法可行性方面考慮欠缺。

Das等人[50]以最大化并行傳輸的鏈路數為目標，以干擾、信道數和接口數為約束條件，提出 2個面向靜態多信道調度問題的混合整數線性規劃模型，但是并未給出可實現的多項式時間算法。Soldati和 Zhang等人[51～53]基于無線 HART標準，基于線型路由和樹型路由下完成匯聚傳輸所需時隙數和信道數的理論下限值，提出一種時隙和信道聯合分配的傳輸調度算法。

綜上所述，集中式多信道傳輸調度算法需要收集全局網絡信息，與集中式共享信道傳輸調度算法相似，也存在單點故障問題。

2) 分布式多信道傳輸調度

目前，大部分學者的研究集中于分布式多信道傳輸調度算法。分布式多信道傳輸調度算法大多數采用提前預留資源的方法。與分布式共享信道傳輸調度算法相比，這類方法將預留的資源擴展為時隙和信道。Nasipuri等人[54]提出一種基于CSMA的軟信道預留算法。該算法由節點分布式執行，并要求節點同時可以偵聽所有信道上的數據傳輸情況。當節點有數據需要發送時，從空閑信道中選擇上次傳輸成功的信道進行傳輸。之后，Nasipuri等人[55]又改進了空閑信道選擇方法，將發送端信道強度最大的信道作為最佳選擇。該算法在網絡吞吐量方面具有很好的性能，但由于要求每個節點上安裝多個收發器，因此硬件成本太大。

Wu等人[56]將收發器的數量減為2個，提出了一種按需動態信道調度算法DCA。DCA算法中，網絡中的信道被劃為控制信道和數據信道。每個節點的2個收發器可以同時偵聽到來自控制信道和數據信道的數據。節點之間通過RTS/CTS握手方式交互通信所需信道。由于節點的一個收發器始終偵聽控制信道上的數據，因此，DCA算法不存在多信道隱藏終端。同時，DCA算法不需要精確同步，控制開銷較小。但由于該算法采用專用信道進行協商，因此對于網絡信道數較少的應用場合，控制開銷較大；其次，對于可用信道數較多的應用場合，單條控制信道又會成為信道協商的瓶頸，導致無法充分利用數據信道。Jain等人[57]在DCA算法的基礎上，改進了目的端節點選擇信道的方法，選擇質量最好的信道作為數據信道。但改進的 DCA算法仍然未解決DCA算法的缺陷。

So等人[58]針對上述算法中存在的硬件成本大、控制開銷高和多信道隱藏終端問題，面向單收發器的節點，以時間為代價實現多信道傳輸調度的協商過程。在算法開始階段，網絡中的所有節點在規定的時間內采用統一信道進行協商，這一時間段稱為信道協商階段。信道協商階段后，收發雙方按照預先協商好的信道進行通信。該算法需要精確地全網時間同步以克服多信道隱藏終端問題；同時，由于采用單收發器，因此硬件成本小。但由于該算法需要另辟一段時間用于信道協商，因此在克服控制信道所需開銷的同時，引入了新的時間開銷，不適合實時性要求較高的應用場合。Ko等人[59]在探討信道調度策略前，致力于達到3個方面的目標：1)僅依賴局部信息作出信道調度決策；2)信道調度策略基于網絡的物理結構，而非動態的網絡信息；3)信道調度的結果不應該頻繁改變網絡的連接狀態，可為端到端的路由提供較為穩定的網絡環境。基于上述目標，提出了一個分布式的輕型信道調度策略。該策略由節點分布式執行，以最小化局部干擾總和為目標，僅依賴節點的局部信息，采用貪婪算法進行求解，實現了網絡連通性和信道多樣性的折中。實驗表明，該算法執行時間短且網絡容量高，但未考慮接口數量對于信道調度的影響。

目前，針對無線傳感器網絡的時隙和信道聯合調度的研究比較少見，典型的研究包括MMSN[60]、MCMAC[61]、Y-MAC[62]和 TFMAC[63]等。

Zhou等人[60]首次面向無線傳感器網絡提出一種多信道MAC協議(MMSN，multi-frequency MAC for wireless sensor networks)。MMSN算法充分考慮了無線傳感器網絡的以下2個特點：出于能耗和成本考慮，傳感器節點僅安裝一個收發器，因此節點不能同時收發數據且不能同時工作在多個頻段；無線傳感器網絡中的報文長度較短，因此傳統方法中基于 RTS/CTS交互的通信方式帶來的控制開銷不容忽視。MMSN算法由信道分配和介質訪問2個階段組成。在信道分配階段，節點分布式協商信道的分配且以廣播方式通知鄰居節點。MMSN算法在降低能耗和提高節點并行傳輸等方面性能突出，但其屬于靜態分配方法，不適用于網絡環境動態變化的場合。為了克服靜態分配不靈活的缺陷，Chen等人[61]為節點動態分配多個信道，并考慮分簇網絡的信道和時隙聯合調度，提出一種基于協調者的多信道MAC協議MCMAC。MCMAC算法將N個信道分為1個控制信道和(N-1)個數據傳輸信道，并擴展了IEEE 802.15.4的超幀結構，如圖6所示。MCMAC算法在提高網絡能效性、網絡壽命方面可以獲得較好的性能。但由于超幀的活動期階段大部分時間用于簇成員請求信道分配，因此，控制開銷比較大，影響網絡吞吐量。

Kim等人[62]針對傳統能量有效的多信道調度算法以犧牲吞吐量為代價的問題，提出一種能量有效的多信道輕型傳輸調度算法 Y-MAC，旨在解決網絡中突發數據的傳輸問題。Y-MAC算法要求節點局部協調時隙的分配，是一個面向接收者的調度方法。Y-MAC算法避免了節點偵聽信道的能耗，可以有效處理突發數據的傳輸；同時，采用多信道傳輸機制提高了數據傳輸的成功率且降低了延時。Jovanovic等人[63]以提高網絡吞吐量為目的，提出一種分布式時隙和信道聯合調度算法(TFMAC，time frequency MAC)。TFMAC算法中的超幀包括2個階段：競爭階段和非競爭階段。其中，競爭階段由控制時隙組成，用于節點收集鄰居節點的時隙和信道分配結果，隨機選擇多個空閑時隙和一個接收信道，并廣播自身的選擇結果。非競爭階段用于節點在指定的時隙和信道上進行通信。TFMAC算法中，每個節點的發送時隙數等于網絡中的信道數。該算法可以最大限度地提高網絡中節點的并行傳輸，提高網絡吞吐量，但無法避免時隙和信道選擇過程中的沖突問題，因此對于規模較大的網絡效率比較低；同時，TFMAC算法為每個節點在每條信道上分配時隙，對于負載量較輕的應用，資源浪費嚴重。

綜上所述，分布式多信道傳輸調度采用固定分配方式則靈活性不夠，采用動態分配方式則控制開銷較大、效率較低。

3) 集中/分布混合式多信道傳輸調度

由于傳統的動態信道調度方法會改變網絡的初始拓撲結構，影響網絡其他方面的設計，如路由等，導致全網調度低效。為了克服上述問題，Subramanian和Gupta等人[64]在滿足接口約束的前提下，以最小化網絡干擾度為優化目標，采用半正定規劃法求解該優化問題。將網絡構造為沖突圖，首次求取了網絡干擾度的下限值。同時，以網絡干擾和流量模型為輸入，分別設計了集中式和分布式的啟發式算法來逼近下限值。所提算法的優勢在于提高了網絡吞吐量、不影響路由決策、易于實現以及適用于正交信道和非正交信道的分配。

圖6 IEEE 802.15.4和MAMAC的超幀比較

Martin等人[65]針對網絡中信道數量受限的情況，提出一種分簇的信道調度方法(CCA，cluster channel assignment)，目的在于實現信道在多個簇之間的復用、最大化網絡平均吞吐量以及最小化干擾。該方法是集中式和分布式結合的動態、按需的信道調度方法。CCA方法的優勢在于：將信道分配的難度分散到每個簇內，易于執行；允許使用網絡中的空閑信道，可以有效利用帶寬且避免干擾；允許簇首自主調整本簇的信道分配，靈活性更強，且可以有效克服干擾等時空特性。

Nikolaidis等人[66]考慮無線傳感器網絡中的匯聚傳輸，通過構建樹階段和調度階段實現調度。作者證明了所需調度長度的下限值，并基于該值利用二偶圖的半匹配方法構建樹，最后綜合節點的權重和干擾約束等，采用基于排列的方法為網絡中的每個節點分配通信資源。

針對我國新進頒布實施的工業無線網絡標準WIA-PA，部分學者給出了集中和分布式結合的 2階段資源調度方法[67,68]。該類方法面向網絡-星型的混合拓撲結構，針對簇內和簇間的通信，采用搜索算法，分別為網絡中簇內和簇間的不同設備分配信道和時隙資源。

綜上所述，現有的多信道傳輸調度算法分配方式固定，開銷較大，沒有充分考慮無線環境的時變特性，對可靠性和實時性考慮也較少，因此不適合應用于環境復雜多變的無線網絡中，特別是工業無線傳感器網絡。

4.3 傳輸調度和功率控制的聯合

功率控制被用于動態調整發送節點的功率，不僅能夠有效減少通信中的能量消耗，延長無線傳感器網絡的壽命，同時對于網絡的拓撲控制與連通性、吞吐量、消息傳遞的實時性等系統性能具有顯著的影響，而且可以通過MAC層或跨層協議的設計，優化網絡性能，為提升QoS提供有效途徑[69]。根據控制范圍，功率控制方法包括：網絡級控制、鄰居節點級控制和獨立節點級控制[69]。其中，網絡級功率控制是指網絡中所有節點均使用統一的優化功率值發送數據；鄰居節點級功率控制是指每個節點均使用可覆蓋其所有鄰居節點的功率值發送數據，而節點之間的發射功率值并不相同；獨立節點級功率控制是指發送節點可以針對每個單一的目的節點，自適應調整發射功率水平。

傳輸調度和功率控制的聯合研究，大致包括 3個方面。1)功率控制-傳輸調度法。首先從上述3種功率控制方法中選擇其一，確定節點的發射功率，從而確定網絡的干擾范圍和連通性后。研究傳輸調度算法；2)傳輸調度-功率控制法。首先按照一定的干擾模型，如協議干擾模型和SINR干擾模型等，確定傳輸調度方案，隨后根據源-目的節點關系，調節節點的發射功率；3)傳輸調度和功率控制的聯合研究。研究發現，將傳輸調度與功率控制獨立研究的效率較低[70]。這主要是功率調節會引起節點發送范圍的改變，從而引起周圍信道容量的改變。為了提高傳輸調度和功率調節的效率，一些學者將二者的聯合問題等價為一個高復雜性的非凸最優解問題，進行了研究。該類研究給出的一些調度算法是初步的，僅適用于小型網絡的應用。

ElBatt和Ephremides[71]以提高單跳吞吐量和延長網絡壽命為目的，首次針對傳輸調度和功率控制的聯合問題進行了研究，并采用傳輸調度和功率控制交互的方式求解該聯合問題。Lu等人[72]提出一種基于SINR干擾模型的能量高效傳輸調度和功率控制聯合算法，屬于上述的傳輸調度-功率控制法之列。首先將傳輸調度和功率控制的聯合問題形式化為一個考慮能量、吞吐量和延時折中的優化問題TJSPC；隨后，設計了2個指數時間和多項式時間的貪婪算法求解TJSPC問題；最后，在保證所有報文截止期約束的條件下，研究了以最小化能耗為目的的傳輸調度和功率控制聯合問題。該算法針對靜態單信道無線網絡，因此不適合于動態場合，且所給優化模型無法有效擴展到多信道的應用場合中。Wang等人[73]提出一種適合于組播的傳輸調度和功率控制聯合算法。該算法以功率控制為主，基于SINR模型，以最小化傳輸功率為優化目標，利用線性規劃方法尋求功率最優值；如果搜索不到功率最優值，則調用傳輸調度和功率控制聯合算法，利用傳輸調度最大限度降低干擾后，重新執行功率控制算法。該算法由節點分布式執行，依賴局部信息，屬于一個次優算法。Moscibroda等人[74,75]分析了利用啟發算法求解傳輸調度和功率控制聯合問題在最壞情況下所需時隙的上限值，而沒有給出與最優結果的逼近程度。針對上述問題，Fu等人[76]研究了SINR干擾模型下的最小超幀長度傳輸調度和功率控制聯合問題，首次證明了SINR干擾模型下的最小超幀長度傳輸調度和功率控制聯合問題是NP-完全問題，并提出一個多項式時間的集中式近似算法——保障貪婪算法GGS。同時，給出了GGS算法所求結果與最優結果的逼近度，并分析得出 GGS算法可適合于任何網絡拓撲結構。然而，在一些網絡環境中，GGS算法的最優性往往會松弛。因此，尋找緊界且分布式的算法是未來的一個研究挑戰。

表1 典型傳輸調度算法的特點比較

5 傳輸調度算法的分析和比較

由于無線傳感器網絡中節點的構成、應用場景、用戶需求等不盡相同，故傳輸調度算法具有多樣性的特點，使得算法優劣的比較具有較大難度。表1使用本文的分類方法對上述重點介紹的傳輸調度算法進行了詳細的比較。在實際應用中，應當根據網絡的特點和用戶的要求選擇合適的傳輸調度算法。具體采用何種方法，主要根據具體的網絡環境和用戶需求而定，同時考慮網絡結構、實現難度和部署成本等因素，并在諸多因素之間作出選擇和折中。

6 結束語

如前所述，傳輸調度因其在保障網絡性能和有效避免干擾等方面展現出的巨大潛力，正吸引著越來越多學者的關注。研究人員針對無線傳感器網絡的應用需求和新特征進行了大量卓有成效的研究，新的傳輸調度方法層出不窮。但由于各種傳輸調度方法關注的網絡特性、優化的性能指標、采取的技術手段和面向的具體應用各不相同，因而實際效果千差萬別。事實上，無線傳感器網絡的傳輸調度方法研究的趨勢并沒有呈現收斂性，也無法形成標準。究其原因：首先，傳輸調度方法不可避免的受到物理硬件平臺和物理層協議的影響，而目前作為協議棧底層基礎架構的物理層仍缺乏統一的標準；其次，無線傳感器網絡與應用高度相關，應用差異性使得傳輸調度方法無法兼顧所有的網絡特性，只能在多個性能指標之間做出選擇和折中。鑒于無線傳感器網絡對于應用相關的要求(主要為實時性和可靠性)更加嚴格，使得現階段的研究工作在調度建模、約束滿足、調度方法、容限分析、測試和驗證等方面還存在很多需待解決的問題。下面予以概況，供今后研究參考。

1) 調度建模問題

建模是對實際問題的抽象和簡化，是調度算法設計和分析的基礎。無線傳感器網絡的傳輸調度問題具有復雜動態、多目標、多約束等特點，需要重點解決考慮多種因素、綜合多種指標的傳輸調度建模問題。而針對目前無線傳感器網絡的應用特點，傳輸調度的約束主要由點到點單跳傳輸間的順序關系、報文截止期、單跳成功率、與位置相關的信道占用以及能量等約束構成；傳輸調度的目標主要由資源利用率、截止期、能耗以及各目標的均衡構成。同時，無線傳感器網絡的應用環境，特別是工業應用環境，存在不確定因素：環境干擾嚴重、溫度變化范圍大(一般從-45℃～80℃)；高濕度、高震動以及頻繁移動的人員和設備，使得信道的狀態和容量會隨著時間、位置和頻率而變化；節點加入、離開和失效等導致網絡拓撲結構和路由等也具有動態性。種種因素對傳輸調度的精確建模提出了更高的實用性和靈活性要求，增加了調度建模的難度。因此，需要對具有動態適應性、復雜時空約束和多目標的傳輸調度問題進行精確建模。

2) 約束滿足問題

目前無線傳感器網絡對報文截止期和成功傳輸率的要求更加苛刻。在網絡動態性強、信道時空變化頻繁等前提下，如何將端到端的截止期約束和成功傳輸率約束轉化為傳輸調度算法所能處理的單跳約束，是需要下一步解決的問題。而目前的傳輸調度方法對這2個約束考慮較少，致使現有研究成果無法直接應用。

3) 調度方法問題

大規模網絡、周期性任務等特點，使得問題的求解面臨著組合爆炸問題；大規模、分布式等特點，使得集中式算法無法滿足應用，而分布式局部調度算法又面臨著無法保證確定性要求和全局最優的困擾。非周期性任務、信道狀態的動態變化、拓撲結構和路由的改變等不確定性因素，對傳輸調度方法提出了更高的自適應要求。現有的集中式傳輸調度方法，存在單點故障問題且開銷較大，而分布式傳輸調度方法僅限于小規模網絡的應用。此外，現有的傳輸調度方法分配方式固定，主要面向周期性任務，而且對網絡的動態性考慮較少。因此，需要研究適用于大規模網絡的、分布式優化的、適應網絡動態性的、快速和輕型的傳輸調度方法。

4) 容限分析問題

網絡容量和所需通信資源上下限，是評價傳輸調度算法優劣的關鍵指標。現有的研究主要針對Ad hoc網絡以及網狀結構的無線傳感器網絡進行分析，且不考慮底層協議對于網絡容量的影響，從而導致分析結果過于理想。因此，需要研究考慮底層協議，特別是傳輸調度協議下的網絡容量，為后續底層協議的設計和優化提供理論依據。

5) 測試和驗證問題

無線傳感器網絡在工業中的應用才剛剛起步，現有的研究還主要采用仿真驗證和小規模實驗驗證，缺乏完善的實驗平臺和驗證體系。需要設計和開發實驗平臺，建立評價體系，以對研究成果進行有效地驗證。

綜上所述，面向無線傳感器網絡的傳輸調度問題，是具有明確應用背景和相當研究難度的問題，已有的傳輸調度理論和方法還不能滿足實際問題的需求，尤其是目前對于可靠傳輸調度的研究仍然是一個空白。另一方面，在傳輸調度理論已經取得重要進展的前提下，針對新領域、發掘新問題，面向實際拓展研究的深度和廣度，是傳輸調度理論研究的重要方向。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y,et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4):393-422.

[2] 孫利民,李建中.無線傳感器網絡[M].北京:清華大學出版社,2005.SUN L M, LI J Z. Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.

[3] ESTRIN D, GOVINDAN R, HEIDEMANN J. Next century challenges: scalable coordination in sensor networks[A]. Proc of ACM MOBICOM[C]. Seattie, USA, 1999. 263-270.

[4] 谷有臣,孔英,陳若輝.傳感器技術的發展和趨勢綜述[J].物理實驗,2002, 22(12): 40-42.GU Y C, KONG Y, CHENG R H. Development and trend of sensor technology[J]. Physics Experimentation, 2002, 22(12): 40-42.

[5] WEISER M. The computer for the twenty-first century[J]. Scientific American, 1991, 265(3): 94-104.

[6] 田乃碩,徐秀麗,馬占友.離散時間排隊論[M].北京:科學出版社, 2008.TIAN N S, XU X L, MA Z Y. Discrete Time Queuing Theory[M].Beijing: Science Press, 2008.

[7] STANKOVIC J A. Research challenges for wireless sensor networks[J]. SIGBED Review: Special Issue on Embedded Sensor Networks and Wireless Computing, 2004, 1(2): 9-12.

[8] CIDON I, SIDI M. Distributed assignment algorithms for multihop packet radio networks[J]. IEEE Transactions on Computers, 1989,38(10): 1353-1361.

[9] ZHU C, CORSON M S. A five-phase reservation protocol (FPRP) for mobile ad hoc networks[A]. Proc of IEEE Conference on Computer Communications (INFOCOM)[C]. San Francisco,USA,1998. 322-331.[10] RAMANATHAN R. A unified framework and algorithm for channel assignment in wireless networks[J]. Wireless Networks, 1999, 5(2):81-94.

[11] RAMANATHAN S, LLOYD E L. Scheduling algorithm for multihop radio networks[J]. IEEE/ACM Transactions on Networking, 1993,1(2): 166-177.

[12] ARUNABHA S, JEFFRY M C. Scheduling in packet radio networks -a new approach[A]. Proc of IEEE GLOBECOM[C]. Rio de Janeiro,Brazil, 1999. 650-654.

[13] VUONG T H P, HUYNH D T. Adapting broadcasting sets to topology changes in packet radio networks[A]. Proc of the 8th International Conference on Computer Communications and Networks (IC3N 1999)[C]. Boston, USA,1999. 263-268.

[14] WANG G, ANSARI N. Optimal broadcast scheduling in packet radio networks using meanfield annealing[J]. IEEE JSAC, 1997, 15(2):250-260.

[15] HUANLI P S, RAMAMRITHAM K. Scheduling messages with deadlines in multi-hop real-time sensor networks[A]. Proc of IEEE Real Time and Embedded Technology and Applications Symposium[C].San Francisco, USA, 2005. 415-425.

[16] HAJEK B, SASAKI G. Link scheduling in polynomial time[J]. IEEE Transactions on Informatic Theory, 1988, 34(5): 910-917.

[17] YI Y, PROUTIERE A, CHIANG M. Complexity in wireless scheduling: impact and tradeoffs[A]. Proc of 9th ACM MOBIHOC[C]. Hong Kong, China, 2008. 33-42.

[18] WARRIER S, JANAKIRAMAN, RHEE I. Diffq: practical differential backlog congestion control for wireless networks[A]. Proc of IEEE INFOCOM[C]. Rio de Janeirio, Brazil, 2009. 1-9.

[19] YANG S, ZHANG C, FANG Y G. Minimum energy scheduling in multi-hop wireless networks with retransmissions[J]. IEEE Transactions on Wireless Communications, 2010, 9(1): 348-355.

[20] ADITYA D, NICHOLAS B. On the fairness delay trade-off in wireless packet scheduling[A]. Proc of IEEE GLOBECOM[C]. St Louis,USA, 2005. 2544-2548.

[21] GUPTA P, KUMAR P R. The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000, 46(2): 388-404.

[22] GOUSSEVSKAIS O, OSWALD Y A, WATTENHOFER R. Complexity in geometric SINR[A]. Proc of ACM MOBIHOC’09[C]. Louisiana, USA, 2009. 100-109.

[23] CHAFEKAR D, KUMAR V S A, MARATHE M V. Cross-layer latency minimization in wireless networks with SINR constraints[A].Proc 8th ACM MOBICOM[C]. Montreal,Canada, 2007. 110-119.

[24] MOSCIBRODA T, WATTENHOFER R, WEBER Y. Topology control meets SINR: the scheduling complexity of arbitrary topologies[A].Proc of ACM MOBIHOC[C]. Florence, Italy, 2006. 310-321.

[25] MOSCIBRODA T, WATTENHOFER R. The complexity of connectivity in wireless networks[A]. Proc of IEEE INFORCOM[C]. Barcelona, Spain, 2006. 1-13.

[26] BRAR G, BLOUGH DM, SANTI P. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks[A]. Proc of ACM MOBICOM[C].Los Angeles, USA, 2006. 2-13.

[27] BJORKLUND P, VARBRAND P, YUAN D. A column generation method for spatial TDMA scheduling in ad hoc networks[J]. Ad Hoc Network, 2004, 2(4): 405-418.

[28] KARP R M. Reducibility among combinatorial problems[A]. Proceedings of Symposium on the Complexity of Computer Computations[C]. New York, USA, 1972. 85-103.

[29] 呂俊,于全,汪李峰.移動Ad Hoc網絡中基于TDMA的媒體訪問控制技術[J].現代通信技術,2004,17(3):13-19.LU J, YU Q, WANG L F. TDMA medium access control technology in mobile ad hoc network[J]. Modern Communication Technology,2004, 17(3):13-19.

[30] FUNABIKI N, TAKEFUJI Y. A parallel algorithm for broadcast scheduling problem in packet radio networks[J]. IEEE Transactions on Communications, 1993, 41(6): 828-831.

[31] POST M, KERSHENBAUM A, SARACHIK P. A distributed evolutionary algorithm for reorganizing network communications[A]. Proceedings of MILCOM’85[C]. Boston, USA, 1985. 133-139.

[32] POND L C, LI V O K. A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks[A]. Proc of IEEE MILCOM’89[C]. Boston, USA, 1989. 70-74.

[33] RAMASWAMI R, PARHI K K. Distributed scheduling of broadcast in a radio network[A]. Proc of IEEE INFORCOM’89[C]. Ottawa,Canada, 1989. 497-504.

[34] EPHREMIDES A, TRUONG T. Scheduling broadcasts in multihop radio networks[J]. IEEE Transactions on Communications, 1990,38(4): 456-460.

[35] CHLAMTAC I, FARAGO A. Making transmission schedules immune to topology changes in multi-hop packet radio networks[J].IEEE/ACM Transactions on Networking, 1994, 2(1): 23-29.

[36] JU J H, VICTOR O K, L I. An optimal topology-transparent schedul-ing method in multihop packet radio networks[J]. IEEE/ACM Transactions on Networking, 1998, 6(3): 298-306.

[37] 李衛,王杉,魏急波. Ad hoc網絡中基于拓撲透明特性的混合 MAC協議[J]. 軟件學報, 2009, 20(6): 1642-1650.LI W, WANG S, WEI J B. Topology-transparent hybrid MAC protocol for ad hoc networks[J]. Journal of Software, 2009, 20(6):1642-1650.

[38] CHLAMTA I, FARAGO A, ZHANG H. Time-spread multiple-access(TSMA) protocols for multihop mobile radio networks[J]. IEEE/ACM Transactions on Networking, 1997, 5(6): 804-817.

[39] KRISHNAN R, STERBENZ J P G. An Evaluation of the TSMA Protocol as a Control Channel Mechanism in MMWN[R]. BBN Technical Report, 2000.

[40] JOSEPH K, WILSON N D, GANESH R,et al. Packet CDMA versus dynamic TDMA for multiple access in an integrated voice/data PCN[J]. IEEE JSAC, 1993, 11(6): 870-884.

[41] ZHU C X, CORSONMS M C. An Evolutionary-TDMA Scheduling Protocol (E-TDMA) for Mobile Ad Hoc Networks[R]. ISR Technical Report, 2001.

[42] 楊雙懋,郭偉.基于預約調度的無線傳感器網絡的MAC協議[J].計算機應用研究, 2008, 25(3):855-859.YANG S M, GUO W. Schedule-based sensor MAC protocol in wireless sensor network[J]. Application Research of Computers, 2008,25(3): 855-859.

[43] PHUA V, DATTA A, CARDELL-OLIVER R. A TDMA-based MAC procotol for industrial wireless sensor network applications using link state dependent scheduling[A]. IEEE GLOBECOM '06[C]. San Francisco, USA, 2006. 1-6.

[44] GANDHAM S, ZHANG Y, HUANG Q F. Distributed minimal time convergecast scheduling in wireless sensor networks[A]. Proc of the 26the International Conference on Distributed Computing Systems(ICDCS)[C]. Lisboa, Portugal, 2006. 50-57.

[45] 柯欣,孫利民,吳志美.基于無線傳感器網絡匯聚傳輸實時性的分布式調度算法[J].通信學報,2007,28(4): 44-50.KE X, SUN L M, WU Z M. Distributed scheduling for real-time convergecast in wireless sensor networks[J]. Journal on Communication,2007, 28(4): 44-50.

[46] YI Y, VECIANA G D, SHAKKOTTAI S. On optimal MAC scheduling with physical interference[A]. Proc IEEE INFOCOM[C]. Anchorage, USA, 2007. 294-302.

[47] KYASANUR P, VAIDYA N H. Capacity of multi-channel wireless networks: impact of number of channels and interfaces[A]. Proc of ACM MOBICOM[C]. Cologne, German, 2005. 1-15.

[48] KIM Y G, SHIN H J, CHA H J. Y-MAC: an energy-efficient multi-channel MAC protocol for dense wireless sensor networks[A].Proc of International Conference on Information Processing in Sensor Networks (IPSN 2008)[C]. St Louis, USA, 2008. 55-63.

[49] RANIWALA R, CHIUEH T. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network[A]. IEEE INFOCOM’05[C]. Miami, USA, 2005.2223-2234

[50] DAS A, ALAZEMI H, VIJAYAKUMAR R,et al. Optimization models for fixed channel assignment in wireless mesh networks with multiple radios[A]. Proc of IEEE SECON[C]. Santa Clara, USA, 2005.

[51] SOLDTI P. On Cross-layer Design and Resource Scheduling in Wireless Networks[D]. Stockholm, Sweden, KTH, 2009.

[52] SOLDTI P, ZHANG H, HOHANSSON M. Deadline-Constrained Transmission Scheduling and Data Evacuation in WirelessHART Networks[R]. KTH Technical Report, 2009.

[53] ZHANG H, SOLDTI P, HOHANSSON M. Optimal link scheduling and channel assignment for convergecast in linear WirelessHART networks[A]. The 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT’09)[C].Seoul, Korea, 2009. 1-8.

[54] NASIPURI A, DAS S R. A multichannel CSMA MAC protocol for multihop wireless networks[A]. Proc of IEEE Wireless Communications and Networking Conference (WCNC)[C]. New Orleans,USA,1999. 1402-1406.

[55] NASIPURI A, DAS S R. Multichannel CSMA with signal power-based channel selection for multihop wireless networks[A]. Proc of IEEE Vehicular Technology Conference (VTC)[C]. Tokyo, Japan, 2000. 211-218.

[56] WU S L, LIN C Y, TSENG Y C,et al. A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks[A]. Int Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN)[C]. Dallas, USA, 2000. 232-237.

[57] JAIN N, DAS S. A multichannel CSMA MAC protocol with receiver-based channel selection for multihop wireless networks[A].Proc of 9th International Conference on Computer Communications and Networks (IC3N)[C]. Scottsdale, USA, 2001. 432-439.

[58] SO J, VAIDYA N H. Multi-channel MAC for ad hoc networks: handling multi-channel hidden terminals using a single transceiver[A].Proc of ACM MOBIHOC[C]. Roppongi Hills, Japan, 2004. 222-233.

[59] KO B J, MISRA V, PADHYE J,et al. Distributed channel assignment in multi-hop 802.11 mesh networks[A]. Proc of IEEE Wireless Communications and Networking Conference (WCNC’07)[C]. Hong Kong,China, 2007.

[60] ZHOU G, HUANG C D, YAN T,et al. MMSN: multi-frequency media access control for wireless sensor networks[A]. Proc of IEEE INFOCOM[C]. Barcelona, Spain, 2006. 1-13.

[61] CHEN X, HAN P, HE P S,et al. A multi-channel MAC protocol for wireless sensor networks[A]. Proc 6th IEEE International Conference on Computer and Information Technology (CIT’06)[C]. Bhubaneswar,India, 2006.1-6.

[62] KIM Y G, SHIN H J, CHA H J. Y-MAC: an energy-efficient multi-channel MAC protocol for dense wireless sensor networks[A].Proc of International Conference on Information Processing in Sensor Networks (IPSN 2008)[C]. St Louis,USA, 2008. 55-63.

[63] JOVANOVIC M D, DJORDIEVIC G L. TFMAC: multi-channel MAC protocol for wireless sensor networks[A]. Proc of IEEE INFOCOM[C]. Barcelona, Spain, 2006. 23-26.

[64] SUBRAMANIAN A P, GUPTA H, DAS S R. Minimum interference channel assignment in multi-radio wireless mesh networks[A]. Proc of IEEE SECON[C]. San Diego, USA, 2007. 481-490.

[65] SADEQ A, AMINE K, MARTIN K. Dynamic channel assignment for wireless mesh networks using clustering[A]. Proc of Seventh International Conference on Networking (ICN 2008)[C]. Cancun, Maxico,2008. 539-544.

[66] MALHOTRA B, NIKOLAIDIS I, NASCIMENTO M A. Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011, 17(2): 319-335.

[67] ZHANG X L, Capcity Analysis and Transmission Scheduling for Industrial Wireless Sensor Networks[D]. Doctoral Thesis, Shenyang,SIA, 2011.

[68] LIANG W, ZHANG X L, XIAO Y,et al. Survey and experiments of WIA-PA specification of industrial wireless network[J]. Wireless Communications and Mobile Computing, 2011, 11(8): 1197-1212.

[69] 李方敏, 徐文君, 劉新華. 無線傳感器網絡功率控制技術[J]. 軟件學報, 2008, 19(3): 716-732.LI F M, XU W J, LIU X H. Power control for wireless sensor networks[J]. Journal of Software, 2008, 19(3): 716-732.

[70] GOLDSMITH A, WICKER S. Design challenges for energy-constrained ad hoc wireless networks[J]. IEEE Wireless Communications, 2002, 9(4): 8-27.

[71] ELBATT T, EPREMIDES A. Joint scheduling and power control for wireless ad hoc networks[J]. IEEE Transaction on Wireless Communications, 2002, 3(1): 74-85.

[72] LU G, KRISHNAMACHARI B. Energy efficient joint scheduling and power control for wireless sensor networks[A]. Proc of Sensor and Ad Hoc Communications and Networks (IEEE SECON’05)[C].Santa Clara, USA, 2005. 361-373.

[73] WANG K, CARLA F C, RAMESH R R,et al. A distributed joint scheduling and power control algorithm for multicasting in wireless ad hoc networks[A]. IEEE International Conference on Communications(ICC’03)[C]. Anchorage, USA, 2003. 725-731.

[74] MOSCIBRODA T, WATTENHOFER R. Minimizing interference in ad hoc and sensor networks[A]. Proc of DLALM-POMC’05[C].Cologne, German, 2005. 1-10.

[75] MOSCIBRODA T, OSWALD Y A, WATTENHOFER R. How optimal are wireless scheduling protocols[A]. Proc of IEEE INFORCOM[C]. Anchorage, USA, 2007. 1433-1441.

[76] FU L Q, LIEW S C, HUANG J W. Power controlled scheduling with consecutive transmission constraints: complexity analysis and algorithm design[A]. Proc of IEEE INFOCOM[C]. Rio de Janeiro,Brazil, 2009. 1530-1538.