基于交換策略的混合網絡用戶接入算法

李玉娜，曾興斌，2，何加銘，2

(1.寧波大學通信技術研究所，浙江寧波 315211;2.浙江省移動網應用技術重點實驗室，浙江寧波 315211)

0 引言

蜂窩系統網絡與ad-hoc網絡相結合的混合網絡［1］是一種新型的無線接入網結構，在蜂窩移動通信系統的終端之間引入自組網通信方式可以利用自組網的自身特點有效地解決目前蜂窩系統的一些特殊問題:解決“盲點”緩解“熱點”。文獻［2］指出，因為結合了蜂窩網絡的穩定性及ad-hoc網絡的靈活性和移動性，混合網絡應用前景十分廣闊。但是有利也有弊，自組網模式通信的加入帶來了如:資源分配機制、均衡負責等一些仍需解決的技術難點，特別是由于多種通信方式共享系統信道資源所帶來的一系列干擾問題。本文從ad-hoc網絡的可靠性和蜂窩網絡的通信質量2個方面出發，分析在單小區的情況下，由于ad-hoc用戶接入產生的對混合網絡的干擾，并提出了一種基于交換策略的混合網絡用戶接入控制的算法能夠有效地減少和避免干擾。

1 混合網絡中用戶接入的問題闡述

1.1 ad-hoc用戶接入網絡引來干擾問題分析

混合網絡［3］中存在2種通信模式，把自組網通信模式引入到混合網絡中，如果基站沒有協調好管理自身使用帶寬，而是讓自組網絡共享自身使用帶寬資源的同時采用分布式控制方式，則蜂窩系統很大可能會受到自組網絡帶來的不同程度的干擾。尤其是當自組網絡很龐大時，將無法控制自組網絡對蜂窩網絡的累積干擾以及自組網絡內部的干擾，從而導致2種通信系統網絡都無法正常進行通信。而如果由蜂窩基站端來控制自組網絡的通信方式，首先需要混合網絡預留出自組網絡需要的資源，自組網絡的資源分配以及功率控制由基站端來執行，從而降低系統的整體資源利用率;其次，自組網絡如何通信由基站來控制，由此會由于信令的交互而增加混合系統網絡的復雜度，同時如果自組網絡的用戶過多，則無法協調自組網絡鏈路之間的干擾，并且實際操作不現實?？紤]到上面提到的情況，為了可以協調和控制子系統之間共享資源可能會帶來的一些嚴重干擾，在本文的單小區混合網絡中將由基站在一定程度上不完全地控制 ad-hoc網絡［4］。

1.2 系統模型

在這里考慮ad-hoc用戶接入單小區混合網絡的問題，蜂窩小區使用全向天線(小區覆蓋范圍是360°)，蜂窩基站位于小區的中心，自組網絡共享蜂窩系統的上行頻段。把小區按照地理位置分為多個小型區域，每個分割后的小區域產生一個ad-hoc簇，簇內的ad-hoc終端用戶由簇頭控制。為了降低ad-hoc網絡對蜂窩系統的累積干擾調控的難度，系統內不同ad-hoc簇使用不同的頻段資源，本文主要考慮的是基站如何根據所掌握的ad-hoc網絡信息有選擇性地激活某些區域，使基站去給一個簇頭授權，從而使得簇頭范圍內的ad-hoc節點能夠接入到混合網絡內，共享蜂窩授權頻段進行通信。

圖1 單小區混合網絡模型

在此系統模型下，考慮的優化目標［5］有2個，一個是ad-hoc網絡的可靠性，使得長時間下能夠進行端到端通信的節點比例盡可能高;另一個是要保證蜂窩網絡的通信質量，使得在引入端到端通信后，可以保證蜂窩系統上行鏈路的通信質量，控制由于adhoc網絡帶來的干擾不超過一定的門限。系統優化目標如下:

式中，UAble是混合網絡中接入進來的ad-hoc節點數目;UAll為所有的ad-hoc節點數目 ;INAble(i)為示性函數，具體表示為:

