WSN內一種基于TDMA的時隙優化重組算法

李 峰，范 菁，黃 道

（1.云南民族大學云南省高校無線傳感器網絡重點實驗室，云南昆明650500；2.云南民族大學電氣信息工程學院，云南昆明650500）

WSN內一種基于TDMA的時隙優化重組算法

李 峰1，范 菁1，黃 道2

（1.云南民族大學云南省高校無線傳感器網絡重點實驗室，云南昆明650500；2.云南民族大學電氣信息工程學院，云南昆明650500）

無線傳感器網絡內節點的時隙分配是影響整個網絡能耗、時延的重要因素.STDMA的時隙分配算法能避免數據碰撞，在一定程度上降低了能量損耗，但由于每個節點分配的時隙固定、離散，造成節點頻繁啟動，損耗了大量能量，為此，在STDMA的基礎之上提出了OTT-TDMA算法，在MAC層重新調度時隙，減少節點啟動次數，同時盡量將節點發送時隙調度到接收時隙之后.實驗仿真表明，改進算法在能耗和時效性方面比STDMA有一定提高.

無線傳感器網絡；時隙重組；時延；MAC；能量損耗

無線傳感器網絡（wireless sensor networks，WSN）是由分布在物理空間上的大量無線傳感器節點通過自組織形式構成的網絡.網絡中每個傳感器節點都具有一種或多種感知器，能在所分布空間內進行多領域、大范圍的實時數據采集，在國防工業、險情監測等領域有廣泛的應用.無線傳感器網絡常部署在惡劣環境和人不宜到達的場所［1］，因此節點能量的補充受到了極大的限制，而良好的MAC層協議設計不僅可以減小WSN的能耗，還能提高WSN的時效性.文獻［2-3］分析了合理的MAC層協議設計對能量效率的有效提高.STDMA［4］（spatial time division multiple access）被視為一種主要的MAC層協議，因為它一方面提供了無碰撞的多信道接入，另一方面它允許多條非沖突鏈路在同一時隙中進行傳輸，有效降低了能量損失，提高了網絡的吞吐量.文獻［5-6］分析節點的頻繁啟動會造成能量的損失，然而只局限在鏈路層的能量優化.事實上，MAC層的時隙重組是有效減少啟動次數的最佳選擇.文獻［7］分析了采用全向天線時網絡內存在的廣播風暴和信號干擾問題.

本文闡述了時隙分配機制，分析、歸納了STDMA時隙分配算法，利用STDMA無碰撞接入和鏈路容量大的優勢，針對數據匯聚樹這種拓撲結構，提出了OTT-TDMA算法，在MAC層重新調度時隙，從根本上降低能耗與時延.本文的研究在基于使用定向天線節點基礎上展開，因為定向天線允許在同一鄰近區域內同時進行多個發送，而不會損壞被發送的分組［7］.

1 時隙分配

WSN內節點間的數據傳輸總是在某個信道上完成的，因此可以通過將信道進行時間分隙來描述節點的激活-休眠機制.不同拓撲結構的WSN根據自身節點數目、拓撲形態在信道上沿時間軸劃分不同的周期Tf.每個周期Tf包含數量不同、長度均為τ的時隙，且滿足Tf＝mτ（其中m為Tf內包含的時隙個數，τ為時隙長度）.當節點在周期Tf的第i個時隙為激活態且這個時隙為發送時隙時，將此時隙按圖1所示標記為1，用tran表示；當節點在周期Tf的第i個時隙為激活態且這個時隙為接收時隙時，將此時隙標記為-1，用rece表示；當節點處于休眠態時，相應的標記為0.當節點在某個時隙采集到或是接收到來自子節點的數據，用prod表示這個時隙.

這樣，可以將某個節點i的激活／休眠周期通過一個向量V來表示.若將節點的向量V按節點序號排列則可得到整個網絡內節點的時隙分配矩陣.

1.1 基于定向天線節點的TDMA時隙分配規則

WSN內存在2類碰撞［8-9］，第1類碰撞是本節點自身收發數據的碰撞；第2類碰撞是本節點和其他節點之間發送數據時產生的碰撞.不滿足上述2類碰撞的鏈路，證明他們可以在同一時隙內共存，在使用全向天線的WSN內STDMA無沖突鏈路間分配時隙的準則，可以歸納為：①只要指定鏈路在傳輸數據，該鏈路的發送節點一跳之內的所有鄰居節點（接收節點除外）將不能在該時隙內發送數據和接收數據；②指定鏈路的發送節點2跳以外的節點既可以在該時隙內發送數據，也可以接收數據；③如果該節點恰好是此鏈路發送節點的2跳鄰居節點，則該節點不能發送數據.由于本文的研究基礎是使用定向天線的WSN，允許在同一鄰近區域內有多個發送同時進行，因此發送鏈路發送節點的2跳鄰居節點可以發送數據［7］.以13個節點的拓撲結構為例（如圖2），通過以上規則可確定其整個網絡內節點的時隙分配矩陣如圖3所示.

