陳　丹，劉卜華，閆茂德，李建東，李長樂

(1．長安大學(xué)電子與控制工程學(xué)院，陜西西安710064; 2．西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)絡(luò)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西西安710071)

?

MIMO Ad Hoc網(wǎng)絡(luò)中基于正交陣列的拓?fù)湮粗嘀方尤雲(yún)f(xié)議

陳丹1，2，劉卜華1，閆茂德1，李建東2，李長樂2

(1．長安大學(xué)電子與控制工程學(xué)院，陜西西安710064; 2．西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)絡(luò)理論及關(guān)鍵技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，陜西西安710071)

摘要:針對支持MIMO(Multiple Input Multiple Output)的Ad Hoc網(wǎng)絡(luò)，提出了基于正交陣列的拓?fù)湮粗嘀方尤雲(yún)f(xié)議MIMO－O－TTMA(MIMO Supported Orthogonal Array Based Topology Transparent Multiple Access)．協(xié)議利用正交陣列為節(jié)點(diǎn)分配若干時(shí)隙，在每個(gè)分配時(shí)隙中，節(jié)點(diǎn)通過與目的節(jié)點(diǎn)交互RTS/CTS(Request To Send/Clear To Send)分組來確定發(fā)送的數(shù)據(jù)流數(shù)，以機(jī)會地利用MIMO的空間復(fù)接來提升網(wǎng)絡(luò)性能．MIMO－O－TTMA在保證節(jié)點(diǎn)在一幀內(nèi)至少有一個(gè)時(shí)隙能夠無干擾地傳輸?shù)幕A(chǔ)上，允許協(xié)議的幀長能在一定的范圍內(nèi)進(jìn)行靈活選擇，從而為協(xié)議性能的優(yōu)化提供了更為有利的條件．為評估MIMO－O－TTMA的性能，利用概率方法分析了協(xié)議的吞吐量性能，數(shù)值結(jié)果表明，與已有拓?fù)湮粗狹AC(Media Access Control)相比，MIMO－O－TTMA有效提升了網(wǎng)絡(luò)吞吐量．

關(guān)鍵詞:多輸入多輸出; Ad Hoc網(wǎng)絡(luò);媒體接入控制協(xié)議;正交陣列

資助項(xiàng)目(No．2014G2320006，No．2014G3322008，No．310832151089)

1　引言

Ad Hoc網(wǎng)絡(luò)是一種由無線連接的移動節(jié)點(diǎn)所構(gòu)成的網(wǎng)絡(luò)，它不需要固定基礎(chǔ)設(shè)施的支持，具有成本低廉、易于布施的特點(diǎn)，可廣泛應(yīng)用于戰(zhàn)場、救災(zāi)、大型會議等場合．由于無線信道的開放特性和節(jié)點(diǎn)傳輸功率有限，網(wǎng)絡(luò)中節(jié)點(diǎn)獲得的信道狀態(tài)可能并不相同，這將導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)的傳輸發(fā)生沖突，影響網(wǎng)絡(luò)的性能．多址接入?yún)f(xié)議通過合理安排節(jié)點(diǎn)的傳輸來減少傳輸沖突，以期實(shí)現(xiàn)高效而公平的信道共享，它的性能直接決定著網(wǎng)絡(luò)傳輸?shù)男剩虼艘恢笔茿d Hoc網(wǎng)絡(luò)的研究熱點(diǎn)之一．

多輸入多輸出技術(shù)(MIMO)通過提供空域傳輸資源，即空間自由度DoF(Degree of Freedom)來提升傳輸性能，它能在不增加傳輸功率的前提下大幅度提高傳輸鏈路的容量或可靠性，因此獲得了廣泛的關(guān)注．從目前的應(yīng)用來看，MIMO技術(shù)主要應(yīng)用于基站、無線接入點(diǎn)AP(Access Point)等接入端設(shè)備，然而，隨著技術(shù)的發(fā)展，用戶終端配置多個(gè)天線以有效支持MIMO技術(shù)也成為必然的趨勢．對于支持MIMO的終端組成的Ad Hoc網(wǎng)絡(luò)，早在2001年就有研究開始探索MIMO對網(wǎng)絡(luò)性能的影響，并發(fā)現(xiàn)MIMO能夠提高網(wǎng)絡(luò)吞吐量、減小分組的時(shí)延抖動［1，2］．由于MIMO技術(shù)帶來了空域傳輸資源，因此即使網(wǎng)絡(luò)上層協(xié)議不進(jìn)行更改，每個(gè)鏈路傳輸速率的提升也能實(shí)現(xiàn)網(wǎng)絡(luò)吞吐量的提高．然而，文獻(xiàn)［3］中的研究表明將傳統(tǒng)的媒體接入控制(MAC)協(xié)議直接應(yīng)用于MIMO Ad Hoc網(wǎng)絡(luò)并不能充分利用MIMO的潛力，因?yàn)榫W(wǎng)絡(luò)中每個(gè)競爭區(qū)域內(nèi)的空域資源在某個(gè)時(shí)刻只能被一個(gè)節(jié)點(diǎn)使用，這導(dǎo)致空域資源沒有得到合理的分配．為了充分利用MIMO的優(yōu)勢來進(jìn)一步提升網(wǎng)絡(luò)性能，需要將競爭區(qū)域內(nèi)的空域資源分配給多個(gè)節(jié)點(diǎn)使用，因此必須設(shè)計(jì)考慮空域資源分配的MAC協(xié)議．所以對于MIMO Ad Hoc網(wǎng)絡(luò)來說，MAC協(xié)議不但要確定節(jié)點(diǎn)何時(shí)接入信道，還需要決定使用多少空間資源來傳輸，這對MAC協(xié)議的設(shè)計(jì)提出了新的挑戰(zhàn)．近些年已經(jīng)有不少學(xué)者針對MIMO Ad Hoc網(wǎng)絡(luò)設(shè)計(jì)了一些新型MAC協(xié)議，如文獻(xiàn)［3～26］．根據(jù)節(jié)點(diǎn)獲取接入機(jī)會的方式，這些MAC協(xié)議大致可以分為兩大類，即競爭型MAC和非競爭型MAC．