式中，NAble是激活區域的集合;G是一個考慮到天線增益和天線高度的常數;PT是ad-hoc節點的固定傳輸功率;EF、ES分別是快衰落(瑞利衰落)、慢衰落(正態衰落)的期望;δ是路徑損耗指數;ri是標號為i的ad-hoc簇頭到基站的距離。

2 用戶接入控制算法

2.1 模型分析

系統的信道模型考慮快慢衰模型并且基站接收功率超過某一給定閾值，這里采用的快衰以及陰影衰落模型［6］為:

式中，rBS≡，Pmin為一個給定的門限，為常數，G、PT、δ與上面的定義相同，R為節點到基站的距離，X為(標準化)包絡快衰落系數(滿足E[ X2]=1)，10Z/10為陰影衰落。

公式可以等價轉換為:

這里Uoff的定義與UAble相反，通過長期觀察分割的ad-hoc區域，可以統計得出各個區域內的ad-hoc節點的分布情況以及相應的參數，分析數據證明，如果簇內的ad-hoc終端的分布情況是均勻隨機的，那么ad-hoc用戶數在簇內服從泊松分布。λi為第i號ad-hoc簇內終端密度分布的期望。根據泊松分布特性以及假設分割后的區域面積是相等的，可以發現，上述問題可以轉化成一個組合優化問題。公式轉化后為:

式中，NOff是沒有被激活的區域的標號集合，λi是第i號區域的分布節點密度期望，S是一個區域所占的面積。由上述公式，可以看出，優化目標問題變成了一個組合優化問題—0-1背包問題。

2.2 求解0－1背包問題的蟻群算法描述

0-1背包問題是一類經典的組合優化NP完全問題［7］。如貨物裝載、資源分配等許多有實用價值的問題，都可以轉化為背包問題。目前對于背包問題的求解方法有精確算法和近似算法，即貪心算法和遺傳法兩大類?；诮粨Q策略的蟻群算法［8］能夠更有效解決0-1背包問題，并且具有較好的性能。

2.2.1 螞蟻的路徑選擇

0-1背包問題的構造圖如圖2所示。

圖2 0－1背包問題的構造圖

設τij(t)為 t(t=0，1，2…)時刻有向線段a[ i，j]上的信息素，則在時刻t，螞蟻k(k=1，2…，m)從節點i(i=1，2…，n)經由線段a[ i，j]轉移到節點 i+1的轉移概率(t)為:

式中，α、β分別為表示軌跡相對重要性的信息啟發式因子和能見度相對重要性的期望啟發式因子;ηij為啟發函數，ηij=wj/vj，wj為物品 j的價值，vj為物品j的體積。Jk(i)是螞蟻k(位于節點i上)可以選擇的有向線段集合，公式為:

假如螞蟻k死亡后禁忌表tabuk中的數字為{j1，j2…，jr}且{j1，j2…，jr}? {1 ，2，…n }，則螞蟻k求得背包問題的解為:

2.2.2 信息素更新

當m只螞蟻都死亡以后，可得到m組可行解。如果本次迭代得出的最好解優于當前的最優解，則用其代替當前的最優解。之后，螞蟻k要對其經過的路徑上的信息素進行相應的更新，即:

式中，ρ表示信息素蒸發系數，Δ τij表示本次迭代中有向線段 a[ i，j]上信息素量的增量;Δ τkij表示第k只螞蟻在有向線段a[ i，j]上留下的信息素量;Q是信息素常數，Lk表示第k只螞蟻在本次迭代中求的解。

2.2.3 算法描述

基于交換策略的蟻群算法表示如下:

begin:

步驟 1:初始化數據:α，β，ρ，Q，NCmax，m，τij(0)，其中 i，j=1，2，…n;

步驟2:將m只螞蟻置于節點1;

步驟3:for每只螞蟻do

①按式(9)計算得出轉移概率同時選擇下一條有向線段;

②如果沒有有向線段符合背包問題的約束條件，則該螞蟻死亡;

③如果螞蟻未死亡，則將選擇的有向線段序號加入到螞蟻k的禁忌表tabuk中;

end for

步驟4:

3 仿真結果

對于0-1背包問題有很多的求解方法，這里把從ad-hoc網絡對蜂窩系統的干擾以及ad-hoc網絡終端接入率出發的2種算法與本文算法進行比較。

