多跳無線網中基于空分TDMA的時隙分配策略

韓 成， 吳援明

0 引言

在多跳無線網中一個具有挑戰性的問題是如何保證延遲。相關文獻研究表明使用CSMA的接入方式，在需提供具有延遲保證的應用環境表現很差[1]。解決這類問題可以引入時分多址接入(TDMA)。但在Ad hoc網絡中鏈路相對較少時使用效率不高。一個對TDMA機制的有效改進方法是空分TDMA，它將無線結點之間的物理距離考慮在內，規定互相不干擾的通訊鏈路可以在相同的時間片內傳輸，從而減少了網絡所需時間片的總量，從而提高了整個網絡的吞吐量。其容量的提高通過時隙的空間復用來實現，而延遲保證有TDMA來提供。

兩種基本STDMA調度策略之一是將傳輸權直接賦予節點。另一種將傳輸權賦予鏈路。節點分配算法和鏈路分配算法在文獻[2]中有過深入的探討。研究表明不論是節點分配還是鏈路分配在尋找最小長度調度是都歸結為全NP問題[3]。在本文中，我們提出了一個結合兩者優點的分配策略。該策略基于鏈路調度，但是傳輸權被擴展。該方式提高了鏈路分配的空間利用程度。為了對比該策略是否優于單純的節點或鏈路分配，我們使用在TDMA調度中經常使用的網絡干擾模型。我們將分別采用分析法和仿真來估計該策略在不同網絡連通性下的端到端時延和吞吐量。

1 網絡模型

假設使用全向天線并且所有節點具有相同的傳輸功率。對于任意兩個節點(vi, vj)，其中 vi表示發送節點， vj表示接收節點，且 vi≠vj，節點vi和節點vj之間的鏈路可以成功傳輸分組的條件是節點間的信噪比(SNR)超過一個門限，即：

其中， Pi表示發送節點 vi的傳輸功率。 G (i,j)表示節點 vi、vj之間的鏈路增益。 Nr表示在接收節點所有的噪聲功率。如果SNR不小于通信門限γc，我們說一對節點(vi, vj)形成一條鏈路(i,j)。η表示網絡中形成的鏈路集合，定義為η={(i,j ):Γi,j≥ γc}。任意的鏈路集合的子集L?η，定義發送節點 VT(L) = { vi:(i,j) ∈ L }。

干擾包括背景噪聲和所有并發鏈路的同頻干擾。對于任意鏈路（i, j）∈L，定義干擾如下：

因此，信干噪比 ∏L(i,j)可由以下式子求得：

2 分配策略描述

2.1 鏈路分配策略

如果{i,j} ∩ { k,l} ≠ Φ ，鏈路(k,l)稱為鏈路(i,j)的鄰近鏈路。時隙ti對應分配的鏈路集合為L，由此我們定義Ψ(L)為集合L中各鏈路對應的鄰近鏈路旁集合。當滿足如下兩個條件：

時隙it分配的鏈路集合L中各鏈路能同時傳輸。

2.2 節點分配策略

在面向節點的分配策略中，我們定義時隙 ti對應分配的節點集合為V，定義集合V中某一節點v(v∈V)的鄰節點為Φ(v)，這里的鄰居節點表示能同時接收到節點v傳輸的分組。設集合V中所有節點的鄰節點為Φ(V)，L(V)表示Φ(V)相關的鏈路集合，為了滿足集合V中的節點以及 L (V)中鏈路能同時傳輸分組，同樣也需要滿足如下兩個約束：

式(5)表示的物理意義為同時傳輸的節點不應有相同的鄰節點以及同時傳輸節點的鏈路相互不應有干擾。

2.3 改進的面向鏈路分配策略

我們注意到式(3)發生沖突檢測的條件依賴于數據包發送節點，而不在于接收節點上。假定某一節點在該時隙中分配為發送節點，這樣就存在一條傳輸鏈路，如果要更改數據包的傳輸方向，除了分配的接收節點外，新的接收節點對于不等式(4) ∏l( i,j) ≥γr， ?( i ,j) ∈ L 仍能得到滿足，這就意味著對于其他接收節點的干擾級別并沒有改變。

基于上述理由改進的面向鏈路分配策略可以描述為，對于已分配時隙的鏈路，首先檢查該條鏈路上是否有分組需要傳輸，如果沒有便將該時隙分配給具有相同發送節點的其他鏈路(該鏈路上存在數據包傳送)。當然為了避免不必要的分組丟失，無沖突鏈路可以按照優先級來選擇。我們定義該策略為基于擴展傳輸權限的鏈路分配策略LET(Link Assignment with Extended Transmission Rights)。

下面我們證明重新分配傳輸權的鏈路不會對本時隙中其他鏈路引入附加的競爭。設按照公式(4)能同時傳輸的鏈路集合為L，則 ∏l( i,j) ≥γr，?( i ,j)∈ L 。打算撤銷傳輸權的鏈路集合為LR(LR∈L)，該時隙余下的鏈路集合設為LNR，滿足關系 LNR= L LR。重新分配傳輸權的鏈路集合為LU，可推得 VT( LU) = VT( LR)。由于 LNR為無沖突鏈路集合，因此需要證明下式無等式成立：

根據式(4)信干噪比SINR定義可知：

挑戰墨西哥和白人文化中根深蒂固的父權價值體系（Madsen,2000:2）是塞利亞文化身份建構的另一關鍵。

