馬計(jì)棟 鄭博文

1.石家莊諾通人力資源有限公司；2.中國(guó)電子科技集團(tuán)公司第五十四研究所

本文提出一種基于陣列天線的數(shù)據(jù)時(shí)隙分配算法，構(gòu)建預(yù)測(cè)數(shù)學(xué)模型，按照比例公平分配各節(jié)點(diǎn)數(shù)據(jù)時(shí)隙。實(shí)現(xiàn)無(wú)沖突預(yù)約和分配，充分利用自組織網(wǎng)絡(luò)多跳的空分復(fù)用特性，降低協(xié)議開(kāi)銷。能夠適應(yīng)網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化，網(wǎng)絡(luò)發(fā)生分割或者融合后也能夠及時(shí)調(diào)整，保證每個(gè)節(jié)點(diǎn)的數(shù)據(jù)時(shí)隙分配結(jié)果適用。兼顧數(shù)據(jù)發(fā)送的公平性，確保高優(yōu)先級(jí)數(shù)據(jù)的低時(shí)延。

自組網(wǎng)具有分布式組網(wǎng)和自組織、自恢復(fù)等功能，能夠?qū)崿F(xiàn)多跳中繼的寬帶傳輸業(yè)務(wù)，在組網(wǎng)拓?fù)浒l(fā)生變化的情況下可以自主探測(cè)拓?fù)湫畔ⅲ瑒?dòng)態(tài)選擇和確定傳輸路由信息[1]。陣列天線的自組織網(wǎng)絡(luò)中空時(shí)資源的分配，決定了網(wǎng)絡(luò)的最大帶寬和傳輸時(shí)延。本文提出一種針對(duì)陣列天線在按需分配的時(shí)隙算法基礎(chǔ)上，加入了動(dòng)態(tài)預(yù)測(cè)和比例公平分配的算法，根據(jù)不同節(jié)點(diǎn)的業(yè)務(wù)需求大小不同動(dòng)態(tài)分配時(shí)隙資源，有效利用網(wǎng)絡(luò)的空時(shí)資源[2]。

1 現(xiàn)狀

數(shù)據(jù)時(shí)隙的分配主要分為固定分配和動(dòng)態(tài)分配方式，但在移動(dòng)自組織網(wǎng)絡(luò)中，由于節(jié)點(diǎn)的移動(dòng)導(dǎo)致無(wú)法及時(shí)獲取網(wǎng)絡(luò)的拓?fù)涞葏?shù)，從而導(dǎo)致固定分配無(wú)法正確使用。而動(dòng)態(tài)分配的方式能夠解決這個(gè)問(wèn)題，尤其網(wǎng)絡(luò)參數(shù)的變化導(dǎo)致時(shí)隙分配的結(jié)果也跟隨更新，并且能夠周期性的重復(fù)操作，以適應(yīng)網(wǎng)絡(luò)的變化。

動(dòng)態(tài)分配的方式主要有以下幾種[3]：

（1）D-TDMA：在此種算法中，首先要求簇頭獲取各成員的時(shí)隙需求信息，由簇頭進(jìn)行統(tǒng)計(jì)后統(tǒng)一規(guī)劃分配。沒(méi)有進(jìn)行空間復(fù)用發(fā)，資源利用率低。

（2）P-TDMA：一個(gè)完整的時(shí)幀包括三個(gè)子幀，Claim幀用來(lái)交換一跳鄰居節(jié)點(diǎn)信息，Response幀交換二跳鄰居節(jié)點(diǎn)信息，Info幀用于傳輸業(yè)務(wù)。這種算法對(duì)新加入的節(jié)點(diǎn)不具備實(shí)時(shí)調(diào)整和接入性，限制了使用范圍[4]。

（3）FPRP：一種基于競(jìng)爭(zhēng)的全分布式算法，通過(guò)五步預(yù)留過(guò)程進(jìn)行時(shí)隙的分配。允許網(wǎng)絡(luò)內(nèi)各個(gè)節(jié)點(diǎn)做出多個(gè)預(yù)留，并且預(yù)留過(guò)程只涉及兩跳范圍內(nèi)的節(jié)點(diǎn)，發(fā)生時(shí)隙碰撞的概率低，并且對(duì)網(wǎng)絡(luò)變化的融合性較高。

（4）FCSA：一種分布式算法[5]，即每個(gè)節(jié)點(diǎn)可以根據(jù)本地信息計(jì)算自己的時(shí)隙分配，并且能夠在自己的傳輸時(shí)隙進(jìn)行無(wú)碰撞的發(fā)送數(shù)據(jù)分組。充分利用多跳網(wǎng)絡(luò)的特點(diǎn)，提高協(xié)議算法的效率。

2 設(shè)計(jì)