競爭型MAC協(xié)議中，節(jié)點(diǎn)采取某種隨機(jī)策略并結(jié)合信道的狀態(tài)來確定當(dāng)前時(shí)刻能否嘗試競爭信道，如果能競爭信道，則節(jié)點(diǎn)可以嘗試發(fā)送．文獻(xiàn)［4］中的協(xié)議在競爭時(shí)直接發(fā)送數(shù)據(jù)，然而由于數(shù)據(jù)分組較長，在發(fā)送時(shí)一旦發(fā)生沖突則會導(dǎo)致信道較長時(shí)間的無效占用．文獻(xiàn)［5］通過讓接收節(jié)點(diǎn)發(fā)送忙音來阻止隱藏節(jié)點(diǎn)發(fā)送，有效減少了沖突，但這要求節(jié)點(diǎn)裝備額外的忙音發(fā)送裝置，不能適用于普通的網(wǎng)絡(luò)節(jié)點(diǎn)．其它更多的競爭型MAC傾向于通過交互請求發(fā)送/允許發(fā)送(RTS/ CTS)分組來獲得競爭結(jié)果，進(jìn)而決定是否發(fā)送數(shù)據(jù)［6～20］．對于競爭型MAC來說，判斷信道的狀態(tài)是參與競爭的前提，然而與單天線節(jié)點(diǎn)的網(wǎng)絡(luò)不同，MIMO網(wǎng)絡(luò)中信道狀態(tài)不能僅用忙、閑來衡量，因?yàn)橹灰凶銐虻氖Ｓ嗫臻g自由度，即使周圍有鏈路正在傳輸，節(jié)點(diǎn)仍可以利用MIMO的干擾消除能力來保證自己發(fā)送的分組不干擾正在進(jìn)行的傳輸．SPACE MAC［6］、NULL MAC［7，8］、MA(MIMO Aware) MAC［9］、MIMOMAN(MIMO MAC protocol for Ad Hoc Networks)［10］和SDMA(Spatial Division Multiple Access) MAC［11］通過調(diào)整天線加權(quán)因子來實(shí)現(xiàn)干擾消除，使得節(jié)點(diǎn)在不干擾已有傳輸?shù)那闆r下能夠采用CSMA/CA(Carrier Sense Multiple Access/ Collision Avoidance)機(jī)制競爭信道進(jìn)而傳輸數(shù)據(jù)，實(shí)現(xiàn)了對競爭區(qū)域內(nèi)空間自由度的有效利用，進(jìn)而提高了吞吐量．然而，為了實(shí)現(xiàn)干擾消除，需要利用正在傳輸?shù)逆溌穬啥说墓?jié)點(diǎn)到當(dāng)前收發(fā)節(jié)點(diǎn)的等效信道估計(jì)結(jié)果來設(shè)置天線加權(quán)因子，這要求多對收發(fā)節(jié)點(diǎn)必須處于一跳范圍內(nèi)，因此上述幾種利用干擾消除的協(xié)議僅適用于一跳網(wǎng)絡(luò)．為了使協(xié)議能廣泛適用于多跳網(wǎng)絡(luò)，可以不考慮MIMO的干擾消除，雖然這導(dǎo)致節(jié)點(diǎn)不能在周圍有鏈路傳輸時(shí)競爭信道，但仍可以通過利用MIMO的空間復(fù)接來提升網(wǎng)絡(luò)性能．MIMA(Mitigating Interference using Multiple Antennas) MAC［12］、MIMA/AS(Mitigating Interference using Multiple Antennas with Antenna Selection) MAC［13］及文獻(xiàn)［14，15］中的MAC協(xié)議考慮利用MIMO空間復(fù)接來實(shí)現(xiàn)相距兩跳節(jié)點(diǎn)的同時(shí)傳輸，并且它們采用相似的時(shí)間結(jié)構(gòu)，將時(shí)間軸劃分為一個(gè)個(gè)時(shí)隙，每個(gè)時(shí)隙又劃分出了信道競爭階段和數(shù)據(jù)傳輸階段，其中信道競爭階段的長度足夠進(jìn)行多次RTS/CTS的交互．網(wǎng)絡(luò)節(jié)點(diǎn)在信道競爭階段通過載波偵聽和隨機(jī)退避來確定何時(shí)競爭信道，并通過交互RTS/CTS來確定競爭成功與否．如果競爭成功，則節(jié)點(diǎn)在數(shù)據(jù)傳輸階段利用較少的固定數(shù)量的空間數(shù)據(jù)流來發(fā)送數(shù)據(jù)，雖然這有利于減少沖突，但在競爭區(qū)域內(nèi)僅有1個(gè)發(fā)送節(jié)點(diǎn)競爭成功時(shí)僅利用較少的固定數(shù)量的數(shù)據(jù)流顯然會浪費(fèi)一些空間自由度．PRP(Parallel RTS Processing) MAC［16］針對這一問題調(diào)整了RTS/CTS交互的順序，允許接收節(jié)點(diǎn)額外等待一個(gè)RTS子時(shí)隙后再回復(fù)CTS分組，這樣接收節(jié)點(diǎn)可以根據(jù)收到的RTS的數(shù)量(1個(gè)或2個(gè))以及其目的節(jié)點(diǎn)來確定允許發(fā)送節(jié)點(diǎn)使用多少空間數(shù)據(jù)流來傳輸數(shù)據(jù)，然后將該數(shù)值攜帶在CTS中回復(fù)給發(fā)送節(jié)點(diǎn)．通過動態(tài)確定發(fā)送使用的空間數(shù)據(jù)流的數(shù)量，PRP MAC充分利用了MIMO的空間復(fù)接．另外一些競爭型MAC［17～20］考慮了對服務(wù)質(zhì)量QoS(Quality of Service)的支持，通過業(yè)務(wù)優(yōu)先級和分組排隊(duì)時(shí)間確定出節(jié)點(diǎn)優(yōu)先級，進(jìn)而決定節(jié)點(diǎn)接入信道的概率．然后節(jié)點(diǎn)依接入概率在當(dāng)前時(shí)隙的信道競爭階段與目的節(jié)點(diǎn)交互RTS/CTS分組，確定發(fā)送使用的空間數(shù)據(jù)流的數(shù)量并在數(shù)據(jù)傳輸階段發(fā)送數(shù)據(jù)．由于同時(shí)考慮了業(yè)務(wù)和排隊(duì)的因素以及MIMO的空間復(fù)接，這些協(xié)議能夠在提供區(qū)分服務(wù)的基礎(chǔ)上最大化鏈路傳輸速率，實(shí)現(xiàn)高效傳輸．

非競爭型MAC一般也采用劃分時(shí)隙的時(shí)間結(jié)構(gòu)，但節(jié)點(diǎn)通常不能獨(dú)立決策接入信道的時(shí)機(jī)，而需要利用網(wǎng)絡(luò)局部或全局的某些信息來確定時(shí)隙和空間自由度的分配．文獻(xiàn)［17～21］中提出了一些集中式時(shí)-空分配方案，它們利用全局網(wǎng)絡(luò)拓?fù)湫畔?，將時(shí)-空分配建模為競爭圖著色問題或整數(shù)線性規(guī)劃問題，然而這些問題都是NP(non-deterministic polynomial) -hard問題，其最優(yōu)解只能通過搜索方法獲得，復(fù)雜度較高，因此這些分配方案僅用作基準(zhǔn)來評估各自文中分布式協(xié)議．為了降低時(shí)-空分配的復(fù)雜度，文獻(xiàn)［22～24］提出了一些啟發(fā)式方法，其中文獻(xiàn)［22］僅考慮了時(shí)隙的分配，而在分配時(shí)隙中節(jié)點(diǎn)將以全部空間數(shù)據(jù)流發(fā)送，雖然這樣做有利于簡化分配的過程，但卻沒有能夠機(jī)會地利用空間復(fù)接;文獻(xiàn)［23，24］則提出了時(shí)-空聯(lián)合的啟發(fā)式分配方法，它們考慮在空間自由度的約束下盡量為相距兩跳的節(jié)點(diǎn)分配相同的時(shí)隙，以便將空域資源分配給競爭區(qū)域內(nèi)多個(gè)節(jié)點(diǎn)，從而可以充分利用MIMO的空間自由度．雖然啟發(fā)式的分配方法依然使用了全局拓?fù)湫畔ⅲ渲匾囊饬x在于，它以較低的復(fù)雜度給出了相對較緊的性能上界，可以廣泛地用來評估其它MAC的性能，并為協(xié)議的改進(jìn)提供一些依據(jù)．另外一些非競爭型MAC［25，26］僅利用網(wǎng)絡(luò)最大度和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)這兩個(gè)參數(shù)，而無需具體的全局網(wǎng)絡(luò)拓?fù)渚涂梢栽O(shè)計(jì)時(shí)隙分配方案，這類MAC協(xié)議稱為拓?fù)湮粗狹AC．在獲得了網(wǎng)絡(luò)的兩個(gè)參數(shù)后，拓?fù)湮粗狹AC可以利用有限域等數(shù)學(xué)方法構(gòu)造出若干時(shí)隙組，然后隨機(jī)地為每個(gè)節(jié)點(diǎn)關(guān)聯(lián)一個(gè)時(shí)隙組就完成了時(shí)隙的分配．協(xié)議中所有時(shí)隙被組織成幀，在每幀中，節(jié)點(diǎn)可以在分配的各時(shí)隙與目的節(jié)點(diǎn)交互RTS/CTS以確定使用多少空間數(shù)據(jù)流來發(fā)送，進(jìn)而發(fā)送數(shù)據(jù)．由于僅利用了網(wǎng)絡(luò)參數(shù)，拓?fù)湮粗狹AC仍不能避免RTS分組發(fā)生沖突，然而，它可以保證在一幀中至少有1個(gè)時(shí)隙可以成功交互，因此，分組的最大時(shí)延可以被限制在一定范圍內(nèi)．