3 分配策略性能分析

本節我們將給出LET性能的一些分析結果。首先討論吞吐量其次計算在低業務到達率前提下的分組延時。

3.1 分配策略對網絡吞吐率的影響

文獻[4]中討論了在固定鏈路容量和固定路由下的網絡吞吐量。文獻[5]中提出了鏈路調度策略的網絡最大吞吐量。重寫如下：

其中 TL是鏈路調度的長度。N表示節點的數目，N = V。hij表示在一個調度幀長內，分配給鏈路(i,j)的時隙數量。Λij表示路由表中包含(i,j)鏈路的路徑數量。對應地，按節點分配的網絡最大吞吐量 λN*如下所示：

其中 TN是節點調度的長度， hi表示在一個調度幀長內，分配給節點(i)的時隙數量。Λi表示路由表中包含節點(i)的路徑數量。

從以上兩式可以看出，如果所有節點或鏈路都處于飽和狀態，那么平均分組時延將會無限長。這時節點吞吐量Λijλ / N (N - 1 )就與 T /hij相等。而且在鏈路調度中對業務進行完全補償(hij=Λij)后，上述網絡吞吐量的計算可以分別簡化為：

這樣上式就建立起兩種分配方案與吞吐量之間的關系：

所以兩種分配方案下的吞吐量與STDMA幀長度相關。

3.2 分配策略對網絡延時的影響

轉發業務可以使用泊松分布過程來描述。根據網絡延時的定義，在面向鏈路的分配策略中對于廣播業務系統網絡延時為 dij= TL/2hij其中 dij為鏈路(i,j)的平均edge delay。

如果對業務進行完全補償(hij=Λij)后：

這里M為網絡中所有鏈路的總數。

以上兩點假設對LET策略同樣適用，但由于LET在低業務負載情況下表現為節點分配調度。因此鏈路分配策略必須擴展到節點，并按照調度中的安排進行廣播或單播。因此LET策略的延時可以定義為。進行業務完全補償后，因此鏈路分配、節點分配分別與LET之間的時延關系如下：

可見，分配策略時延關系與網絡大小、連通度以及調度周期有關。

4 仿真

本節我們評價在不同連接性和節點數下，網絡的吞吐量和時延。為了便于比較分別生成了500個節點數量為10、20和40的網絡拓撲。每個節點平均產生參數為λ的泊松過程數據流。由于傳輸功率P不同，將導致拓撲結構連通性的變化。這里定義連通性為單跳內平均每節點的鏈路數，即M / (N(N - 1 ))。M表示網絡中所有鏈路的數量。

在 20節點高業務負載條件下，鏈路分配最大吞吐量和節點分配最大吞吐量的比值，根據式(10)應等于TL/TN。仿真結果如圖 1所示。從圖中可以看出，鏈路分配策略性能比節點分配策略提供更大的吞吐量，而且不同的網絡連通性有不同的吞吐量比，隨著連通性的下降鏈路分配能實現更高的吞吐量。在 20節點低業務負載條件下，我們探討鏈路分配平均時延LD與節點分配平均時延ND間的比值關系。從圖2可以看出比值基本與連通率呈線性關系。從數值上看，鏈路分配時延遠遠大于節點分配時延。并隨連通率的增大而增大。

下面我們來探討節點分配與 LET的關系，如圖3為20個節點、低延遲負載條件下， DN/DLET的比值大小。

圖 1 吞吐量之比與連通率的關系

圖 2 兩種分配策略延時比值關系

圖3 不同節點數目下吞吐量與連通性的關系

如果參數值大于1則說明LET策略在低負載條件下時比值與連通率的關系，可以看出在不同網絡拓撲下該值變化較大，圖 4為在 10/20/40節點條件下平均 DN/DLET比值關系。DN/DLET隨著連通率的提高而降低，這是由于連通率的提高導致鏈路分配空分復用能力的降低。并且在中低連了DN/DLET＜ 1 的情況。而網絡中節點數越多 DN/DLET比值越大,即LET延遲越小,這是因為網絡越大每個節點可供傳輸的周圍節點越多,則LET策略可選的鏈路也就越多,以致時延減少。

5 結語

從以上三種分配策略分析表明，策略的選擇與網絡連通率、業務負載和網絡大小有關。在高業務負載下，由于鏈路分配有更高的空間復用能力比節點分配具有更好的吞吐量。相反地，在低業務負載下節點分配能提供節點間更短的傳輸時間。從仿真結果可以看出，LET策略在保持高吞吐量的前提下，時延比鏈路分配低很多。而且在中低連通率條件下也比節點分配低。這說明LET策略很好地結合的兩者的優點，使性能達到最佳。

[1] Ramanathan S, Lloyd E. Scheduling Algorithms for Multihop Radio Networks[J]. IEEE/ACM Trans. Networking.,1993,1 (02)：166-177.

[2] Nelson R, Kleinrock L.Spatial-TDMA： A Collision-free Multihop Channel Access Protocol[J]. IEEE Trans. Commun., 1985,33(09)：934-944.

[3] Arikan E. Some Complexity Results about Packet Radio Networks[J]. IEEE Trans. Inform. Theory, 1984（IT-30）：910-918.

[4] Asp B,Eriksson G, Holm P. Detvag-90 R_—Final Report,Scientific Report FOA-R-97-00566-504-SE,Defence Research Est., Div. of Command and Control Warfare Tech.[R]. Sweden：[s.n.], 1997.