崔可嘉,孫 昕

(北京交通大學(xué)電子信息工程學(xué)院,北京100044)

基于TDMA的無(wú)沖突動(dòng)態(tài)時(shí)隙分配算法

崔可嘉,孫 昕

(北京交通大學(xué)電子信息工程學(xué)院,北京100044)

針對(duì)分簇Ad Hoc網(wǎng)絡(luò)中固定時(shí)隙分配算法信道資源浪費(fèi)和競(jìng)爭(zhēng)時(shí)隙分配算法傳輸延遲不固定的問(wèn)題,提出一種基于時(shí)分多址接入的無(wú)沖突動(dòng)態(tài)時(shí)隙分配算法。該算法根據(jù)網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)調(diào)整幀長(zhǎng),即當(dāng)網(wǎng)絡(luò)負(fù)載增大時(shí),增加幀長(zhǎng),提高信道利用率;當(dāng)網(wǎng)絡(luò)負(fù)載減小時(shí),減少幀長(zhǎng),降低信道申請(qǐng)時(shí)延。仿真結(jié)果表明,與NEBS算法和時(shí)隙ALOHA算法相比,該算法可根據(jù)網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)調(diào)整資源分配,從而提高系統(tǒng)的吞吐量。

時(shí)分多址;時(shí)隙分配算法;時(shí)隙回收算法;無(wú)沖突;Ad Hoc網(wǎng)絡(luò);吞吐量

1 概述

在Ad Hoc網(wǎng)絡(luò)中,時(shí)隙分配算法控制信道資源的分配,直接影響系統(tǒng)的性能。時(shí)隙分配算法分為2類:基于競(jìng)爭(zhēng)的分配算法和基于調(diào)度的分配算法[1]。

基于競(jìng)爭(zhēng)的分配算法允許節(jié)點(diǎn)通過(guò)隨機(jī)接入的方式爭(zhēng)用時(shí)隙,典型的基于競(jìng)爭(zhēng)的分配算法包括時(shí)隙ALOHA和CSMA/CA等[2-4]。盡管這類分配算法得到了廣泛的應(yīng)用,但由于其基于競(jìng)爭(zhēng)的本質(zhì),當(dāng)負(fù)載上升后,數(shù)據(jù)的傳輸時(shí)延難以得到保證,因此難以滿足實(shí)時(shí)業(yè)務(wù)(如視頻、語(yǔ)音等)的要求。

最典型的基于調(diào)度的分配算法是TDMA時(shí)隙分配算法。網(wǎng)絡(luò)中各節(jié)點(diǎn)被分配一定數(shù)量的時(shí)隙,進(jìn)行無(wú)沖突的數(shù)據(jù)傳輸,可以滿足服務(wù)質(zhì)量(QoS)的需求[5]。時(shí)隙分配算法控制資源的分配,直接影響系統(tǒng)吞吐量,是這類算法研究的重點(diǎn)[6-7]。

在文獻(xiàn)[8]提出的NAMA算法中,各個(gè)節(jié)點(diǎn)擁有一個(gè)隨機(jī)數(shù)種子,并以此計(jì)算哈希值(Hash),決定當(dāng)前時(shí)隙的使用者。各個(gè)節(jié)點(diǎn)通過(guò)交換隨機(jī)數(shù)種子,即可計(jì)算網(wǎng)絡(luò)內(nèi)所有節(jié)點(diǎn)在當(dāng)前時(shí)隙的哈希值,實(shí)現(xiàn)無(wú)沖突地傳輸數(shù)據(jù)。但是NAMA算法僅能實(shí)現(xiàn)信道資源的均勻分配,未考慮到各個(gè)節(jié)點(diǎn)負(fù)載不平衡的情況,造成了信道資源的浪費(fèi)。同時(shí),在新節(jié)點(diǎn)加入網(wǎng)絡(luò)時(shí),由于其他節(jié)點(diǎn)尚未獲得其隨機(jī)數(shù)種子,可能引起持續(xù)的數(shù)據(jù)碰撞,導(dǎo)致新節(jié)點(diǎn)無(wú)法廣播自身的隨機(jī)數(shù)種子。