從網絡內節點的時隙分配矩陣可以看出，此種時隙分配雖然滿足了無碰撞的條件，卻分配得很散亂，節點在一幀內的啟動次數較多.且接收時隙與發送時隙的順序安排也是隨機的，增大了排隊時延.

1.2 OTT-TDMA算法時隙重組

圖3中，每一時隙內啟動節點數目相差很大，各節點在1幀內的啟動次數也是不一樣的，整個幀在網絡中的節點激活時隙十分散亂.這是由于在STDMA幀劃分無沖突域時，未考慮節點重啟能耗，這樣分配時隙會使某些節點在1幀內的啟動次數很多（啟動次數最大可以占到激活次數的2／3），使得節點不斷地開啟和關閉，造成大量的能量浪費.

在此將運用OTT-TDMA（optimal timeslot table TDMA）算法，對每一幀的時隙進行重新組合，使每一幀的每個節點啟動次數在滿足STDMA的條件下降到最低，如圖4所示.

由圖4可以看出，整個網絡內的發送鏈路并未改變，只是調整了各個鏈路的激活時隙.如鏈路｛7，6｝的激活時隙由第1個變為第4個.調整后的時隙分配矩陣，激活時隙都連在一起且發送時隙一般都被安排在接收時隙之后，既減少了重啟能耗又減少了同步時延和排隊時延.

2 激活時隙反轉分析

STDMA采取的是一種靜態的時隙分配法則，即在1幀內給節點分配固定的激活時隙，無論在此時隙節點有無數據發送都會被激活.本文協議在此基礎上改進.根據本文協議的設計，節點的發送狀態除了當節點所處信道的時隙標記為1時會發生，還會在這種情況下發生：當節點和它的父節點在同一個時隙內都處于接收狀態，父節點在此接收時隙對應的子節點和節點在此接收時隙對應的子節點都無數據發送且節點緩存內有數據時，節點在此時隙內由接收狀態轉變為發送狀態，向父節點發送數據，并將此時隙記為tran.例如在圖2的拓撲結構中，6、7節點在第3個時隙都處于接收狀態，當7節點在此時隙下對應的子節點9及節點6在此時隙下對應的子節點8都無數據發送，且7節點緩存內有數據要發送時，節點7由接收狀態轉變為發送狀態，向父節點6發送數據.

3 時延分析

數據包在傳遞過程中存在2類時延：①節點在產生／接收到數據包后往往不能立即被發送，需等到本幀的發送時隙才能發送，這個等待過程稱為同步時延；②存在緩存內的數據包如果在本幀未被選中發送，需等下一幀的發送時隙，這個等待過程稱為排隊時延.數據包的總時延即同步時延與排隊時延之和.

如果拓撲結構內處在第φ層編號為i的節點在第j個時隙采集到了1個數據包，試圖傳向信宿節點，則在向上傳遞過程中它在各層所產生的時延可表示為d（i，j，k），其中k表示它所處的層.

其中prodk表示數據包在鏈路中第k層時被采集／接收到的時隙，trank表示對應的發送時隙.則這個數據包在網絡中傳輸的總時延：

網絡中數據包是并行傳輸，因此1幀數據傳輸的總時延

4 能耗分析

研究表明無線傳感器節點的能量主要消耗在無線通信模塊，傳感器模塊和處理器模塊的能耗相對較少.通信耗能以幾個數量級的規模大于計算耗能和感知耗能，因此可以忽略計算耗能和感知耗能.

如果在拓撲結構內處在第k層編號為i的節點在第j個時隙采集到1個數據包，試圖傳向信宿節點，則在向上傳遞過程中它的能耗e可表示為：

其中Ptx為發送功率，Prx為接收功率，Ttx為發送時間，Trx為接收時間，Pout為天線驅動功率（很小，可略為0），（k-1）為數據包轉發的次數.其在網絡內的總發送時間可表示為T＝（k-1）Ttx.數據負荷為i的網絡內，1幀的能耗等于激活空閑能耗與數據包發送、接收能耗之和.可表示為：

其中n為網絡內激活時隙數，τ為時隙寬度，pact為激活空閑功率.

5 仿真實驗與結果分析

5.1 仿真環境設置