本文設(shè)計(jì)了一種基于陣列天線的數(shù)據(jù)時(shí)隙資源按照需求比例和數(shù)據(jù)預(yù)測(cè)結(jié)果，進(jìn)行動(dòng)態(tài)分配。提高數(shù)據(jù)時(shí)隙使用效率和網(wǎng)絡(luò)帶寬，能夠適用網(wǎng)絡(luò)拓?fù)涞募眲∽兓?/p>

2.1 時(shí)隙結(jié)構(gòu)

一個(gè)完整的時(shí)隙周期結(jié)構(gòu)(Cycle)如圖1所示，包括N個(gè)相同的時(shí)隙子序列結(jié)構(gòu)，每個(gè)時(shí)隙子序列包括預(yù)約時(shí)隙，固定廣播時(shí)隙和動(dòng)態(tài)數(shù)據(jù)時(shí)隙。在時(shí)隙子序列中，每個(gè)預(yù)約時(shí)隙包括4個(gè)預(yù)約子時(shí)隙組合(RESV1時(shí)隙和RESV2時(shí)隙)，任意兩節(jié)點(diǎn)則可以在一個(gè)周期內(nèi)通過(guò)1個(gè)預(yù)約子時(shí)隙組合來(lái)完成下一周期的動(dòng)態(tài)數(shù)據(jù)時(shí)隙的預(yù)約與分配；每個(gè)固定廣播時(shí)隙包括M個(gè)固定廣播子時(shí)隙，按照節(jié)點(diǎn)號(hào)預(yù)先固定分配給每個(gè)節(jié)點(diǎn)，進(jìn)行無(wú)沖突地發(fā)送廣播包，進(jìn)行全網(wǎng)節(jié)點(diǎn)拓?fù)湫畔⒌慕M建；每個(gè)動(dòng)態(tài)數(shù)據(jù)時(shí)隙包括8個(gè)數(shù)據(jù)子時(shí)隙，所以在每個(gè)完整時(shí)隙周期中包含128個(gè)數(shù)據(jù)時(shí)隙。

圖1 基于TDMA的MAC層接入算法時(shí)隙結(jié)構(gòu)Fig.1 Time slot structure of MAC layer access algorithm based on TDMA

2.2 數(shù)據(jù)時(shí)隙預(yù)約算法

動(dòng)態(tài)數(shù)據(jù)時(shí)隙的有效使用時(shí)間為1個(gè)完整的周期，預(yù)約結(jié)果在每個(gè)周期的初始節(jié)點(diǎn)生效，周期的結(jié)束階段被清除。首先子節(jié)點(diǎn)通過(guò)預(yù)約子時(shí)隙組合RESV1時(shí)隙向父節(jié)點(diǎn)發(fā)送本地空閑數(shù)據(jù)時(shí)隙和本地待發(fā)送業(yè)務(wù)數(shù)據(jù)包數(shù)，父節(jié)點(diǎn)收到子節(jié)點(diǎn)的數(shù)據(jù)時(shí)隙的申請(qǐng)，根據(jù)與子節(jié)點(diǎn)所通信的陣面等信息計(jì)算出有效空閑數(shù)據(jù)時(shí)隙，并統(tǒng)計(jì)子節(jié)點(diǎn)的業(yè)務(wù)數(shù)據(jù)待發(fā)包數(shù)，構(gòu)建數(shù)學(xué)模型并進(jìn)行下個(gè)周期的業(yè)務(wù)數(shù)據(jù)待發(fā)包數(shù)預(yù)測(cè)。父節(jié)點(diǎn)根據(jù)前X個(gè)周期的統(tǒng)計(jì)結(jié)果進(jìn)行X+1個(gè)周期的業(yè)務(wù)數(shù)據(jù)量預(yù)測(cè)，根據(jù)每個(gè)鄰居節(jié)點(diǎn)的預(yù)測(cè)結(jié)果把數(shù)據(jù)時(shí)隙按比例預(yù)分配，再由第X+1個(gè)周期的實(shí)際業(yè)務(wù)數(shù)量父節(jié)點(diǎn)把數(shù)據(jù)時(shí)隙分配結(jié)果通過(guò)預(yù)約子時(shí)隙組合RESV2時(shí)隙發(fā)送給子節(jié)點(diǎn)，子節(jié)點(diǎn)收到分配結(jié)果更新本地?cái)?shù)據(jù)時(shí)隙使用情況，并修改本地空閑數(shù)據(jù)時(shí)隙，數(shù)據(jù)時(shí)隙預(yù)約流程如圖2所示。

圖2 數(shù)據(jù)時(shí)隙預(yù)約流程Fig.2 Data slot reservation process

2.2.1 有效空閑時(shí)隙