文獻(xiàn)[9]提出的NEBS算法對(duì)NAMA算法進(jìn)行了改進(jìn)。NEBS算法中有3種時(shí)隙:基于競(jìng)爭(zhēng)的NE時(shí)隙,用于各節(jié)點(diǎn)傳輸自身的NAMA隨機(jī)數(shù)種子;基于無(wú)競(jìng)爭(zhēng)的NA時(shí)隙,使用NAMA算法進(jìn)行接入,用于各個(gè)節(jié)點(diǎn)申請(qǐng)數(shù)據(jù)傳輸D時(shí)隙;基于無(wú)競(jìng)爭(zhēng)的D時(shí)隙,進(jìn)行數(shù)據(jù)傳輸。各個(gè)節(jié)點(diǎn)在NE時(shí)隙使用隨機(jī)接入?yún)f(xié)議,廣播自身的NAMA隨機(jī)數(shù)種子,解決了NAMA算法中有可能產(chǎn)生的持續(xù)碰撞。由于NEBS僅使用NAMA算法進(jìn)行數(shù)據(jù)傳輸時(shí)隙的預(yù)約,因此可以很好地適應(yīng)網(wǎng)絡(luò)負(fù)載的變化。但是由于NA時(shí)隙以及NE時(shí)隙不能用于數(shù)據(jù)傳輸,它們將固定占用部分時(shí)隙,造成時(shí)隙資源的浪費(fèi)。

在文獻(xiàn)[10]提出的USAP算法中,每復(fù)幀中的幀數(shù)N和每幀中的時(shí)隙數(shù)M均為固定值,需要根據(jù)網(wǎng)絡(luò)規(guī)模提前規(guī)劃。每幀的第一個(gè)時(shí)隙為唯一的節(jié)點(diǎn)保留,用于發(fā)送控制信息預(yù)約時(shí)隙,因此幀數(shù)N需大于網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)。每幀中的時(shí)隙數(shù)M直接影響系統(tǒng)性能。若M取值過(guò)小,則大量時(shí)隙用于發(fā)送控制信息,造成了信道資源的浪費(fèi);若M取值過(guò)大,則導(dǎo)致預(yù)約時(shí)隙的延時(shí)過(guò)大。每幀中的時(shí)隙數(shù)M需要預(yù)先配置,很難取得最優(yōu)值。這種算法的分配方式單一、不夠靈活,難以應(yīng)用于節(jié)點(diǎn)數(shù)較多、負(fù)載變化較大的網(wǎng)絡(luò)。

針對(duì)固定幀長(zhǎng)度的時(shí)隙分配算法,文獻(xiàn)[11]將信道資源劃分為等間隔的時(shí)隙塊,然后使用二叉樹(shù)塊內(nèi)均分法進(jìn)行信道資源的均勻分配。但是,這種算法邏輯較為復(fù)雜,而且在多次劃分后會(huì)產(chǎn)生不等間隔的小時(shí)隙塊,這些時(shí)隙塊不能單獨(dú)分配給用戶,造成了時(shí)隙資源的浪費(fèi)。

文獻(xiàn)[12-13]提出的算法針對(duì)USAP算法不靈活的缺陷進(jìn)行了改進(jìn)。它們以二進(jìn)制指數(shù)增加幀長(zhǎng),調(diào)節(jié)信道資源的分配。但是這些算法并沒(méi)有幀長(zhǎng)減少機(jī)制。新入網(wǎng)節(jié)點(diǎn)只能在每幀的第一時(shí)隙接入網(wǎng)絡(luò),不斷增長(zhǎng)的幀將導(dǎo)致新節(jié)點(diǎn)接入網(wǎng)絡(luò)的時(shí)延增大。同時(shí),過(guò)長(zhǎng)的幀中存在未分配時(shí)隙,降低了信道利用率。

針對(duì)網(wǎng)絡(luò)環(huán)境的特點(diǎn)和上述算法的不足,本文提出了一種基于TDMA的無(wú)沖突動(dòng)態(tài)時(shí)隙分配算法。算法根據(jù)網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)調(diào)整幀長(zhǎng),調(diào)節(jié)固定分配時(shí)隙和動(dòng)態(tài)分配時(shí)隙所占的比例,以解決固定幀長(zhǎng)算法不夠靈活的問(wèn)題。

2 算法描述

2.1 復(fù)幀結(jié)構(gòu)

對(duì)網(wǎng)絡(luò)環(huán)境進(jìn)行了如下假設(shè):