從上述已有的研究來看，針對MIMO Ad Hoc網(wǎng)絡(luò)的MAC協(xié)議中，競爭型MAC占據(jù)了較大的比例，并且近期的一些研究已經(jīng)考慮了對QoS的支持，使競爭型MAC已趨近于完善．非競爭型MAC中，集中式分配要求網(wǎng)絡(luò)節(jié)點(diǎn)要交互較多的拓?fù)湫畔?，這導(dǎo)致網(wǎng)絡(luò)開銷過大，故其并不適合用作實(shí)際的協(xié)議．比較而言，拓?fù)湮粗狹AC不依賴網(wǎng)絡(luò)具體拓?fù)?，具有開銷小、易于實(shí)現(xiàn)的特點(diǎn)，而且目前支持MIMO的拓?fù)湮粗狹AC研究還較少，因此仍值得進(jìn)行進(jìn)一步探索．考察現(xiàn)有的拓?fù)湮粗狹AC協(xié)議MIMO－TTR(MIMO supported Topology Transparent Reservation)［25，26］，其協(xié)議幀長為q2，其中q與網(wǎng)絡(luò)最大度和節(jié)點(diǎn)數(shù)有關(guān)且僅能取素?cái)?shù)或素?cái)?shù)冪，當(dāng)網(wǎng)絡(luò)的兩個(gè)參數(shù)變大時(shí)，q受素?cái)?shù)(冪)的約束可能呈現(xiàn)跳躍式增大，幀長q2也將快速增長，這會導(dǎo)致網(wǎng)絡(luò)吞吐量迅速下降．針對這一問題，本文將利用新的方法來構(gòu)造時(shí)隙組，使協(xié)議幀長能更靈活地進(jìn)行選擇，以保持較高的吞吐量．文中的主要貢獻(xiàn)總結(jié)如下:

(1)針對MIMO Ad Hoc網(wǎng)絡(luò)，提出了基于正交陣列的拓?fù)湮粗狹AC協(xié)議MIMO－O－TTMA．MIMO－O－TTMA利用正交陣列構(gòu)造和分配時(shí)隙組，在分配時(shí)隙中，節(jié)點(diǎn)將通過交互RTS/CTS分組來確定發(fā)送使用的數(shù)據(jù)流數(shù)．與已有的研究相比，利用正交陣列構(gòu)造時(shí)隙組的優(yōu)勢在于協(xié)議的幀長可以由兩個(gè)參數(shù)之積k×s來確定，這里s由網(wǎng)絡(luò)最大度和節(jié)點(diǎn)數(shù)共同決定，而k可以在(網(wǎng)絡(luò)最大度，s + 1］這一區(qū)間內(nèi)任意取值，因此協(xié)議的幀長也可以在一定范圍內(nèi)進(jìn)行靈活地選擇，從而為網(wǎng)絡(luò)吞吐量的優(yōu)化提供了有利的條件．

(2)利用概率方法分析了網(wǎng)絡(luò)中任意鏈路的吞吐量．文獻(xiàn)［25，26］中對MIMO－TTR的性能分析是最壞情況下的吞吐量，而本文考慮了不同情況下鏈路的吞吐量，并依各情況發(fā)生的概率對吞吐量進(jìn)行加權(quán)而獲得了平均吞吐量，這樣的結(jié)果更趨近于網(wǎng)絡(luò)一般狀況下的性能．同時(shí)，本文還給出了優(yōu)選參數(shù)k的方法，即以最大化平均吞吐量為準(zhǔn)則通過搜索來獲得k值，實(shí)現(xiàn)了協(xié)議參數(shù)的最優(yōu)化．

2　MIMO模型和網(wǎng)絡(luò)模型

MIMO有兩種提升傳輸性能的方式，即空間分集(Spatial Diversity)和空間復(fù)接(Spatial Multiplexing)，其中空間分集能夠提升接收端平均信噪比，進(jìn)而提高傳輸可靠性;而空間復(fù)接能夠并行傳輸多個(gè)獨(dú)立的數(shù)據(jù)流，進(jìn)而提高傳輸?shù)乃俾剩疚闹袃H考慮MIMO的空間復(fù)接．假設(shè)發(fā)送端和接收端天線數(shù)均為M，則發(fā)送端或接收端至多可以發(fā)送或接收M個(gè)數(shù)據(jù)流．當(dāng)發(fā)送端發(fā)送的數(shù)據(jù)流到達(dá)接收端后，接收機(jī)可以根據(jù)數(shù)據(jù)流不同的空間特征將數(shù)據(jù)流分離．點(diǎn)對點(diǎn)鏈路中，為了最大化鏈路傳輸速率，通常期望用所有的M個(gè)數(shù)據(jù)流來傳輸;而在網(wǎng)絡(luò)中，傳輸鏈路由于會受到附近其它鏈路的干擾，可能需要采用與點(diǎn)對點(diǎn)鏈路不同的傳輸方案．考慮圖1所示的網(wǎng)絡(luò)，假設(shè)兩個(gè)鏈路A→B和C→D要進(jìn)行傳輸，如果A和C各自發(fā)送M個(gè)數(shù)據(jù)流，則到達(dá)接收節(jié)點(diǎn)的數(shù)據(jù)流有2M個(gè)，超過了接收能力，因此傳輸會發(fā)生沖突．如果A和C各自發(fā)送M/2個(gè)數(shù)據(jù)流，則到達(dá)接收節(jié)點(diǎn)的數(shù)據(jù)流恰好M個(gè)，這樣兩個(gè)鏈路既不發(fā)生傳輸沖突，接收節(jié)點(diǎn)處的空間自由度也獲得了充分的利用．為了描述簡便，下文中稱這種多個(gè)相互干擾的鏈路各自以較少數(shù)據(jù)流同時(shí)傳輸?shù)姆桨笧闄C(jī)會利用空間復(fù)接的傳輸方案．除了能有效減少網(wǎng)絡(luò)中傳輸沖突以后，機(jī)會地利用空間復(fù)接還有可能提高數(shù)據(jù)流的傳輸速率，如對于圖1中的兩個(gè)鏈路，由于每個(gè)鏈路僅傳輸M/2個(gè)數(shù)據(jù)流，則發(fā)送節(jié)點(diǎn)可以選擇等效信道增益較高的M/2個(gè)天線來發(fā)送，因此每個(gè)數(shù)據(jù)流的傳輸速率也相對較高．考慮更為一般的情況，假設(shè)存在l個(gè)相互干擾鏈路，為了機(jī)會地利用空間復(fù)接，每個(gè)鏈路應(yīng)使用M/l個(gè)數(shù)據(jù)流傳輸．

考慮節(jié)點(diǎn)具有M個(gè)天線的Ad Hoc網(wǎng)絡(luò)，假設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)間鏈路對稱，則網(wǎng)絡(luò)用無向圖G(V，E)來表示，其中V是所有節(jié)點(diǎn)的集合，E是所有鏈路的集合．令Nu表示u的鄰節(jié)點(diǎn)的集合，則Nu= { w|u，w∈V，(u，w)∈E}，節(jié)點(diǎn)u的度為D(u) = | Nu|．假設(shè)沖突是導(dǎo)致傳輸失敗的唯一原因，這里的沖突包含兩種類型，第一類沖突是由于無線節(jié)點(diǎn)不能同時(shí)收發(fā)造成的，即對于某一傳輸u→v(u∈V，v∈Nu)，如果v同時(shí)發(fā)送分組則節(jié)點(diǎn)v處發(fā)生第一類沖突;第二類沖突是由于周圍節(jié)點(diǎn)發(fā)送的數(shù)據(jù)流數(shù)超過了接收節(jié)點(diǎn)的接收能力而造成的，即對于傳輸u→v(u∈V，v∈Nu)，如果Nv(包括u)中的節(jié)點(diǎn)同時(shí)發(fā)送的數(shù)據(jù)流之和大于M，則節(jié)點(diǎn)v處發(fā)生第二類沖突．由以上的描述可以看出，對于傳輸u →v，v和Nv－{ u}中的元素可能導(dǎo)致u→v傳輸失敗，因此稱Nv∪{ v}－{ u}為u→v的干擾節(jié)點(diǎn)集，其中稱v為第一類干擾節(jié)點(diǎn)，Nv－{ u}中的節(jié)點(diǎn)為第二類干擾節(jié)點(diǎn)．

3　協(xié)議描述

(1)每個(gè)節(jié)點(diǎn)分配k個(gè)時(shí)隙，即|Su| = k．