參考算法1:最小化ad-hoc系統對蜂窩網絡的干擾-θ。選擇γδi最大的區域來激活，直到θ到達上界;此算法的目的是使θ值變小，由式(6)可以看出，離基站越遠的ad-hoc簇，θ值越小，而離基站越近的ad-hoc簇θ值偏大，接入到網絡中的可能性很小。因此，如果離基站近的ad-hoc簇的分布節點密度高，而遠離基站的ad-hoc簇分布節點密度低，則此算法最后得到的接入率將會很低。

參考算法2:最大化ad-hoc節點接入率—l.選擇λl最大的區域激活，直到θ到達上界;這個算法會優先考慮接入節點密度高的ad-hoc簇，而忽略ad-hoc簇的地理位置。由于干擾門限的存在，即使蜂窩基站附近的ad-hoc簇節點密度很高，然而混合網絡中的ad-hoc終端的接入率也不一定很高。

仿真的正方形單蜂窩小區大小是5 km*5 km，蜂窩小區被分割成5*5的ad-hoc區域。其中將基于交換策略的用戶接入控制算法接入算法模塊部分，仿真流程圖如圖3所示。3種算法下，實際網絡的平均干擾如圖4所示，50次仿真總的平均干擾分別-134.6 dB、-134.9 dB和 -134.1 dB。用戶接入控制算法50次仿真實際的網絡干擾與門限值如圖5所示。3種算法的實際接入比例如圖6所示，50次仿真平均值為4.3、3.7和2.4。

通過仿真結果比較發現，如果從干擾方面考慮，參考算法1仿真得到的總平均值最小，參考算法2得到的值最大，本文算法的干擾結果與參考算法1比較接近;而如果從ad-hoc節點接入比例來看，本文算法得到的ad-hoc用戶接入比例最高，并遠高于其他2種參考算法的仿真結果。

圖3 系統仿真流程圖

圖4 3種算法的平均干擾

圖5 用戶接入控制算法實際網絡干擾與干擾門限值

圖6 3種算法的接入比例

4 結束語

蜂窩網與ad-hoc網絡混合組網模式能夠帶來很多方面的優勢［9］，如:增加網絡覆蓋范圍、降低功耗和均衡業務流量。為了能夠獲得諸多優勢，系統內資源的調度與分配是非常重要的，合理地分配資源，保證混合系統的收益最大化將是未來不斷努力的方向。仿真結果表明所提出的算法能在有效控制干擾的條件下，最大化ad-hoc節點的接入比例，使得整體性能達到最優。

［1］崔維嘉，于宏毅，李青.混合網絡研究［J］.中興通訊技術，2005，11(04):36-41.

［2］李國強，靳浩.Ad hoc技術在未來無線通信中的應用［J］.現代電信科技，2007(06):18-23.

［3］張帆.一種集成ad hoc與蜂窩的4G新型網格(IACG)［J］.無線通信技術，2005，31(01):9-12.

［4］POMPORTES S，TOMASIK J，Vèque V.Ad hoc Network in a Disaster Area:A Composite Mobility Model and its Eevaluation［C］∥Advanced Technologies for Communications(ATC)，2010 International Conference on，2010:17-22.

［5］駱世峰.混合的蜂窩與ad-hoc網絡中的干擾避免與協調［D］.北京:北京郵電大學，2010.

［6］MUKHERJEE S，AVIDOR D.Outage Probabilities in Poisson and Clumped Poisson-distributed Hybrid ad-hoc Networks［C］∥IEEE Conference on Sensor and Ad-hoc Networks(SECON)，2005:563-574.

［7］SYSLOM M.Discrete Optimization Algorithm［M］.Englewood C lifs，New Jersey:Prentice-Hall，1983:118-165.

［8］潘夏福.倪子偉.基于交換策略的蟻群算法求解多維0-1背包問題［J］.計算機與現代化，2008(03):83-85.

［9］錢宗峰，張德興，孔昭煜.蜂窩網與Ad hoc網融合技術探討［J］.電信快報，2009(06):11-14.