(1)數(shù)據(jù)碰撞是導(dǎo)致傳輸失敗的唯一原因;

(2)每個(gè)節(jié)點(diǎn)擁有各自唯一的ID,且ID號(hào)從1開(kāi)始連續(xù)遞增;

(3)網(wǎng)絡(luò)內(nèi)部節(jié)點(diǎn)總數(shù)固定,節(jié)點(diǎn)可能頻繁出入網(wǎng),且負(fù)載不平衡;

(4)網(wǎng)絡(luò)內(nèi)有中心,且中心節(jié)點(diǎn)與其他各節(jié)點(diǎn)均在一跳范圍內(nèi)。中心節(jié)點(diǎn)的ID號(hào)為1。

在本文算法中,一個(gè)復(fù)幀包含n個(gè)固定幀,n應(yīng)不小于分簇Ad Hoc網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。一個(gè)幀包含k(1≤k≤MAX_SLOT)個(gè)不固定時(shí)隙,k隨網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)調(diào)整。MAX_SLOT為每幀最大的時(shí)隙數(shù),隨著MAX_SLOT的增加,可以對(duì)信道資源進(jìn)行更細(xì)致的劃分;但是在高負(fù)載情況下,若每幀時(shí)隙數(shù)過(guò)大,會(huì)導(dǎo)致時(shí)隙申請(qǐng)的時(shí)延增大。因此,需要根據(jù)實(shí)際情況設(shè)置MAX_SLOT的取值。復(fù)幀結(jié)構(gòu)如圖1所示。

圖1 復(fù)幀結(jié)構(gòu)

本文算法中包含2類信令:控制信令和數(shù)據(jù)信令?？刂菩帕钣?種:一般節(jié)點(diǎn)的時(shí)隙申請(qǐng)信令和中心節(jié)點(diǎn)的時(shí)隙分配信息信令。每幀包含2個(gè)部分:固定分配時(shí)隙部分和動(dòng)態(tài)分配時(shí)隙部分。每幀的第1時(shí)隙為固定分配時(shí)隙,第1幀的第1時(shí)隙固定分配給中心節(jié)點(diǎn),用于發(fā)送時(shí)隙分配信息信令,第i幀的第1時(shí)隙固定分配給ID號(hào)為i的節(jié)點(diǎn),用于發(fā)送數(shù)據(jù)信令或時(shí)隙申請(qǐng)信令;每幀的第2～k時(shí)隙由簇內(nèi)中心節(jié)點(diǎn)根據(jù)網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)分配給各個(gè)節(jié)點(diǎn)。

文獻(xiàn)[9]中的NEBS算法將時(shí)隙分為控制信令時(shí)隙和數(shù)據(jù)時(shí)隙,控制信令時(shí)隙專門用于傳輸控制信令,不可進(jìn)行數(shù)據(jù)信令的傳輸;同理,在數(shù)據(jù)時(shí)隙不能進(jìn)行控制信令的傳輸。本文算法不再做這種劃分,除第1幀的第1時(shí)隙用于時(shí)隙分配信息信令的傳輸,其他時(shí)隙均可傳輸控制信令或數(shù)據(jù)信令。當(dāng)無(wú)需傳輸控制信令時(shí),控制信令時(shí)隙的存在會(huì)降低時(shí)隙利用率;而當(dāng)節(jié)點(diǎn)需要申請(qǐng)時(shí)隙時(shí),本文算法可使用節(jié)點(diǎn)擁有的任何時(shí)隙進(jìn)行傳輸控制信令,降低了時(shí)隙申請(qǐng)的時(shí)延。

2.2 時(shí)隙分配流程

時(shí)隙分配流程包括2個(gè)部分:一般節(jié)點(diǎn)申請(qǐng)時(shí)隙和中心節(jié)點(diǎn)授予時(shí)隙。

當(dāng)網(wǎng)絡(luò)負(fù)載上升時(shí),1個(gè)復(fù)幀中的1個(gè)時(shí)隙不能滿足數(shù)據(jù)傳輸?shù)男枨?數(shù)據(jù)在節(jié)點(diǎn)內(nèi)部的緩存隊(duì)列中緩存。當(dāng)緩存隊(duì)列長(zhǎng)度L小于等于幀數(shù)n時(shí),節(jié)點(diǎn)發(fā)送隊(duì)列中的數(shù)據(jù);當(dāng)緩存隊(duì)列長(zhǎng)度L大于幀數(shù)n時(shí),節(jié)點(diǎn)將向中心節(jié)點(diǎn)發(fā)送時(shí)隙申請(qǐng)信令,請(qǐng)求中心節(jié)點(diǎn)額外分配時(shí)隙。申請(qǐng)的時(shí)隙數(shù)s為:

在收到時(shí)隙申請(qǐng)信令后,中心節(jié)點(diǎn)判斷是否滿足時(shí)隙授予條件,若時(shí)隙數(shù)量k未達(dá)到最大時(shí)隙數(shù)MAX_SLOT,則中心節(jié)點(diǎn)根據(jù)申請(qǐng)時(shí)隙數(shù)增加每幀中時(shí)隙的個(gè)數(shù),將這些時(shí)隙分配給該節(jié)點(diǎn),并更新時(shí)隙分配表;若時(shí)隙數(shù)量k已經(jīng)達(dá)到最大時(shí)隙數(shù)MAX_SLOT,則中心節(jié)點(diǎn)進(jìn)行優(yōu)先級(jí)搶占。在1幀1時(shí)隙,中心節(jié)點(diǎn)發(fā)送時(shí)隙分配信息信令,各個(gè)節(jié)點(diǎn)收到后,進(jìn)行時(shí)隙分配信息的同步,確定自身的發(fā)送時(shí)隙。圖2給出了一個(gè)時(shí)隙分配的例子,網(wǎng)絡(luò)中共包含5個(gè)節(jié)點(diǎn),1個(gè)復(fù)幀內(nèi)包含5個(gè)幀。

圖2 時(shí)隙分配舉例

在初始狀態(tài)下,中心節(jié)點(diǎn)在1幀1時(shí)隙發(fā)送時(shí)隙分配信息信令,其余節(jié)點(diǎn)各擁有20%的信道資源。當(dāng)3號(hào)節(jié)點(diǎn)的負(fù)載上升,20%的信道資源不能滿足傳輸需求。假設(shè)在3幀1時(shí)隙時(shí),3號(hào)節(jié)點(diǎn)的隊(duì)列長(zhǎng)度達(dá)到12,根據(jù)式(1),它將向中心節(jié)點(diǎn)申請(qǐng)2個(gè)時(shí)隙。在收到時(shí)隙申請(qǐng)信令后,中心節(jié)點(diǎn)將時(shí)隙2和時(shí)隙3分配給3號(hào)節(jié)點(diǎn),并將每幀時(shí)隙數(shù)k增加到3,此時(shí)幀結(jié)構(gòu)尚未變化。中心節(jié)點(diǎn)在下一復(fù)幀的1幀1時(shí)隙廣播新的時(shí)隙分配表,各個(gè)節(jié)點(diǎn)收到新的時(shí)隙分配表后,根據(jù)其內(nèi)容更新本地的時(shí)隙信息,此時(shí),幀結(jié)構(gòu)發(fā)生變化,3號(hào)節(jié)點(diǎn)可以在每幀的2時(shí)隙、3時(shí)隙和3幀1時(shí)隙發(fā)送數(shù)據(jù),3號(hào)節(jié)點(diǎn)擁有73.3%的信道資源。

2.3 時(shí)隙回收流程

本文算法可以對(duì)未使用的時(shí)隙進(jìn)行回收,減少幀長(zhǎng)度,以保證信道資源的高效利用。在時(shí)隙分配之后,中心節(jié)點(diǎn)將持續(xù)監(jiān)聽(tīng)各個(gè)已分配時(shí)隙的使用情況,并以復(fù)幀(n幀)為單位統(tǒng)計(jì)各個(gè)節(jié)點(diǎn)未使用的時(shí)隙數(shù)count。在一個(gè)復(fù)幀結(jié)束后,中心節(jié)點(diǎn)首先根據(jù)監(jiān)聽(tīng)結(jié)果,計(jì)算各個(gè)節(jié)點(diǎn)需回收的時(shí)隙數(shù)m。需回收的時(shí)隙數(shù)m為:

然后,中心節(jié)點(diǎn)刪除時(shí)隙分配表中被回收的時(shí)隙,并更新每幀時(shí)隙數(shù)k,最后,中心節(jié)點(diǎn)在1幀1時(shí)隙發(fā)送時(shí)隙分配信息信令,其他節(jié)點(diǎn)該信令后,進(jìn)行時(shí)隙分配信息的同步。圖3給出了一個(gè)時(shí)隙回收的例子。