(3)節(jié)點(diǎn)分配的時(shí)隙數(shù)k＞c×Dmax．具體來說，對傳輸u→v(u∈V，v∈Nu)，由于節(jié)點(diǎn)v至多有Dmax個(gè)鄰節(jié)點(diǎn)，u→v的干擾節(jié)點(diǎn)集Nv∪{ v}－{ u}中也至多包含Dmax個(gè)節(jié)點(diǎn)，而每干擾節(jié)點(diǎn)至多與u 有c個(gè)相同的時(shí)隙，則所有干擾節(jié)點(diǎn)至多與u有c× Dmax個(gè)相同的時(shí)隙，因此當(dāng)節(jié)點(diǎn)u的時(shí)隙數(shù)k＞c×Dmax時(shí)，u→v在一幀中至少有一個(gè)時(shí)隙可以無干擾傳輸，由v的任意性可知，節(jié)點(diǎn)u在一幀中至少有一個(gè)時(shí)隙可以無干擾傳輸．

由以上的描述可以看到，構(gòu)造滿足三個(gè)條件的時(shí)隙組Su(u =1，2，…，N)是設(shè)計(jì)拓?fù)湮粗嘀方尤雲(yún)f(xié)議的關(guān)鍵．本文中將利用正交陣列來構(gòu)造滿足條件的Su(u =1，2，…，N)，進(jìn)而設(shè)計(jì)支持MIMO的拓?fù)湮粗嘀方尤雲(yún)f(xié)議．下面首先介紹正交陣列的相關(guān)概念．

定義1［27］對于由s個(gè)符號組成的k×st(0≤t≤k)矩陣A，如果在A的任一t×st子矩陣中，任一長為t的符號排列恰好在1個(gè)列中出現(xiàn)，稱A為水平s，強(qiáng)度t(0 ≤t≤k)的正交陣列，記為OA(t，k，s)．

表1中給出了正交陣列OA(2，4，3)的例子，其中3個(gè)符號分別是0，1，2．任意取矩陣中的兩行，如第一和第二行來組成2×9的子陣，記此子陣為A'．長度為2的符號排列共有9個(gè)，分別是(0，0)，(0，1)，(0，2)，(1，0)，(1，1)，(1，2)，(2，0)，(2，1)，(2，2)，可以看到，每個(gè)排列恰好在A'的列中出現(xiàn)了一次．

表1　正交陣列OA(2，4，3)

由正交陣列的定義可以知道，矩陣任意兩列中至多有t－1行的元素相同［27］，以表1中的OA(2，4，3)為例，取任意兩列，它們至多有2－1 =1行的元素相同，如第一列和第三列中僅第四行元素相同．利用這一性質(zhì)，將矩陣的每列元素映射為一個(gè)時(shí)隙組，則由任意兩列元素映射的兩個(gè)集合可能滿足至多有c個(gè)相同的時(shí)隙，再考慮到網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)N和最大度Dmax，則如果有正交陣列OA(t，k，s)滿足stN，k＞(t－1)×Dmax，即可構(gòu)造滿足條件的時(shí)隙組Su(u =1，2，…，N)．具體來說，記OA (t，k，s)的第i行、第j列元素為aij，將aij映射為時(shí)隙tij，映射規(guī)則為

由式(1)中的映射規(guī)則可以看到:

(1)最大時(shí)隙序號為tij= (k－1)×s + (s－1) + 1 = k×s，即協(xié)議的幀長為k×s．

(2)時(shí)隙的確定僅與行號和元素本身有關(guān)，因此對于OA(t，k，s)的任意兩列(如第m列和第n列)，僅當(dāng)同一行的兩個(gè)元素相同時(shí)，這兩個(gè)元素才會映射到同一時(shí)隙，而由于OA(t，k，s)第m列和第n列中至多有t －1行的元素相同，映射得到的時(shí)隙組Tm，Tn(1≤m，n ≤st，m≠n)也至多有t－1個(gè)相同的時(shí)隙．

由OA(t，k，s)第j列的k個(gè)元素映射可以得到k個(gè)時(shí)隙，記其集合為Tj，有Tj= { tij|1≤i≤k}．由于OA(t，k，s)共有st個(gè)列，因此可以得到st個(gè)時(shí)隙組．stN保證了每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)都有唯一的時(shí)隙組，k＞(t－1)×Dmax則保證了節(jié)點(diǎn)在一幀中有無干擾傳輸?shù)臅r(shí)隙．在分配時(shí)隙組時(shí)，只需要從st個(gè)集合中任意取出N個(gè)集合，并隨機(jī)地分配給網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)，則節(jié)點(diǎn)的時(shí)隙組Su(u =1，2，…，N)可以滿足拓?fù)湮粗獏f(xié)議需要的條件．

下面以圖2(a)中的網(wǎng)絡(luò)為例來說明如何分配時(shí)隙．對于圖中所示的網(wǎng)絡(luò)，節(jié)點(diǎn)數(shù)N = 8，Dmax= D(B) = 3．由表1中正交陣列的參數(shù)知，st=32=9，k =4，恰好滿足stN，k＞(t－1)×Dmax，因此可以利用表1的OA (2，4，3)來構(gòu)造時(shí)隙組．由表中OA(2，4，3)各列映射得到的時(shí)隙組如表2，可以看到，協(xié)議幀長為k×s = 4×3 =12．從表2中這9個(gè)時(shí)隙組中任意選擇7個(gè)分配給各個(gè)節(jié)點(diǎn)，這里取表中Ti(i = 1，2，3，4，5，6，7)，并按照下標(biāo)由小到大的順序依次分配給節(jié)點(diǎn)A～G．圖2(b)中給出了直觀的時(shí)隙分配結(jié)果，從圖中可以看出，節(jié)點(diǎn)G的時(shí)隙中包含時(shí)隙12，此時(shí)隙只有節(jié)點(diǎn)G占用，顯然能夠無干擾地傳輸;節(jié)點(diǎn)A與F相距三跳，彼此不可能是對方鏈路的干擾節(jié)點(diǎn)，因此在時(shí)隙4中，節(jié)點(diǎn)A和節(jié)點(diǎn)F可以無干擾地傳輸，同樣節(jié)點(diǎn)D、E的無干擾傳輸時(shí)隙分別為1、11．對于節(jié)點(diǎn)B而言，無論其目的節(jié)點(diǎn)是鄰節(jié)點(diǎn)中哪一個(gè)，也總能找到無干擾傳輸?shù)臅r(shí)隙，如B→A 和B→C的無干擾時(shí)隙是2，B→E為5，類似的，節(jié)點(diǎn)C與任一鄰節(jié)點(diǎn)的鏈路也存在無干擾時(shí)隙，其中C→B和C→D為3，C→F為9．總結(jié)上述的時(shí)隙分配結(jié)果可見，網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都至少具有了一個(gè)可以無干擾傳輸?shù)臅r(shí)隙．上述時(shí)隙分配結(jié)果通過每幀重復(fù)，可以保證每個(gè)節(jié)點(diǎn)在一幀中有一個(gè)無干擾傳輸?shù)臅r(shí)隙．

觀察圖2(b)中的時(shí)隙分配結(jié)果可以發(fā)現(xiàn)，某些鏈路的發(fā)送節(jié)點(diǎn)和第二類干擾節(jié)點(diǎn)分配在了相同的時(shí)隙，如對于B→C，節(jié)點(diǎn)B與第二類干擾節(jié)點(diǎn)D都分配了時(shí)隙5，如果B和D同時(shí)用全部的M個(gè)數(shù)據(jù)流傳輸，則B→C和D→C的傳輸會因第二類沖突而失敗，而考慮機(jī)會地利用MIMO的空間復(fù)接，即節(jié)點(diǎn)B和D各自以M/2個(gè)數(shù)據(jù)流發(fā)送分組，則B和D各自發(fā)送的分組都可以成功地被節(jié)點(diǎn)C接收到．為了能夠機(jī)會地利用MIMO的空間復(fù)接來改善網(wǎng)絡(luò)性能，本協(xié)議中進(jìn)一步將每個(gè)時(shí)隙劃分成4個(gè)子時(shí)隙，即RTS、CTS、DATA、ACK (ACKnowledgement)子時(shí)隙，其中除了DATA外的其它子時(shí)隙稱為控制子時(shí)隙，控制子時(shí)隙中分組都以1個(gè)數(shù)據(jù)流發(fā)送，以減少沖突．在RTS和CTS子時(shí)隙，節(jié)點(diǎn)通過交互RTS/CTS分組可以確定發(fā)送DATA分組使用的數(shù)據(jù)流數(shù)，這樣互為第二類干擾節(jié)點(diǎn)的多個(gè)節(jié)點(diǎn)可能同時(shí)傳輸DATA分組且能成功被目的節(jié)點(diǎn)接收到，從而有效提高了網(wǎng)絡(luò)吞吐量．