在基于陣列天線的自組織網(wǎng)絡(luò)中，節(jié)點(diǎn)在數(shù)據(jù)時(shí)隙預(yù)約階段交互空閑數(shù)據(jù)時(shí)隙時(shí)，空閑時(shí)隙的提取需要根據(jù)本地信息表對(duì)數(shù)據(jù)時(shí)隙進(jìn)行篩選，實(shí)現(xiàn)資源高效利用的目的。

有效空閑時(shí)隙包括完全空閑時(shí)隙和復(fù)用空閑時(shí)隙，如圖3所示。

圖3 陣面3的有效空閑時(shí)隙Fig.3 Effective idle time slot of front 3

完全空閑時(shí)隙標(biāo)識(shí)節(jié)點(diǎn)在當(dāng)前數(shù)據(jù)時(shí)隙的所有陣面完全空閑，可按需預(yù)約為發(fā)送或接收時(shí)隙；復(fù)用空閑時(shí)隙標(biāo)識(shí)節(jié)點(diǎn)在該數(shù)據(jù)時(shí)隙與其他節(jié)點(diǎn)完成過(guò)預(yù)約過(guò)程，處于發(fā)送或接收狀態(tài)，但與目標(biāo)節(jié)點(diǎn)通信所使用的陣面仍處于空閑，可以向目標(biāo)節(jié)點(diǎn)發(fā)送或接收數(shù)據(jù)。

節(jié)點(diǎn)的復(fù)用空閑時(shí)隙需要根據(jù)實(shí)時(shí)的收發(fā)狀態(tài)區(qū)分為復(fù)用空閑接收時(shí)隙和復(fù)用空閑發(fā)送時(shí)隙。同時(shí)，節(jié)點(diǎn)的完全空閑時(shí)隙對(duì)于所有鄰居節(jié)點(diǎn)是一致的，而復(fù)用空閑時(shí)隙需要根據(jù)目標(biāo)節(jié)點(diǎn)的不同而具體計(jì)算。

2.2.2 預(yù)測(cè)數(shù)學(xué)建模

根據(jù)業(yè)務(wù)產(chǎn)生的方式和統(tǒng)計(jì)結(jié)果分析，數(shù)學(xué)建模類型可以分成兩種：線性相關(guān)預(yù)測(cè)和均值預(yù)測(cè)。因?yàn)榫殿A(yù)測(cè)對(duì)節(jié)點(diǎn)業(yè)務(wù)數(shù)據(jù)包數(shù)量的變化響應(yīng)較慢，必定增加業(yè)務(wù)的時(shí)延。線性相關(guān)預(yù)測(cè)能夠按照特定業(yè)務(wù)產(chǎn)生的數(shù)量趨勢(shì)進(jìn)行有效預(yù)測(cè)，保證了業(yè)務(wù)數(shù)據(jù)的速率平穩(wěn)變化。

通過(guò)特定線性預(yù)測(cè)算法，仿真業(yè)務(wù)數(shù)量累加的變化預(yù)測(cè)如圖，在業(yè)務(wù)產(chǎn)生的初始階段會(huì)出現(xiàn)響應(yīng)誤差，但在隨后的預(yù)測(cè)中緊跟變化趨勢(shì)。業(yè)務(wù)數(shù)據(jù)量恒定不變的情況，預(yù)測(cè)也是在初始階段出現(xiàn)誤差較大，但立刻就會(huì)進(jìn)行有效的糾偏，達(dá)到準(zhǔn)確的預(yù)測(cè)。以上兩種情況誤差都出現(xiàn)在預(yù)測(cè)的初始階段，經(jīng)分析得出由于統(tǒng)計(jì)方式及統(tǒng)計(jì)時(shí)長(zhǎng)的不同引起，預(yù)測(cè)的開(kāi)始所使用的統(tǒng)計(jì)的原始數(shù)據(jù)不完整，造成預(yù)測(cè)偏差較大，隨著統(tǒng)計(jì)數(shù)據(jù)的數(shù)量的增大，誤差也就逐漸減小。

2.2.3 數(shù)據(jù)時(shí)隙分配