圖3 時(shí)隙回收舉例

網(wǎng)絡(luò)中有5個(gè)節(jié)點(diǎn),每復(fù)幀包含5個(gè)幀。在初始狀態(tài)下,每幀包含3個(gè)時(shí)隙,2時(shí)隙和3時(shí)隙分配給2號(hào)節(jié)點(diǎn)。在第1復(fù)幀中,2號(hào)節(jié)點(diǎn)在1幀2時(shí)隙、2幀3時(shí)隙、3幀3時(shí)隙和5幀2時(shí)隙發(fā)送數(shù)據(jù),使用時(shí)隙數(shù)為4,未使用時(shí)隙數(shù)為7。根據(jù)式(2),中心節(jié)點(diǎn)應(yīng)回收2號(hào)節(jié)點(diǎn)的一個(gè)時(shí)隙。在第2復(fù)幀中,中心節(jié)點(diǎn)在1幀1時(shí)隙發(fā)送新的時(shí)隙分配信息信令,各個(gè)節(jié)點(diǎn)收到后更新幀結(jié)構(gòu)。更新后,每幀包含2個(gè)時(shí)隙,第1時(shí)隙為固定分配時(shí)隙,第2時(shí)隙供2號(hào)節(jié)點(diǎn)使用。在時(shí)隙回收前,一復(fù)幀共包含15個(gè)時(shí)隙, 2號(hào)節(jié)點(diǎn)擁有73.3%的信道資源;時(shí)隙回收后,一復(fù)幀共包含10個(gè)時(shí)隙,2號(hào)節(jié)點(diǎn)擁有60%的信道資源。與文獻(xiàn)[12-13]相比,本文算法對(duì)未使用時(shí)隙進(jìn)行動(dòng)態(tài)回收,使時(shí)隙申請(qǐng)得到更快的響應(yīng),提高了信道利用率。

2.4 優(yōu)先級(jí)機(jī)制

文獻(xiàn)[8-13]中的算法均無(wú)優(yōu)先級(jí)機(jī)制。當(dāng)網(wǎng)絡(luò)總負(fù)載較大時(shí),各個(gè)節(jié)點(diǎn)將采用平均分配的方式獲取信道資源。在這種情況下,業(yè)務(wù)的服務(wù)質(zhì)量(QoS)無(wú)法得到保障。在本文算法中,時(shí)隙申請(qǐng)遵循優(yōu)先級(jí)機(jī)制,當(dāng)網(wǎng)絡(luò)負(fù)載較大時(shí),僅為低優(yōu)先級(jí)節(jié)點(diǎn)保留固定分配部分的信道資源,保證低優(yōu)先級(jí)節(jié)點(diǎn)不會(huì)因?yàn)闊o(wú)法申請(qǐng)到信道而“餓死”;高優(yōu)先級(jí)節(jié)點(diǎn)將占用大部分信道資源,保證業(yè)務(wù)的服務(wù)質(zhì)量。

各個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)在規(guī)劃網(wǎng)絡(luò)時(shí)配置,在申請(qǐng)時(shí)隙時(shí),各個(gè)節(jié)點(diǎn)聲明自身的優(yōu)先級(jí),以便中心節(jié)點(diǎn)進(jìn)行時(shí)隙分配。當(dāng)每幀的時(shí)隙數(shù)量k達(dá)到最大可分配時(shí)隙數(shù)MAX_SLOT時(shí),中心節(jié)點(diǎn)不能分配新的時(shí)隙。這時(shí)對(duì)于高優(yōu)先級(jí)節(jié)點(diǎn)發(fā)起的時(shí)隙申請(qǐng),中心節(jié)點(diǎn)將遍歷整個(gè)時(shí)隙分配表,尋找最低優(yōu)先級(jí)節(jié)點(diǎn)占有的時(shí)隙,并將該時(shí)隙分配給高優(yōu)先級(jí)節(jié)點(diǎn);對(duì)于低優(yōu)先級(jí)節(jié)點(diǎn)發(fā)起的時(shí)隙申請(qǐng),中心節(jié)點(diǎn)將不再響應(yīng),低優(yōu)先級(jí)節(jié)點(diǎn)可在若干復(fù)幀后再次發(fā)起時(shí)隙申請(qǐng)。