表2　OA(2，4，3)映射得到的時(shí)隙組

下面給出完整的協(xié)議描述，為了方便，稱提出的協(xié)議為MIMO－O－TTMA．考慮到t3時(shí)OA(t，k，s)的性質(zhì)較為復(fù)雜，因此將利用OA(2，k，s)來構(gòu)造時(shí)隙組．

由文獻(xiàn)［27］知，當(dāng)s為素?cái)?shù)冪時(shí)，OA(2，s + 1，s)存在，并且OA(2，k，s) (k≤s)可以由OA(2，s +1，s)刪去s +1－k行得到．因此對于具有N個(gè)節(jié)點(diǎn)且最大度為Dmax的網(wǎng)絡(luò)，尋找滿足s2N和s + 1＞Dmax的最小素?cái)?shù)s，并按文獻(xiàn)［28］中的Bush方法構(gòu)造OA(2，s +1，s)，然后取k為滿足Dmax＜k≤s +1且保證吞吐量最大的某一值．根據(jù)式(1)的映射規(guī)則將OA(2，k，s)的每個(gè)列映射為一個(gè)時(shí)隙組，然后從s2個(gè)時(shí)隙組中任意選出N個(gè)并隨機(jī)地分配給每個(gè)節(jié)點(diǎn)．記任一節(jié)點(diǎn)u(u = 1，2，…，N)的時(shí)隙組為Su，當(dāng)前時(shí)隙為t，網(wǎng)絡(luò)節(jié)點(diǎn)在各子時(shí)隙的行為為:

(1) RTS子時(shí)隙

如果t∈Su(u = 1，2，…，N)，節(jié)點(diǎn)u在這個(gè)子時(shí)隙以1個(gè)數(shù)據(jù)流向目的節(jié)點(diǎn)v(v∈Nu)發(fā)送RTS分組并等待回復(fù);如果t?Su，節(jié)點(diǎn)u保持接收狀態(tài)．

(2) CTS子時(shí)隙

收到RTS分組的節(jié)點(diǎn)v根據(jù)RTS的數(shù)量及其目的節(jié)點(diǎn)來確定允許發(fā)送節(jié)點(diǎn)使用多少數(shù)據(jù)流傳輸DATA分組，具體來說，如果節(jié)點(diǎn)v收到了l(l∈{ 1，2，…，M} )個(gè)RTS且其目的節(jié)點(diǎn)都是v，則允許每個(gè)發(fā)送節(jié)點(diǎn)用M/l個(gè)數(shù)據(jù)流發(fā)送DATA;如果節(jié)點(diǎn)v收到了l(l∈{ 1，2，…，M} )個(gè)RTS，其中l(wèi)'(0＜l'＜l)個(gè)RTS的目的節(jié)點(diǎn)是v，則允許l'個(gè)發(fā)送節(jié)點(diǎn)各自以1個(gè)數(shù)據(jù)流發(fā)送DATA．節(jié)點(diǎn)v將允許使用的數(shù)據(jù)流數(shù)及l(fā)'個(gè)發(fā)送節(jié)點(diǎn)地址攜帶在CTS分組當(dāng)中，然后以1個(gè)數(shù)據(jù)流向發(fā)送節(jié)點(diǎn)回復(fù)CTS分組．

(3) DATA子時(shí)隙

收到目的節(jié)點(diǎn)v的CTS分組后，節(jié)點(diǎn)u查看允許發(fā)送的數(shù)據(jù)流數(shù)，然后用相應(yīng)的數(shù)據(jù)流數(shù)來發(fā)送DATA分組，并等待目的節(jié)點(diǎn)的確認(rèn)．

(4) ACK子時(shí)隙

目的節(jié)點(diǎn)v如果成功收到各發(fā)送節(jié)點(diǎn)的DATA分組，則以1個(gè)數(shù)據(jù)流向各發(fā)送節(jié)點(diǎn)回復(fù)ACK分組，以確認(rèn)分組成功傳輸．

4　性能分析

首先介紹性能分析中會用到的關(guān)于OA(2，k，s)的一些性質(zhì)．

正交陣列OA(t，k，s)中，每個(gè)列也被稱為一個(gè)碼字［27］，記OA(t，k，s)的第j(1≤j≤s2)個(gè)列為碼字Wj．如果碼字Wj第i行元素aij和碼字Wj'相同行的元素aij'滿足aij= aij'(j≠j')，稱碼字Wj與碼字Wj'相交(intersect)于位置i［27］．對于OA(2，k，s)中的任一碼字Wj，其它碼字與Wj的關(guān)系滿足［27］:

(1) Wj'(1≤j≤s2，j'≠j)可能與Wj相交于0個(gè)或1個(gè)位置(因t =2)．

(2)與Wj相交于某個(gè)特定位置的碼字?jǐn)?shù)量為s－1．

(3)由于每個(gè)碼字有k行，因此與Wj相交于1個(gè)位置的碼字?jǐn)?shù)量為

(4)與Wj相交于0個(gè)位置的的碼字?jǐn)?shù)量為s2－1－k(s－1) = (s－1) (s +1－k)．

本文中以吞吐量為指標(biāo)考察協(xié)議性能，這里，吞吐量定義為平均每個(gè)時(shí)隙發(fā)送的數(shù)據(jù)流數(shù)．下面將分析任一傳輸u→v的吞吐量．與文獻(xiàn)［25，26］類似，本文僅分析所有鄰節(jié)點(diǎn)都向v發(fā)送數(shù)據(jù)且網(wǎng)絡(luò)處于重負(fù)荷下的吞吐量．對于MIMO－O－TTMA，節(jié)點(diǎn)的時(shí)隙組是由OA(2，k，s)的碼字映射得到的，因此可以根據(jù)干擾節(jié)點(diǎn)的碼字得到u→v無干擾傳輸?shù)臅r(shí)隙數(shù)以及干擾時(shí)隙中可能發(fā)送的數(shù)據(jù)流數(shù)，進(jìn)而獲得u→v的吞吐量．

對于傳輸u→v，如果v的度為D(v)，則u→v的干擾節(jié)點(diǎn)數(shù)為D(v)，記節(jié)點(diǎn)u、v的碼字為Wu、Wv，由OA (2，k，s)的性質(zhì)知，Wv與Wu可能相交于0或1個(gè)位置，而這決定了u→v的傳輸是否會發(fā)生第一類沖突，因此下面分兩種情況來討論u→v的吞吐量．

(1) Wv與Wu相交于1個(gè)位置

Wv與Wu相交于1個(gè)位置時(shí)，u→v的傳輸會在某個(gè)時(shí)隙中發(fā)生第一類沖突．由于OA(2，k，s)中除Wu外共有s2－1個(gè)碼字，其中與Wu相交于1個(gè)位置的碼字?jǐn)?shù)量k(s－1)，則Wv與Wu相交于1個(gè)位置的概率為

當(dāng)所有干擾節(jié)點(diǎn)的碼字的并集與Wu相交于w個(gè)位置時(shí)，表明u→v的傳輸在w個(gè)時(shí)隙中存在干擾，在其余k－w個(gè)時(shí)隙無干擾．在w個(gè)存在干擾的時(shí)隙中，有1個(gè)時(shí)隙發(fā)生了第一類沖突(因Wv與Wu相交于1個(gè)位置)，在該時(shí)隙中u→v的傳輸必然失敗，其它w－1個(gè)時(shí)隙中u→v的傳輸可能成功或發(fā)生第二類沖突．

Wv與Wu相交于位置i(1≤i≤k)的條件下，所有干擾節(jié)點(diǎn)碼字的并集與Wu相交于w個(gè)特定位置的概率記為，為了得到，需要獲取干擾節(jié)點(diǎn)選擇碼字的情況．這里利用生成函數(shù)來表征干擾節(jié)點(diǎn)選擇碼字情況，生成函數(shù)的原型為［27］