本文采用Matlab進行仿真，仿真均基于同一實驗場景：13個無線傳感器節點通過自組織的方式形成圖2所示的WSN.仿真所用模型分別是STDMA算法與本文提出的OTT-TDMA算法.2種算法設置的參數相同，仿真主要參數如表1.

表1 仿真參數

5.2 仿真結果與分析

設網絡內每個幀長所產生數據包從1～30變化.在2種算法下網絡總時延變化如圖5.由圖5可得，在相同的仿真場景下OTT-TDMA算法的總時延基本低于STDMA算法的總時延，且隨著網絡負荷增大網絡總時延也呈增大趨勢.這是因為新算法總是盡量將發送時隙安排在接收時隙之后，以此來減少數據包轉發過程中的同步、排隊時延，時隙反轉算法也能在一定程度上降低時延，網絡負載增大，節點緩存內數據包增多，數據包的排隊時延隨之增大，傳輸時延也隨之增大.

設網絡內每個幀長所產生數據包從6～10變化.在2種算法模式下包平均能耗變化如圖6.從圖6中可以看出在相同的仿真場景下OTT-TDMA算法的包平均能耗要低于STDMA算法，且隨著網絡負載增大，包平均能耗降低.這是因為新算法將節點的激活時隙連結到了一塊，降低了節點的啟動能耗.網絡內的激活時隙數固定，節點接收／發送功率與激活空閑功率相近，所以在2種算法下幀能耗都相對固定，包平均能耗隨負荷增大而下降.

［1］AKYILDIZ I F，SU W，SANKARASUBRAMANIAM Y，et al.Wireless sensor networks：A survey［J］.Computer Networks，2002，38（4）：393-422.

［2］XIAO X，ZHENG B Y，YAN ZY，et al.Energy efficient TDMA-based MAC protocol associated with GAF for wireless sensor networks［J］.The Journal of China Universities of Posts and Telecommunications，2007，14（1）：6-11.

［3］LU X F，TOWSLEY D，LIO P，et al.An adaptive directional MAC protocol for ad hoc networks using directional antennas［J］.Science China Information Sciences，2012，55（6）：1360-1371.

［4］LATTANZI E，REGINIE，ACQUAVIVA A，et al.Energetic sustainability of routing algorithms for energy-harvesting wireless sensor networks［J］.Computer Communications，2007，30（14）：2976-2986.

［5］NELSON R，KLEINROCK L.Spatial TDMA：A collisionfree multihop channel access protocol［J］.Communications，IEEE Transactions on，1985，33（9）：934-944.

［6］XIANG C S，LIG，LIQ X，et al.Energy efficient cross layer STDMA design in solar-powered wireless mesh network［J］.Applied Mechanics and Materials，2013，321：2849-2854.

［7］安豐彩，吳華.定向天線配置Ad Hoc網絡的MAC協議研究［J］.大連海事大學學報：自然科學版，2005，31（3）：90-93.

［8］范菁.異構無線傳感器網絡跨層MAC協議研究現狀［J］.云南民族大學學報：自然科學版，2011，20（5）：381-387.

［9］KWON Y，FANG Y，LATCHMAN H.A novel MAC protocol with fast collision resolution for wireless LANs［C］／／INFOCOM 2003，Twenty-Second Annual Joint Conference of the IEEE Computer and Communications.IEEE Societies.IEEE，2003（2）：853-862.

（責任編輯 莊紅林）

An optimization algorithm based on reorganizing TDMA′s time slot in WSN

LI Feng1，FAN Jing1，HUANG Dao2
（1.Key Laboratory of Wireless Sensor Networks in Universities of Yunnan Province，Yunnan Minzu University，Kunming 650500，China；2.School of Electric and Information，Yunnan Minzu University，Kunming 650500，China）

The node′s time slot assignment in WSN is very important because it affects the entire network′s energy consumption and delay.STDMA can help avoid data collisions and reduce the energy loss to some extent，but each node′s time slots are both fixed and discrete，resulting in frequent node′s start and a lot of energy loss.On the basis of STDMA，this researchhas proposed OTT-TDMA algorithm to reschedule slots at the MAC layer，reducing the number of the node′s startand trying to schedule the node′s sending slotsafter its receiving slots.Simulation results show that the proposed algorithm has better performance on delay and energy consumption than STDMA.

wireless sensor networks；time slots reschedule；delay；MAC；energy consumption

TP393

A

1672-8513（2014）06-0396-04

2014-04-11.

國家自然科學基金（60963026，61163061）；云南省應用基礎科學研究計劃項目（2011FZ174）.

李峰（1988-），男，碩士研究生.主要研究方向：無線傳感器網絡.

范菁（1976-），女，博士研究生，教授，碩士生導師.主要研究方向：無線傳感器網絡、智能計算與環境監測.