3 算法性能分析

歸一化吞吐量(時(shí)隙利用率)是衡量時(shí)隙分配算法性能的重要指標(biāo)。對(duì)于本文算法,當(dāng)網(wǎng)絡(luò)內(nèi)負(fù)載不平衡或網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)較多時(shí),由于固定分配算法的存在,將造成一定信道資源的浪費(fèi)?？紤]最極端的一種情況:網(wǎng)絡(luò)內(nèi)部?jī)H有一個(gè)節(jié)點(diǎn)有數(shù)據(jù)發(fā)送,分配給其他節(jié)點(diǎn)的固定時(shí)隙均無(wú)法得到利用。在這種情況下,歸一化吞吐量S應(yīng)為:

其中,k為時(shí)隙數(shù)量;n為每復(fù)幀中的幀數(shù),由網(wǎng)絡(luò)中的最大節(jié)點(diǎn)數(shù)決定。表1給出了n為20和100時(shí),數(shù)量k與歸一化吞吐量S的對(duì)應(yīng)關(guān)系。

表1 時(shí)隙數(shù)量與歸一化吞吐量的對(duì)應(yīng)關(guān)系

隨著時(shí)隙數(shù)量k的上升,固定分配時(shí)隙所占的比例逐漸降低,有效減少了由于負(fù)載不平衡造成的資源浪費(fèi)。網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)對(duì)歸一化吞吐量S影響不大。

平均時(shí)隙申請(qǐng)時(shí)延t是衡量動(dòng)態(tài)時(shí)隙分配算法性能的另一項(xiàng)重要指標(biāo)。時(shí)隙申請(qǐng)時(shí)延是指,從一般節(jié)點(diǎn)發(fā)送時(shí)隙申請(qǐng)信令到中心節(jié)點(diǎn)發(fā)送時(shí)隙分配信息信令的時(shí)間。平均時(shí)隙申請(qǐng)時(shí)延t應(yīng)滿足:

其中,k為時(shí)隙數(shù)量;n為每復(fù)幀中的幀數(shù),由網(wǎng)絡(luò)中的最大節(jié)點(diǎn)數(shù)決定。平均時(shí)隙申請(qǐng)時(shí)延t由時(shí)隙數(shù)量k和網(wǎng)絡(luò)中最大節(jié)點(diǎn)數(shù)共同影響。綜合式(3)和式(4),可得出以下結(jié)論:

(1)隨時(shí)隙數(shù)量上升,吞吐量上升,平均時(shí)隙申請(qǐng)時(shí)延上升;

(2)隨網(wǎng)絡(luò)規(guī)模上升,吞吐量基本保持不變,平均時(shí)隙申請(qǐng)時(shí)延上升。

對(duì)于USAP等固定時(shí)隙分配算法,由于時(shí)隙數(shù)量k為固定值,需要預(yù)先定義,很難取得最優(yōu)值。若時(shí)隙數(shù)量k過(guò)大,雖然可以獲得較高的吞吐量,但是帶來(lái)的負(fù)面影響是時(shí)隙申請(qǐng)時(shí)延上升,即吞吐量與時(shí)隙申請(qǐng)時(shí)延2項(xiàng)性能指標(biāo)不可兼得。而本文算法可以隨時(shí)調(diào)整時(shí)隙數(shù)量k的取值,當(dāng)網(wǎng)絡(luò)負(fù)載較小時(shí),減少時(shí)隙數(shù)量,降低時(shí)隙申請(qǐng)時(shí)延;當(dāng)網(wǎng)絡(luò)負(fù)載較大時(shí),增加時(shí)隙數(shù)量,提高吞吐量。

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

利用Matlab軟件對(duì)本文算法的歸一化吞吐量性能進(jìn)行了仿真。在仿真中,最大時(shí)隙數(shù)MAX_SLOT為100,每復(fù)幀中的幀數(shù)n與網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量相等,各個(gè)節(jié)點(diǎn)數(shù)據(jù)包的到達(dá)相互獨(dú)立。圖4給出了在10個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中,本文算法、NEBS(1∶5∶7)算法[9]、時(shí)隙ALOHA算法和理論的G-S曲線。