其中xi的系數(shù)的含義是:選擇i個(gè)碼字使其并集與Wu相交于w個(gè)特定位置，選法共有C(w)i種．利用這一原型，可以構(gòu)造合適的生成函數(shù)．由于文獻(xiàn)［27］中已經(jīng)給出了生成函數(shù)構(gòu)造的詳細(xì)過程，這里不再贅述，僅給出表達(dá)式．構(gòu)造出的三個(gè)生成函數(shù)分別是:

其中Dj、、Fn的含義分別為: (a) Dj:除Wv外，與Wu相交于位置i的碼字有s－2個(gè)，從這些碼字中選擇j個(gè)，選法有Dj種．

(c) Fn:與Wu相交于0個(gè)位置的碼字共有(s－1) (s +1－k)個(gè)，從這些碼字中選擇n個(gè)，選法有Fn種．

其中第一個(gè)求和號的上限min(max(0，D(v)－1－(w－ 1) )，s－2)可以解釋如下:由于定義了碼字相交位置數(shù)為w，而任意兩個(gè)碼字至多相交于1個(gè)位置，因此除Wv外至少還需要w－1個(gè)碼字，如果第二類干擾節(jié)點(diǎn)數(shù)D(v)－1≤w－1，則第二類干擾節(jié)點(diǎn)不會選擇與Wu相交于位置i的碼字，即j只能為0，因此有max(0，D (v)－1－(w－1) )，而此值與s－2取小是因?yàn)榕cWu相交于位置i的碼字除去Wv外只有s－2個(gè)．

除Wv和Wu外還有s2－2個(gè)碼字，因此除v外的其它D(v)－1個(gè)干擾節(jié)點(diǎn)任意選擇碼字時(shí)，選法的數(shù)量為

因此有

由于每個(gè)碼字有k個(gè)位置，除了位置i外，Wu還有k－1個(gè)位置，從這些位置中任選w－1個(gè)，選法數(shù)量為

計(jì)算吞吐量之前，定義如下的符號:

(Ⅳ) T1: Wv與Wu相交于1個(gè)位置時(shí)，u→v的吞吐量．

其中ks表示協(xié)議幀長．

由式(12)和式(13)，可以得到

由于Wu共有k個(gè)位置，因此

(2) Wv與Wu相交于0個(gè)位置

Wv與Wu相交于0個(gè)位置時(shí)，u→v的傳輸不會發(fā)生第一類沖突．由于OA(2，k，s)中除Wu外共有s2－1個(gè)碼字，其中與Wu相交于0個(gè)位置的碼字?jǐn)?shù)量(s－1) (s +1－k)，則Wv與Wu相交于0個(gè)位置的概率為

當(dāng)所有干擾節(jié)點(diǎn)的碼字的并集與Wu相交于w個(gè)位置時(shí)，表明u→v的傳輸在w個(gè)時(shí)隙中存在干擾，在其余k－w個(gè)時(shí)隙無干擾．由于Wv與Wu相交于0個(gè)位置，僅第二類干擾節(jié)點(diǎn)的碼字可能與Wu相交，因此在w個(gè)存在干擾的時(shí)隙中，u→v的傳輸可能成功或發(fā)生第二類沖突．

第二類干擾節(jié)點(diǎn)碼字的并集與Wu相交于w個(gè)特定位置的概率記為，為了得到，與之前類似，構(gòu)造兩個(gè)生成函數(shù):

若第二類干擾節(jié)點(diǎn)任意選擇碼字時(shí)，選法的數(shù)量為

因此有

從Wu的k個(gè)位置中任選w個(gè)，選法數(shù)量為

與之前相類似，定義幾個(gè)與吞吐量有關(guān)的符號:

(Ⅳ) T0: Wv與Wu相交于0個(gè)位置時(shí)，u→v的吞吐量．

因?yàn)閡→v共有(k－w)個(gè)無干擾時(shí)隙，每個(gè)無干擾時(shí)隙可以傳輸M個(gè)數(shù)據(jù)流，因此

其中ks表示協(xié)議幀長．

由式(24)和式(25)，可以得到

由于Wu共有k個(gè)位置，因此

u→v的吞吐量T由(15)和(27)相加得到，即

由上述性能分析的過程知，T是k的函數(shù)，然而由于T的表達(dá)式中存在關(guān)于k的組合數(shù)，如式子它們關(guān)于k是不可導(dǎo)的，因此T關(guān)于k也不可導(dǎo)．所以想要確定最優(yōu)k值，僅能通過搜索方法來進(jìn)行，即對于每個(gè)k計(jì)算一次T，然后選擇最優(yōu)k值為

5　數(shù)值結(jié)果

本節(jié)考察MIMO－O－TTMA在不同網(wǎng)絡(luò)參數(shù)(節(jié)點(diǎn)數(shù)和最大度)下的吞吐量，并與已有的協(xié)議進(jìn)行比較．仿真工具采用MATLAB，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)取100和400，每個(gè)節(jié)點(diǎn)的傳輸半徑為250m，節(jié)點(diǎn)在正方形的仿真區(qū)域內(nèi)隨機(jī)分布，仿真區(qū)域的邊長在一定范圍內(nèi)變化，以便使生成的網(wǎng)絡(luò)的最大度能在一定區(qū)間內(nèi)變化．節(jié)點(diǎn)數(shù)取100時(shí)邊長的取值范圍為(1000，4500)，節(jié)點(diǎn)數(shù)為400邊長范圍為(2000，8900)，這樣的取值范圍對應(yīng)的平均節(jié)點(diǎn)密度大約為18節(jié)點(diǎn)/跳到1節(jié)點(diǎn)/跳，因此能保證生成的網(wǎng)絡(luò)拓?fù)涞淖畲蠖纫暂^大的概率落在［4，20］的區(qū)間內(nèi)．對于給定的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，網(wǎng)絡(luò)拓?fù)浒摧喆紊桑總€(gè)輪次中區(qū)域邊長相同，相鄰的兩輪次中區(qū)域邊長相差100m．在每個(gè)輪次中一共執(zhí)行10000次生成網(wǎng)絡(luò)拓?fù)涞牟僮?，每產(chǎn)生一次網(wǎng)絡(luò)拓?fù)?，判斷網(wǎng)絡(luò)的最大度是否在區(qū)間［4，20］內(nèi)，如果是，則保存該拓?fù)?，如果不是，就重新生成網(wǎng)絡(luò)拓?fù)洳⑦M(jìn)行判斷，直到該輪次結(jié)束．執(zhí)行完所有輪次后，按照不同的最大度統(tǒng)計(jì)保存的拓?fù)鋽?shù)量，計(jì)最大度為i(i =4，5，…，20)的拓?fù)鋽?shù)量為di，令，對于每個(gè)最大度i(i =4，5，…，20)，從其對應(yīng)的di個(gè)拓?fù)渲须S機(jī)選出d個(gè)拓?fù)溆靡苑抡鎱f(xié)議．經(jīng)過上述的過程，任一網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和最大度組合下，用以仿真的拓?fù)錁颖緮?shù)量都為d個(gè)，對每個(gè)拓?fù)鋱?zhí)行協(xié)議并統(tǒng)計(jì)吞吐量，共可以得到d個(gè)吞吐量，然后這d吞吐量求平均來獲得協(xié)議在某一參數(shù)組合下的平均吞吐量．

由于MIMO－O－TTMA和MIMO－TTR同為拓?fù)湮粗狹AC，因此將比較這兩個(gè)協(xié)議的吞吐量．對于給定的網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)和最大度，MIMO－O－TTMA參數(shù)s由協(xié)議描述中的方法確定，k由式(29)確定，而MIMO－TTR的參數(shù)由GRAND(Galois Radio Network Design)算法［25，26］設(shè)計(jì)．

