WSN內(nèi)一種基于TDMA的時隙優(yōu)化重組算法

李 峰，范 菁，黃 道

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

WSN內(nèi)一種基于TDMA的時隙優(yōu)化重組算法

李 峰1，范 菁1，黃 道2

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

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

無線傳感器網(wǎng)絡(luò)；時隙重組；時延；MAC；能量損耗

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

本文闡述了時隙分配機制，分析、歸納了STDMA時隙分配算法，利用STDMA無碰撞接入和鏈路容量大的優(yōu)勢，針對數(shù)據(jù)匯聚樹這種拓?fù)浣Y(jié)構(gòu)，提出了OTT-TDMA算法，在MAC層重新調(diào)度時隙，從根本上降低能耗與時延.本文的研究在基于使用定向天線節(jié)點基礎(chǔ)上展開，因為定向天線允許在同一鄰近區(qū)域內(nèi)同時進(jìn)行多個發(fā)送，而不會損壞被發(fā)送的分組［7］.

1 時隙分配

WSN內(nèi)節(jié)點間的數(shù)據(jù)傳輸總是在某個信道上完成的，因此可以通過將信道進(jìn)行時間分隙來描述節(jié)點的激活-休眠機制.不同拓?fù)浣Y(jié)構(gòu)的WSN根據(jù)自身節(jié)點數(shù)目、拓?fù)湫螒B(tài)在信道上沿時間軸劃分不同的周期Tf.每個周期Tf包含數(shù)量不同、長度均為τ的時隙，且滿足Tf＝mτ（其中m為Tf內(nèi)包含的時隙個數(shù)，τ為時隙長度）.當(dāng)節(jié)點在周期Tf的第i個時隙為激活態(tài)且這個時隙為發(fā)送時隙時，將此時隙按圖1所示標(biāo)記為1，用tran表示；當(dāng)節(jié)點在周期Tf的第i個時隙為激活態(tài)且這個時隙為接收時隙時，將此時隙標(biāo)記為-1，用rece表示；當(dāng)節(jié)點處于休眠態(tài)時，相應(yīng)的標(biāo)記為0.當(dāng)節(jié)點在某個時隙采集到或是接收到來自子節(jié)點的數(shù)據(jù)，用prod表示這個時隙.

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

1.1 基于定向天線節(jié)點的TDMA時隙分配規(guī)則

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

從網(wǎng)絡(luò)內(nèi)節(jié)點的時隙分配矩陣可以看出，此種時隙分配雖然滿足了無碰撞的條件，卻分配得很散亂，節(jié)點在一幀內(nèi)的啟動次數(shù)較多.且接收時隙與發(fā)送時隙的順序安排也是隨機的，增大了排隊時延.

1.2 OTT-TDMA算法時隙重組

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

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

由圖4可以看出，整個網(wǎng)絡(luò)內(nèi)的發(fā)送鏈路并未改變，只是調(diào)整了各個鏈路的激活時隙.如鏈路｛7，6｝的激活時隙由第1個變?yōu)榈?個.調(diào)整后的時隙分配矩陣，激活時隙都連在一起且發(fā)送時隙一般都被安排在接收時隙之后，既減少了重啟能耗又減少了同步時延和排隊時延.

2 激活時隙反轉(zhuǎn)分析