自組織網(wǎng)絡(luò)中的節(jié)點(diǎn)每個(gè)周期都與鄰居進(jìn)行一次預(yù)約時(shí)隙交互，相互告知對(duì)方本地與對(duì)端的業(yè)務(wù)數(shù)據(jù)的待發(fā)數(shù)量，這些業(yè)務(wù)數(shù)據(jù)量會(huì)被統(tǒng)計(jì)到預(yù)測(cè)數(shù)學(xué)模型的源數(shù)據(jù)池，每個(gè)周期的結(jié)束前節(jié)點(diǎn)進(jìn)行下個(gè)周期每個(gè)鄰居節(jié)點(diǎn)與本節(jié)點(diǎn)的業(yè)務(wù)數(shù)據(jù)時(shí)隙所需預(yù)測(cè)S1…SN，以及本節(jié)點(diǎn)與所有鄰居節(jié)點(diǎn)的業(yè)務(wù)數(shù)據(jù)時(shí)隙所需預(yù)測(cè)X1…XM，計(jì)算出下周期本節(jié)點(diǎn)和鄰居節(jié)點(diǎn)產(chǎn)生的總業(yè)務(wù)所需時(shí)隙量S總=S1+…+SN+X1+…+XM，這樣就可以得到每個(gè)鄰居節(jié)點(diǎn)通信最多可以分配數(shù)據(jù)時(shí)隙的比例：Z1=S1/S總，…，ZN=SN/S總，節(jié)點(diǎn)與鄰居節(jié)點(diǎn)通信最多分配數(shù)據(jù)時(shí)隙的比例：Z1'=X1/S總，…，ZM'=XM/S總。根據(jù)時(shí)隙結(jié)構(gòu)的劃分，每個(gè)周期存在數(shù)據(jù)時(shí)隙的數(shù)量，便可以依據(jù)分配比例計(jì)算出每個(gè)節(jié)點(diǎn)可以獲得的最多數(shù)據(jù)時(shí)隙數(shù)量。再由預(yù)約時(shí)隙交互時(shí)獲得的當(dāng)前業(yè)務(wù)數(shù)據(jù)包數(shù)計(jì)算出實(shí)際需要的數(shù)據(jù)時(shí)隙數(shù)量，依據(jù)可獲得數(shù)據(jù)時(shí)隙數(shù)量不超過(guò)預(yù)先按照比例分配的數(shù)量進(jìn)行分配，這樣便完成每個(gè)節(jié)點(diǎn)的數(shù)據(jù)時(shí)隙的等比例分配，如圖4所示。

圖4 數(shù)據(jù)時(shí)隙預(yù)約流程Fig.4 Data slot reservation process

3 實(shí)現(xiàn)

在硬件平臺(tái)FPGA ZYNQ xcZ7100的PL端實(shí)現(xiàn)時(shí)隙結(jié)構(gòu)的劃分和運(yùn)行，在PS端兩核同時(shí)運(yùn)行，實(shí)現(xiàn)預(yù)約子時(shí)隙組合的構(gòu)建、解析、更新和業(yè)務(wù)數(shù)據(jù)的發(fā)送和接收。通過(guò)測(cè)試電腦端下發(fā)特定速率的測(cè)試包，統(tǒng)計(jì)業(yè)務(wù)出口的緩存的等待發(fā)送包數(shù)、速率和數(shù)據(jù)時(shí)隙的預(yù)約分配情況。其中事實(shí)速率如圖5所示測(cè)試速率。

圖5 測(cè)試速率Fig.5 Test rate

如圖6所示所需時(shí)隙數(shù)與實(shí)際分配時(shí)隙數(shù)比對(duì)，通過(guò)時(shí)間段15～25s的所需數(shù)據(jù)時(shí)隙和實(shí)際分配數(shù)據(jù)時(shí)隙的比對(duì)，此時(shí)間段的實(shí)際數(shù)據(jù)時(shí)隙分配數(shù)量明顯多于所需的數(shù)據(jù)時(shí)隙數(shù)量，所以速率基本穩(wěn)定在最高速率。但隨著預(yù)測(cè)誤差的抖動(dòng)，速率也會(huì)跟隨變化。

圖6 所需時(shí)隙數(shù)與實(shí)際分配時(shí)隙數(shù)比對(duì)Fig.6 Comparison of required time slots with actual allocated time slots

4 總結(jié)

通過(guò)硬件平臺(tái)的搭建測(cè)試，發(fā)現(xiàn)數(shù)據(jù)時(shí)隙的預(yù)約模型存在誤差，并且這個(gè)誤差直接影響業(yè)務(wù)速率。節(jié)點(diǎn)統(tǒng)計(jì)鄰居節(jié)點(diǎn)的業(yè)務(wù)數(shù)據(jù)包數(shù)量進(jìn)行更新預(yù)測(cè)模型，所預(yù)測(cè)得到的數(shù)據(jù)時(shí)隙的生效時(shí)間和統(tǒng)計(jì)時(shí)間存在延時(shí)，這樣導(dǎo)致預(yù)測(cè)模型的誤差變大。后期應(yīng)該考慮預(yù)測(cè)數(shù)學(xué)模型的搭建方式和優(yōu)化數(shù)據(jù)更新時(shí)間及機(jī)制，以削弱預(yù)測(cè)誤差對(duì)速率的影響。