圖4中的給出了節(jié)點(diǎn)數(shù)為N = 100時(shí)MIMO－OTTMA和MIMO－TTR協(xié)議的吞吐量隨節(jié)點(diǎn)度的變化曲線，圖中帶后綴－sim的線表示仿真結(jié)果，沒有后綴的線表示理論分析結(jié)果．由圖可見，兩種協(xié)議的仿真吞吐量比理論結(jié)果大，這是因?yàn)閮煞N協(xié)議的性能分析中為了獲得一定的簡化均用到了近似，即某些情況下以較小的吞吐量來取代正常應(yīng)有的吞吐量．從仿真結(jié)果與理論結(jié)果的吻合程度上看MIMO－O－TTMA顯然更高．這是因?yàn)镸IMO－TTR的分析中以最壞情況下的吞吐量來衡量協(xié)議性能，而MIMO－O－TTMA的分析考慮了各種情況，并且僅對部分情況下的吞吐量進(jìn)行了近似，因此加權(quán)平均以后的吞吐量更具有一般性，也就與仿真結(jié)果更接近．比較兩個(gè)協(xié)議的仿真吞吐量可見，MIMOO－TTMA的吞吐量始終大于MIMO－TTR的吞吐量，并且隨著節(jié)點(diǎn)度的增大，MIMO－TTR的吞吐量下降較快，而MIMO－O－TTMA吞吐量下降較為平緩，因此兩種協(xié)議吞吐量的差異隨節(jié)點(diǎn)度的增加越來越明顯，例如當(dāng)節(jié)點(diǎn)度為20、天線數(shù)為4時(shí)，兩種協(xié)議吞吐量差異達(dá)到了60％以上，這種差異是由兩種協(xié)議的設(shè)計(jì)方法導(dǎo)致的．由于MIMO－O－TTMA基于正交陣列設(shè)計(jì)，其參數(shù)k的變化非常靈活，可以?。跠 +1，s +1］之間任一值，k取值的靈活性也使得協(xié)議幀長k×s的變化較為靈活，從而為吞吐量的優(yōu)化提供了有利條件．當(dāng)節(jié)點(diǎn)度較小時(shí)，s取值比較小且網(wǎng)絡(luò)中沖突較少，此時(shí)增加k可以有效提高發(fā)送分組數(shù)而不會顯著增加幀長，有利于提高吞吐量，例如D(v) =4時(shí)s和k分別取11和12吞吐量獲得最優(yōu);而當(dāng)節(jié)點(diǎn)度較大時(shí)，s較大且網(wǎng)絡(luò)中沖突較多，此時(shí)k的取D +1有利于減小幀長從而提高吞吐量，例如節(jié)點(diǎn)度D(v)大于8時(shí)，k取D + 1可以獲得最優(yōu)吞吐量．比較而言，MIMO－TTR基于GRAND算法［25，26］設(shè)計(jì)，其幀長只能是q2(其中q需要滿足的條件與s類似，即q2N，q＞c×Dmax)，變化的范圍有限，并且MIMO－TTR中又對q加入了其它約束［25，26］，使得q在節(jié)點(diǎn)度較大時(shí)取值偏大，因此MIMO－TTR僅在節(jié)點(diǎn)度較小即網(wǎng)絡(luò)中沖突較少時(shí)具有較理想的吞吐量，而當(dāng)節(jié)點(diǎn)度增大時(shí)吞吐量下降較快．

圖5中給出了節(jié)點(diǎn)數(shù)N = 400時(shí)MIMO－O－TTMA 和MIMO－TTR協(xié)議的吞吐量隨節(jié)點(diǎn)度的變化曲線，圖中帶后綴-sim的線表示仿真結(jié)果，沒有后綴的線表示理論分析結(jié)果．由圖5可以得出與圖4類似的結(jié)論，協(xié)議的仿真吞吐量比理論結(jié)果大，且MIMO－O－TTMA的仿真吞吐量與理論結(jié)果吻合程度高，MIMO－O－TTMA的仿真吞吐量大于MIMO－TTR的仿真吞吐量，并且兩種協(xié)議吞吐量差異隨節(jié)點(diǎn)度的增加而增加．與圖4不同之處在于，兩協(xié)議吞吐量隨節(jié)點(diǎn)度的變化較為平緩，這是因?yàn)镸IMO－O－TTMA的參數(shù)s和MIMO－TTR的參數(shù)q是由節(jié)點(diǎn)數(shù)N和節(jié)點(diǎn)度共同確定的，當(dāng)節(jié)點(diǎn)度較小時(shí)，參數(shù)主要由節(jié)點(diǎn)數(shù)確定，故N =400時(shí)協(xié)議幀長k·s和q2較N = 100時(shí)長，吞吐量較也相應(yīng)減小;而當(dāng)節(jié)點(diǎn)度增加到一定值時(shí)，上述的參數(shù)主要由節(jié)點(diǎn)度來確定，如當(dāng)節(jié)點(diǎn)度為20時(shí)無論N = 100或N = 400，協(xié)議的參數(shù)取值均相同，吞吐量也非常接近．由以上可知道，對于N=400的情況，節(jié)點(diǎn)度最小時(shí)協(xié)議吞吐量較N = 100的情況小，而節(jié)點(diǎn)度較大吞吐量與N = 100的情況基本相等，故協(xié)議吞吐量在整個(gè)節(jié)點(diǎn)度區(qū)間內(nèi)變化的范圍較小，因此變化較為平緩．

6　結(jié)論

考慮到已有的針對MIMO Ad Hoc網(wǎng)絡(luò)的拓未知MAC在節(jié)點(diǎn)度增大時(shí)吞吐量下降較快，本文中設(shè)計(jì)了能改善這一問題的新型拓?fù)湮粗狹AC協(xié)議MIMO－OTTMA．MIMO－O－TTMA利用正交陣列來設(shè)計(jì)，陣列中每個(gè)元素被映射成一組時(shí)隙，每組時(shí)隙再被隨機(jī)地關(guān)聯(lián)給某個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，以實(shí)現(xiàn)時(shí)隙的分配．在每個(gè)時(shí)隙中，分配了該時(shí)隙的節(jié)點(diǎn)通過與目的節(jié)點(diǎn)交互RTS/CTS分組來確定要發(fā)送的數(shù)據(jù)流數(shù)，以機(jī)會地利用MIMO的空間復(fù)接．MIMO－O－TTMA在保證節(jié)點(diǎn)在一幀內(nèi)至少有一個(gè)時(shí)隙能夠無干擾地傳輸?shù)幕A(chǔ)上，允許協(xié)議的幀長能在一定的范圍內(nèi)進(jìn)行靈活選擇，從而為協(xié)議性能的優(yōu)化提供了更為有利的條件．為評估MIMO－O－TTMA的性能，利用概率方法分析了協(xié)議的吞吐量，相應(yīng)地也以吞吐量最大化為準(zhǔn)則給出了優(yōu)選協(xié)議參數(shù)的方法．最后，文中用仿真比較了MIMO－O－TTMA和已有的拓?fù)湮粗獏f(xié)議MIMO－TTR，結(jié)果表明，MIMO－O－TTMA能夠有效提高網(wǎng)絡(luò)吞吐量．

參考文獻(xiàn)

［1］Demirkol M F，Ingram M A．Power-controlled capacity for interfering MIMO links［A］．IEEE VTC 2001 Fall［C］．Atlantic City: IEEE，2001．187－191．

［2］Demirkol M F，Ingram M A．Stream control in networks with interfering MIMO links［A］．IEEE WCNC 2003［C］．New Orleans: IEEE，2003．343－348．

［3］Sundaresan K，Sivakumar R，Ingram，M A，et al．Medium access control in Ad Hoc networks with MIMO links: Optimization considerations and algorithms［J］．IEEE Transactions on Mobile Computing，2004，3(4) : 350－365．

［4］Yoon S，Rhee I，Jung B C，Daneshrad B，Kim J H．Contrabass: Concurrent transmissions without coordination for Ad Hoc networks［A］．IEEE INFOCOM 2011［C］．Shanghai: IEEE，2011．1134－1142．

［5］Wang D，Tureli U．Joint MIMO-OFDM and MAC design for broadband multihop Ad Hoc networks［J］．EURASIP journal on Wireless Communications and Networking，2006，2006(2) : 1－9．

［6］Park J S，Nandan A，Gerla M，Lee H．SPACE-MAC: enabling spatial reuse using MIMO channel-aware MAC［A］．IEEE ICC 2005［C］．Seoul: IEEE，2005．3642－3646．