STDMA采取的是一種靜態(tài)的時隙分配法則，即在1幀內(nèi)給節(jié)點分配固定的激活時隙，無論在此時隙節(jié)點有無數(shù)據(jù)發(fā)送都會被激活.本文協(xié)議在此基礎(chǔ)上改進(jìn).根據(jù)本文協(xié)議的設(shè)計，節(jié)點的發(fā)送狀態(tài)除了當(dāng)節(jié)點所處信道的時隙標(biāo)記為1時會發(fā)生，還會在這種情況下發(fā)生：當(dāng)節(jié)點和它的父節(jié)點在同一個時隙內(nèi)都處于接收狀態(tài)，父節(jié)點在此接收時隙對應(yīng)的子節(jié)點和節(jié)點在此接收時隙對應(yīng)的子節(jié)點都無數(shù)據(jù)發(fā)送且節(jié)點緩存內(nèi)有數(shù)據(jù)時，節(jié)點在此時隙內(nèi)由接收狀態(tài)轉(zhuǎn)變?yōu)榘l(fā)送狀態(tài)，向父節(jié)點發(fā)送數(shù)據(jù)，并將此時隙記為tran.例如在圖2的拓?fù)浣Y(jié)構(gòu)中，6、7節(jié)點在第3個時隙都處于接收狀態(tài)，當(dāng)7節(jié)點在此時隙下對應(yīng)的子節(jié)點9及節(jié)點6在此時隙下對應(yīng)的子節(jié)點8都無數(shù)據(jù)發(fā)送，且7節(jié)點緩存內(nèi)有數(shù)據(jù)要發(fā)送時，節(jié)點7由接收狀態(tài)轉(zhuǎn)變?yōu)榘l(fā)送狀態(tài)，向父節(jié)點6發(fā)送數(shù)據(jù).

3 時延分析

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

如果拓?fù)浣Y(jié)構(gòu)內(nèi)處在第φ層編號為i的節(jié)點在第j個時隙采集到了1個數(shù)據(jù)包，試圖傳向信宿節(jié)點，則在向上傳遞過程中它在各層所產(chǎn)生的時延可表示為d（i，j，k），其中k表示它所處的層.

其中prodk表示數(shù)據(jù)包在鏈路中第k層時被采集／接收到的時隙，trank表示對應(yīng)的發(fā)送時隙.則這個數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸?shù)目倳r延：

網(wǎng)絡(luò)中數(shù)據(jù)包是并行傳輸，因此1幀數(shù)據(jù)傳輸?shù)目倳r延

4 能耗分析

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

如果在拓?fù)浣Y(jié)構(gòu)內(nèi)處在第k層編號為i的節(jié)點在第j個時隙采集到1個數(shù)據(jù)包，試圖傳向信宿節(jié)點，則在向上傳遞過程中它的能耗e可表示為：

其中Ptx為發(fā)送功率，Prx為接收功率，Ttx為發(fā)送時間，Trx為接收時間，Pout為天線驅(qū)動功率（很小，可略為0），（k-1）為數(shù)據(jù)包轉(zhuǎn)發(fā)的次數(shù).其在網(wǎng)絡(luò)內(nèi)的總發(fā)送時間可表示為T＝（k-1）Ttx.數(shù)據(jù)負(fù)荷為i的網(wǎng)絡(luò)內(nèi)，1幀的能耗等于激活空閑能耗與數(shù)據(jù)包發(fā)送、接收能耗之和.可表示為：

其中n為網(wǎng)絡(luò)內(nèi)激活時隙數(shù)，τ為時隙寬度，pact為激活空閑功率.

5 仿真實驗與結(jié)果分析

5.1 仿真環(huán)境設(shè)置

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

表1 仿真參數(shù)

5.2 仿真結(jié)果與分析

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

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

［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網(wǎng)絡(luò)的MAC協(xié)議研究［J］.大連海事大學(xué)學(xué)報：自然科學(xué)版，2005，31（3）：90-93.

［8］范菁.異構(gòu)無線傳感器網(wǎng)絡(luò)跨層MAC協(xié)議研究現(xiàn)狀［J］.云南民族大學(xué)學(xué)報：自然科學(xué)版，2011，20（5）：381-387.

［9］KWON Y，F(xiàn)ANG 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.

（責(zé)任編輯 莊紅林）

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

LI Feng1，F(xiàn)AN 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.

國家自然科學(xué)基金（60963026，61163061）；云南省應(yīng)用基礎(chǔ)科學(xué)研究計劃項目（2011FZ174）.

李峰（1988-），男，碩士研究生.主要研究方向：無線傳感器網(wǎng)絡(luò).

范菁（1976-），女，博士研究生，教授，碩士生導(dǎo)師.主要研究方向：無線傳感器網(wǎng)絡(luò)、智能計算與環(huán)境監(jiān)測.