圖4 G-S曲線的對(duì)比

在NEBS算法中,每個(gè)幀中NE時(shí)隙與NA時(shí)隙的比為1∶7,NA時(shí)隙與D時(shí)隙的比為1∶5。在總負(fù)載G低于0.8時(shí),本文算法和NEBS算法均接近理論值;隨著總負(fù)載G的進(jìn)一步上升,NEBS算法上升變慢,歸一化吞吐量S最終穩(wěn)定于0.83附近。這是由于NA時(shí)隙與D時(shí)隙的比為1∶5,每6個(gè)時(shí)隙中有一個(gè)時(shí)隙用來(lái)進(jìn)行信道預(yù)約,因此歸一化吞吐量最高僅能達(dá)到5/6。而在本文算法中,隨著總負(fù)載G的上升,每幀時(shí)隙數(shù)變大,用于發(fā)送控制信令的時(shí)隙在所有時(shí)隙中的比例降低,當(dāng)總負(fù)載G達(dá)到1.5時(shí),歸一化吞吐量S達(dá)到0.98以上。時(shí)隙ALOHA算法的歸一化吞吐量S在總負(fù)載G為1時(shí)達(dá)到最大值,但仍然不足0.4,隨著總負(fù)載G進(jìn)一步上升,碰撞增多,歸一化吞吐量S開(kāi)始下降。

圖5給出了在10個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中2種不同算法歸一化吞吐量S隨信道負(fù)載的變化曲線。在10個(gè)節(jié)點(diǎn)中,僅有一個(gè)節(jié)點(diǎn)有數(shù)據(jù)發(fā)送,其余節(jié)點(diǎn)皆處于空閑狀態(tài)。通過(guò)控制該節(jié)點(diǎn)在不同時(shí)刻的包到達(dá)率來(lái)模擬網(wǎng)絡(luò)負(fù)載動(dòng)態(tài)變化的過(guò)程。

圖5 歸一化吞吐量隨信道負(fù)載的變化曲線

在0～250時(shí)隙范圍內(nèi),該節(jié)點(diǎn)的包到達(dá)率為0.9;在250～800時(shí)隙范圍內(nèi),該節(jié)點(diǎn)的包到達(dá)率為0.5;在800～2 000時(shí)隙范圍內(nèi),該節(jié)點(diǎn)的包到達(dá)率為0.25,在2 000時(shí)隙后,該節(jié)點(diǎn)的包到達(dá)率為0。

NAMA算法將信道資源平均分配,每個(gè)節(jié)點(diǎn)占用10%的信道帶寬。當(dāng)包到達(dá)率為0.9時(shí),10%的信道帶寬并不能滿足傳輸需求,并且整個(gè)網(wǎng)絡(luò)的歸一化吞吐量?jī)H為0.1。本文算法可以根據(jù)網(wǎng)絡(luò)負(fù)載調(diào)整幀長(zhǎng),使幀結(jié)構(gòu)適應(yīng)當(dāng)前負(fù)載,高效利用信道資源。

5 結(jié)束語(yǔ)

本文提出了一種基于TDMA的無(wú)沖突動(dòng)態(tài)時(shí)隙分配算法。通過(guò)動(dòng)態(tài)調(diào)整幀長(zhǎng)來(lái)適應(yīng)網(wǎng)絡(luò)負(fù)載的變化,進(jìn)行時(shí)隙的動(dòng)態(tài)分配和回收。在低負(fù)載時(shí),減少幀長(zhǎng),降低信道申請(qǐng)時(shí)延;在高負(fù)載時(shí),增加幀長(zhǎng),提高信道利用率。仿真結(jié)果表明,本文算法實(shí)現(xiàn)了信道資源的高效利用;同時(shí),由于本文算法采用無(wú)沖突的數(shù)據(jù)傳輸,當(dāng)負(fù)載達(dá)到飽和后,吞吐量并不會(huì)下降。本文算法為如何高效合理利用時(shí)隙資源提供了參考,改善時(shí)延性能是下一步研究的重點(diǎn)。

[1] Czapski P P.A Survey:MAC Protocols for Applications of Wireless Sensor Networks[C]//Proc.of TENCON’06.[S.l.]:IEEE Press,2006:1-4.

[2] IEEE.IEEE 802.11-1997 Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications [S].1997.