［7］Mundarath J C，Ramanathan P，Veen B D V．NULLHOC: A MAC protocol for adaptive antenna array based wireless Ad Hoc networks in multipath environments［A］．IEEE GLOBECOM 2004［C］．Dallas: IEEE，2004．2765－2769．

［8］Mundarath J C，Ramanathan P，Veen B D V．A cross layer scheme for adaptive antenna array based wireless Ad Hoc networks in multipath environments［J］Wireless Networks，2007，13(5) : 597－615．

［9］Dechene D，Meerja K，Shami A，Primak S．A novel MIMO aware distributed media access control scheme for IEEE 802．11 wireless local area networks［A］．IEEE LCN 2007 ［C］．Dublin: IEEE，2007．125－132．

［10］Park J S，Gerla M．MIMOMAN: A mimo mac protocol for Ad Hoc networks［J］．Lecture Notes in Computer Science，2005，3738: 207－220．

［11］Zhao P，Daneshrad B，Warrier A，Zhu W，Takeshita O．Performance of a concurrent link sdma mac under practical phy operating conditions［J］．IEEE Transactions on Vehicular Technology，2011，60(3) : 1301－1307．

［12］Park M，Choi S H，Nettles S M．Cross-layer MAC design for wireless networks using MIMO［A］．IEEE GLOBECOM 2005［C］．St．Louis: IEEE，2005．938－942．

［13］Park M，Heath R，Nettles S．Improving throughput and fairness of MIMO Ad Hoc networks using antenna selection diversity［A］．IEEE GLOBECOM 2004［C］．Dallas: IEEE，2004．3363－3367．

［14］Ke B W，Zhang Y J，Liew S C．Media access control with spatial correlation for MIMO Ad Hoc networks［A］．IEEE ICC 2007［C］．Glasgow: IEEE，2007．3660－3665．

［15］Siam M Z Krunz M．Channel access scheme for MIMOEnabled Ad Hoc networks with adaptive diversity/multiplexing gains［J］．Mobile Networks and Applications，2009，14(4) : 433－450．

［16］Shirasu M，Sasase I．A MAC protocol for maximum stream allocation depending on the number of antennas and received RTS packets in MIMO Ad Hoc networks［A］．IEEE ICC 2007［C］．Glasgow: IEEE，2007．3295 －3300．

［17］Chu Shan，Wang Xin．Opportunistic and cooperative spatial multiplexing in MIMO Ad Hoc networks［J］．IEEE Transactions on Networking，2010，18(5) : 1610－1623．

［18］Chu Shan，Wang Xin，Yang Yuanyuan．Exploiting cooperative relay for high performance communications in MIMO Ad Hoc networks［J］．IEEE Transactions on computers，2013，62(4) : 716－729．

［19］Chu Shan，Wang Xin，Yang Yuanyuan．Adaptive scheduling in MIMO-based heterogeneous Ad Hoc networks［J］．IEEE Transactions on Mobile Computing，2014，13(5) : 964－978．

［20］Gao Cunhao，Chu Shan，Wang Xin．Distributed scheduling in MIMO empowered cognitive radio Ad Hoc networks ［J］．IEEE Transactions on Mobile Computing，2014，13 (7) : 1456－1468．

［21］Blough D M，Resta G，Santi P，Srinivasan R，CortesPena L M．Optimal one-shot scheduling for MIMO networks［A］．IEEE SECON 2011［C］．Salt Lake City: IEEE，2011．404 －412．

［22］李建東，蔡雪蓮，張瑜，張珍．基于模糊控制和MIMO的Ad Hoc網(wǎng)絡(luò)STDMA協(xié)議［J］．西安電子科技大學(xué)學(xué)報(bào)，2013，40(2) : 60－66．Li Jiandong，Cai Xuelian，Zhang Yu，Zhang Zhen．STDMA protocol based on fuzzy control and MIMO for Ad Hoc networks［J］．Journal of Xidian University，2013，40 (2) : 60－66．(in Chinses)

［23］Zhang Guanghui，Li Jiandong，Zhao Min．Broadcast scheduling with MIMO links in Ad Hoc networks［J］．Journal of Electronics(China)，2007，24(4) : 477－483．

［24］Chen Dan，Li Jiandong，Li Changle．Transmission scheduling algorithm for MIMO link Ad Hoc networks［J］．Science China Information Science，2012，55 (6 ) : 1351 －1359．

［25］Zhang Guanghui，Li Jiandong，Sheng Min，Li Changle，Zhou Lei．Topology-transparent reservation time division multiple access protocol with MIMO links in multihop Ad Hoc networks［J］．IEEE Communications Letters，2006，10(5) : 411－413．

［26］張光輝，李建東，趙敏．多跳Ad Hoc網(wǎng)絡(luò)中支持MIMO的分布式拓?fù)湮粗獣r(shí)分多址接入?yún)f(xié)議的研究與分析［J］．電子學(xué)報(bào)，2006，34(10) : 1763－1767．Zhang Guanghui，Li Jiandong，Zhao Min．Study and analysis of distributed topology-transparent schedule for time division multiple access with MIMO links in multihop Ad Hoc networks［J］．Acta Electronica Sinica，2006，34(10) : 1763－1767．(in Chinses)

［27］Syrotiuk V R，Colbourn C J，Ling A C H．Topology-transparent scheduling in MANETs using orthogonal arrays ［A］．Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing［C］．San Diego: IEEE，2003．43－49．

［28］Hedayat A S，Sloane N J A，and Stufken J．Orthogonal Arrays: Theory and Applications［M］．NewYork: Springe，1999．

陳丹(通信作者)男，1984年生于陜西省商洛市．長安大學(xué)電子與控制工程學(xué)院講師，主要研究方向包括無線網(wǎng)絡(luò)協(xié)議設(shè)計(jì)與性能分析、無線信道建模、量子通信等．

E-mail: danchen@ chd．edu．cn

劉卜華男，1991生于陜西省西安市．長安大學(xué)電子與控制工程學(xué)院研究生，主要研究方向控制理論與應(yīng)用、控制系統(tǒng)設(shè)計(jì)及智能監(jiān)測．

Orthogonal Array Based Topology Transparent MAC Protocol for MIMO Ad Hoc Networks

CHEN Dan1，2，LIU Bu-hua1，YAN Mao-de1，LI Jian-dong2，LI Chang-le2
(1．School of Electronic and Control Engineering，Chang’an University，Xi’an，Shaanxi 710064，China; 2．State Key Lab of Integrated Service Networks，Xidian University，Xi’an，Shaanxi 710071，China)

Abstract:An orthogonal array based topology transparent MAC(Media Access Control) protocol named MIMO－OTTMA(MIMO Supported Orthogonal Array Based Topology Transparent Multiple Access) is proposed for MIMO(Multiple Input Multiple Output) Ad Hoc networks．The protocol utilizes the orthogonal arrays to assign slots for network nodes，in each assigned slot，the transmitters determine the number of streams to be used by exchanging the RTS/CTS(Request To Send/Clear To Send) packets with their destination nodes，in this way，the nodes can opportunistically use the spatial multiplexing(SM) of MIMO to enhance the network performances．In addition to ensuring at least one collision-free slot in a frame for each node，the MIMO－O－TTMA allows the frame length to be flexibly chosen in certain range，which provides favorable conditions for optimizing the protocol performances．To evaluate the performance the MIMO－O－TTMA，a probability method is used to analysis the throughput of the protocol．Numerical results show that，compared with the existing topology transparent MAC，MIMO－O－TTMA can effectively improves the network throughputs．

Key words:MIMO(Multiple Input Multiple Output) ; Ad Hoc networks; MAC(Media Access Control) protocol; orthogonal arrays

作者簡介

基金項(xiàng)目:國家自然科學(xué)基金(No．61231008) ;陜西省工業(yè)科技攻關(guān)項(xiàng)目(No．2014K05-59，No．2015GY033) ;中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金

收稿日期:2014-07-15;修回日期: 2015-05-25;責(zé)任編輯:馬蘭英

DOI:電子學(xué)報(bào)URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．010

中圖分類號:TN915.4

文獻(xiàn)標(biāo)識碼:A

文章編號:0372-2112 (2016) 02-0308-11