[3] 方 飛,毛玉明.時(shí)隙ALOHA二進(jìn)制指數(shù)回退算法[J].計(jì)算機(jī)應(yīng)用,2013,33(5):1203-1207.

[4] 徐圓圓,曾雋芳,劉 禹.基于Aloha算法的幀長(zhǎng)及分組數(shù)改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用,2008,28(3):588-590.

[5] 秦 勇,張 軍,張 濤.TDMA時(shí)隙分配對(duì)業(yè)務(wù)時(shí)延性能的影響分析[J].電子學(xué)報(bào),2009,37(10):2277-2283.

[6] 馬 柯,俞能海,楊福榮.EASA:一種分簇Ad Hoc網(wǎng)絡(luò)高效自適應(yīng)TDMA時(shí)隙分配算法[J].電子學(xué)報(bào), 2010,38(7):1678-1682.

[7] 任昊翔,郭達(dá)偉,邵凝寧,等.一種新型的無(wú)競(jìng)爭(zhēng)的基于TDMA的MAC協(xié)議[J].傳感技術(shù)學(xué)報(bào),2013,26 (1):89-94.

[8] Bao Lichun,Garcia-Luna-Aceves J J.A New Approach to Channel Access Scheduling for Ad Hoc Networks [C]//Proc.of the 7th Annual International Conference on Mobile Computing and Networking.[S.l.]:ACM Press,2001:210-221.

[9] Sung P,Denh S.Dynamic Control Slot Scheduling Algorithms for TDMA Based Mobile Ad Hoc Networks [C]//Proc.of Military Communications Conference. [S.l.]:IEEE Press,2008:1-7.

[10] Young C D.USAP:A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol[C]// Proc.of MILCOM’96.[S.l.]:IEEE Press,1996: 235-239.

[11] 李建勛,樊曉光,張 喆,等.基于優(yōu)先級(jí)的TDMA動(dòng)態(tài)時(shí)隙分配算法[J].計(jì)算機(jī)工程,2011,37(14): 288-290.

[12] Kanzaki A,Uemukai T,Hara T,et al.Dynamic TDMA Slot Assignment in Ad Hoc Networks[C]//Proc.of the 17th International Conference on Advanced Information Networking and Applications.[S.l.]:IEEE Press, 2003:330-335.

[13] Li Wei,WeiJibo,Wang Shan.An Evolutionary-Dynamic TDMA Slot Assignment Protocol for Ad Hoc Networks[C]//Proc.of Wireless Communications and Networking Conference.[S.l.]:IEEE Press,2007: 138-142.

編輯 任吉慧

Dynamic Slot Assignment Algorithm of Contention-avoid Based on TDMA

CUI Ke-jia,SUN Xin
(School of Electronic and Information Engineering,Beijing Jiaotong University,Beijing 100044,China)

Concerning the problem of resource waste in fixed assignment algorithm and uncertain transmission delay in contention assignment algorithm,a dynamic slot assignment algorithm of contention-avoid based on Time Division Multiple Address(TDMA)for clustered Ad Hoc network is proposed.The length of frame can be adapted to the net traffic.When the net traffic increases,the frame length increases to improve channel utilization;when the net traffic reduces,the frame length reduces to reduce the delay of accessing.It is proved by simulation results that the algorithm can increase throughput of the system,compared with NEBS and slot-ALOHA.

Time Division Multiple Address(TDMA);slot assignment algorithm;slot reuse algorithm;contentionavoid;Ad Hoc network;throughput

1000-3428(2014)10-0122-05

A

TP393

10.3969/j.issn.1000-3428.2014.10.024

北京交通大學(xué)?；鹳Y助項(xiàng)目(2012JBZ015)。

崔可嘉(1988-),男,碩士研究生,主研方向:Ad Hoc網(wǎng)絡(luò),無(wú)線接入技術(shù);孫 昕,教授。

2013-10-08

2013-11-26E-mail:ckjhljcy@126.com

中文引用格式:崔可嘉,孫 昕.基于TDMA的無(wú)沖突動(dòng)態(tài)時(shí)隙分配算法[J].計(jì)算機(jī)工程,2014,40(10):122-126.

英文引用格式:Cui Kejia,Sun Xin.Dynamic Slot Assignment Algorithm of Contention-avoid Based on TDMA[J]. Computer Engineering,2014,40(10):122-126.