王勇杰, 陳 靜
(1. 山西大學(xué) 商務(wù)學(xué)院, 山西 太原 030031; 2. 中國航天科工集團第二研究院706所, 北京 100854)
無線中繼網(wǎng)絡(luò)部署方案設(shè)計
王勇杰1, 陳 靜2
(1. 山西大學(xué) 商務(wù)學(xué)院, 山西 太原 030031; 2. 中國航天科工集團第二研究院706所, 北京 100854)
根據(jù)無線中繼器來擴大無線網(wǎng)絡(luò)的覆蓋面積, 提升當(dāng)前區(qū)域內(nèi)網(wǎng)絡(luò)質(zhì)量的需要, 提出了一種無線中繼設(shè)備部署策略來提升區(qū)域內(nèi)用戶的滿意度. 對無線中繼網(wǎng)絡(luò)進行了建模, 對無線網(wǎng)絡(luò)中信號傳輸過程進行了量化處理, 利用用戶接收到的信號強度定義用戶的體驗度; 利用最速下降法, 使無線中繼器能夠自適應(yīng)地向一些理想位置進行移動, 最終確定每一個無線中繼設(shè)備的部署位置. 仿真實驗表明, 本文算法能夠很好地提升區(qū)域內(nèi)用戶的體驗度, 具有較高的應(yīng)用價值.
無線中繼網(wǎng)絡(luò); 信號傳輸; 體驗度; 最速下降法
由于無線網(wǎng)絡(luò)信號源放置位置不合理, 發(fā)射功率不足以及障礙物的阻斷, 導(dǎo)致了無線網(wǎng)絡(luò)的覆蓋范圍小, 無線信號弱等問題, 無法滿足用戶的用網(wǎng)需求[1]. 近年來出現(xiàn)的無線中繼器設(shè)備, 可以對接收到的無線信號進行轉(zhuǎn)發(fā)放大, 滿足了更多用戶的需求, 擴大無線網(wǎng)絡(luò)的覆蓋范圍[2-5], 無線網(wǎng)絡(luò)也就變成了無線中繼網(wǎng)絡(luò), 使得無線網(wǎng)絡(luò)的應(yīng)用面更廣, 作用更大. 因此, 人們對無線中繼器的研究也越來越多.
2004年, Nosratinia等人[6]首先提出了無線中繼協(xié)作這一概念, 即借助無線中繼設(shè)備, 來完成數(shù)據(jù)包的傳遞, 并給出了三種中繼轉(zhuǎn)發(fā)模式, 針對三種不同的模式, 進行了詳細(xì)的理論分析, 得出了每種模式的應(yīng)用場景, 使得中繼這一概念逐漸流行. 有很多研究集中在了無線中繼網(wǎng)絡(luò)的物理特性, 如無線轉(zhuǎn)發(fā)機制的測試與評價[7], 編碼機制[8], 以及無線信號信道特性[9].
2010年之后, 越來越多的研究者開始利用無線中繼設(shè)備來擴大覆蓋范圍, 其中包括利用中繼節(jié)點來擴大無線傳感器網(wǎng)絡(luò)范圍, 幫助傳感器來傳輸數(shù)據(jù), 起到連接作用. Jiang等人[10]研究在無線傳感器網(wǎng)絡(luò)中, 利用無線中繼設(shè)備將傳感器連接到主干中心網(wǎng)絡(luò)上, 擴大整個監(jiān)控范圍, 他們提出了一種分布式的算法, 首先解決傳感器的部署覆蓋問題, 之后部署無線中繼器來連接傳感器. Lang等人[11]針對下一代移動網(wǎng)絡(luò), 通過部署無線中繼器來擴大整個網(wǎng)絡(luò)覆蓋范圍, 根據(jù)不同區(qū)域的使用需求以及部署開銷, 來確定最優(yōu)的部署策略與方案. Pervin等人[12]研究在目標(biāo)覆蓋區(qū)域內(nèi)的節(jié)點候選集合中選出聯(lián)通的傳感器網(wǎng)絡(luò), 實現(xiàn)區(qū)域的全覆蓋, 他們提出了兩種集中式的貪心算法, 相較于分布式算法, 能夠減少計算的復(fù)雜性.
同時, 也有借助無線中繼器來擴大無線網(wǎng)絡(luò)范圍, 提升網(wǎng)絡(luò)質(zhì)量. Ma等人[13]利用無線中繼器延長整個網(wǎng)絡(luò)的工作時間, 將問題轉(zhuǎn)化為無線中繼器部署問題, 覆蓋所有的傳感器節(jié)點, 提出了布局搜索的近似算法, 借助獨立集和集合覆蓋進行算法分析, 得到了較好的近似比. Gueguen等人[14]針對協(xié)作編碼模式的無線中繼器, 提出了一種獎勵機制, 通過選擇區(qū)域內(nèi)的網(wǎng)絡(luò)設(shè)備, 進行中轉(zhuǎn)信號從而增大網(wǎng)絡(luò)區(qū)域面積, 該網(wǎng)絡(luò)設(shè)備的擁有者獲得了一定的獎勵, 實現(xiàn)了雙贏.
這些研究都是通過部署無線中繼器來實現(xiàn)整個無線網(wǎng)絡(luò)中網(wǎng)絡(luò)性能的提升, 但他們對于無線中繼器的部署位置有著相對嚴(yán)格的要求, 即給出了相應(yīng)的候選集合, 這樣就導(dǎo)致無線中繼器并不能自適應(yīng)地進行調(diào)整, 存在一定的局限性; 另外, 單純地聯(lián)通傳感器等一些節(jié)點并不能真實地反映連通結(jié)果, 信號傳輸快慢、 信號傳輸大小等具體指標(biāo)才能夠地直觀反映無線中繼器連通的作用. 因此, 本文主要研究無線中繼器的部署問題, 提出最速下降算法, 使每一個無線中繼器根據(jù)用戶分布以及連通性要求進行自適應(yīng)地移動, 從而對部署位置進行優(yōu)化, 使更多的用戶獲得滿意的無線信號.
由于無線中繼網(wǎng)絡(luò)涉及到無線中繼設(shè)備之間的連通性, 以及用戶與無線設(shè)備之間的信號傳輸, 因此分別對網(wǎng)絡(luò)模型與通訊模型進行建模處理, 網(wǎng)絡(luò)模型主要考慮無線中繼網(wǎng)絡(luò)之間設(shè)備的連通性, 通訊模型則主要考慮無線信號傳輸過程, 對用戶體驗等進行定義.
針對一個目標(biāo)區(qū)域Ω, 假設(shè)該區(qū)域連續(xù)、 平坦且沒有障礙物妨礙, 區(qū)域內(nèi)有n個用戶, 記為U={u1,u2,…,un}, 每個用戶使用一個移動設(shè)備, 進行無線信號接收. 區(qū)域內(nèi)放置著一個無線基站B, 用來發(fā)射無線信號, 共有m個無線中繼器可以放置在當(dāng)前區(qū)域中, 記為R={r1,r2,…,rm}, 位置函數(shù)L(·)記錄區(qū)域內(nèi)用戶、 無線基站以及無線中繼器的位置.
由于無線中繼器無法感應(yīng)太弱的無線信號, 因此, 無線中繼器之間以及無線中繼器與無線基站之間的距離不能過長, 記該距離為通訊半徑d, 即當(dāng)兩個設(shè)備之間的距離小于d時, 兩者之間可以互相接收到滿足工作需求的無線信號.
為了實現(xiàn)無線通信, 需要在區(qū)域內(nèi)的所有無線中繼器與無線基站之間進行若干條連接, 從無線基站獲取最初的無線信號, 形成一個連通的網(wǎng)絡(luò).
在無線網(wǎng)絡(luò)中, 用戶所能夠接收到的無線信號強度決定著用戶在該網(wǎng)絡(luò)下的體驗度, 因此需要計算無線信號傳播過程中, 用戶所能夠接收到的無線信號強度. 由于該區(qū)域平坦連續(xù)且沒有障礙物, 無線信號發(fā)射源與用戶的移動設(shè)備之間沒有障礙物, 能夠直接看到對方, 因此采用Friis自由空間傳播模型來計算移動設(shè)備的接收信號功率, 即
式中:PR是接收功率;PT是發(fā)射功率;d是兩個設(shè)備之間的距離;GT和GR分別表示發(fā)射和接收增益;λ為無線信號的波長. 因此, 移動設(shè)備的接收功率是一個隨距離變化的函數(shù), 不同的移動設(shè)備對無線信號的敏感度、 接收增益也不同.
在日常生活中, 常見的無線路由器的發(fā)射增益為3 dBi和5 dBi, 一些性能更強的無線路由器采用7 dBi的天線; 平時使用的手機等移動設(shè)備的接收增益一般為2~3 dBi, 一般的無線路由器的發(fā)射功率在50~100 mW之間, 我國現(xiàn)在常見的無線網(wǎng)絡(luò)中, 信號頻率通常是2.4 GHz和5 GHz.
可以看出, 移動設(shè)備的接收功率與無線信號源的距離平方成反比, 因此需要考慮路徑損耗PL, 即發(fā)射功率與接收功率的相差值, 代表信號的衰減程度
由于用戶大多使用移動設(shè)備, 因此記用戶接收到的無線信號功率為無線信號接收強度, 即為需要優(yōu)化的目標(biāo), 但由于這個目標(biāo)難以量化, 因此定義用戶體驗度函數(shù), 將用戶接收到的無線信號功率轉(zhuǎn)化為用戶體驗度, 這樣更利于以后的計算.
一些移動設(shè)備接收到的信號強度過小, 并不能滿足用戶的基本需求, 因此設(shè)定一個基本信號強度的閾值T, 即當(dāng)移動設(shè)備接收到的信號強度大于信號強度閾值T時, 該接收信號強度能夠滿足用戶的基本需求, 才會被計算在內(nèi), 作為優(yōu)化的目標(biāo). 用戶體驗度函數(shù)定義為
式中:Pmax表示移動設(shè)備能夠接收到的最大無線信號功率. 這樣就將優(yōu)化目標(biāo)進行了歸一化處理, 便于之后的計算. 根據(jù)用戶所連接的無線設(shè)備, 對體驗度函數(shù)進行重新定義為
本文通過放置有限數(shù)目的無線中繼器, 來使得區(qū)域內(nèi)用戶所接收到的無線信號強度之和達到最大, 每一個用戶的移動設(shè)備都可能會接收到來自不同無線信號源發(fā)射的無線信號, 那么根據(jù)無線信號強度的大小排序, 每個移動設(shè)備都會選擇信號強度最大的無線信號發(fā)射源進行連接, 定義此時已經(jīng)在區(qū)域內(nèi)放置的無線信號源的狀態(tài)為A, 定義連接函數(shù)cA(u)為用戶所選擇的接收到在A狀態(tài)下的最大信號強度u的無線信號源, 可以是無線基站B, 也可以是無線中繼器R, 根據(jù)該連接函數(shù)確定用戶與無線信號發(fā)射源的對應(yīng)關(guān)系, 即
具體的問題定義為: 在目標(biāo)區(qū)域Ω中放置著一個無線基站B, 在區(qū)域內(nèi)分布著n個用戶, 通過放置m個無線中繼器, 保證中繼器的連通狀態(tài), 使得區(qū)域內(nèi)的用戶接收到的無線信號, 其體驗度之和達到最大, 即
梯度下降算法是一種經(jīng)典的最優(yōu)化方法, 一般用于無約束問題, 它的變量少, 要求不高. 一般的思想為, 從某個用戶u所在位置出發(fā), 取函數(shù)s(u) 在L(u)點時下降最快的方向作為移動方向, 經(jīng)過多次迭代, 達到想要的目標(biāo)值, 即在一定區(qū)域內(nèi)的極值, 此時迭代過程結(jié)束.
對于該問題, 整個迭代過程如下: 首先, 區(qū)域內(nèi)隨機放置一個無線信號基站, 可以覆蓋一部分區(qū)域, 接著在能夠與無線信號基站連通的區(qū)域內(nèi)隨機放置無線中繼器, 根據(jù)在該點放置無線中繼器能夠給予整個區(qū)域用戶信號強度的增量之和, 尋找增量增加最多的一個方向進行一定長度的移動, 之后繼續(xù)移動, 直到找不到能夠使得信號強度之和增加的點, 即作為無線中繼器的一個放置位置. 按照這個步驟放置k個無線中繼器, 使得無線中繼器分布能夠盡可能滿足區(qū)域內(nèi)更多用戶.
該算法的核心是尋找最優(yōu)的移動方向, 由于用戶接收到信號強度增量不是一個連續(xù)函數(shù), 因此需要定義信號強度的求導(dǎo)公式, 便于之后計算. 當(dāng)在該點放置無線中繼器時, 用戶與該無線中繼器連接所獲得的信號強度小于其接收到其他已放置好的無線信號源的信號強度, 即s(r,u)≤s(cA(u),u), 其中A為當(dāng)前無線中繼器放置狀態(tài), 則定義信號強度增量的導(dǎo)數(shù)為0; 當(dāng)在該點放置無線中繼器, 用戶與該無線中繼器連接所獲得的信號強度大于其接收到其他已放置好的無線信號源的信號強度時, 即s(r,u)>s(cA(u),u), 則信號強度增量的導(dǎo)數(shù)為用戶與該無線中繼器所獲得的信號強度的導(dǎo)數(shù). 具體為
式中:Lt(rj)表示無線中繼器rj在時刻t的位置;α為移動的步長.
輸入: 用戶集合U, 無線中繼器集合R
通訊半徑d, 用戶體驗度函數(shù)s
輸出: 無線中繼器的部署位置L(R)
1. 初始化: 隨機部署無線基站r1, 生成相應(yīng)的覆蓋區(qū)域
2. fori=2 tomdo
3.α=α0
4. Whileα≥αTdo
5. 在覆蓋區(qū)域內(nèi)放置節(jié)點ri
9. end while
10. end for
11. returnL(R)
該算法同樣可以擴展成分布式算法, 將所有的無線中繼器節(jié)點集中在某一個區(qū)域, 之后根據(jù)最速下降法進行自適應(yīng)移動, 但分布式算法會導(dǎo)致無線中繼節(jié)點移動的方向過于統(tǒng)一, 最終結(jié)果可能是大多數(shù)中繼節(jié)點都集中在某一區(qū)域, 無法很好地覆蓋整個區(qū)域, 使得整體覆蓋效果不如集中式算法, 需要對每個無線中繼器設(shè)置相互排斥屬性, 避免無線中繼節(jié)點的統(tǒng)一趨勢化移動.
該算法的結(jié)果在很大程度上取決于最初隨機放置的位置, 因為最速下降算法很容易受到局部最優(yōu)的影響, 因此需要進行多次模擬, 從中選擇最優(yōu)的情況作為最終的結(jié)果. 同樣, 無線中繼器在移動過程中也有可能陷入局部最優(yōu)解的循環(huán)之中, 不能取得很好的結(jié)果, 因此也需要對這種情況進行一定的判斷, 在適當(dāng)時候增加移動步長, 使得節(jié)點能夠跳出局部最優(yōu)的峽谷, 在更大范圍尋找更優(yōu)的部署位置.
本次仿真實驗主要使用 Matlab 實現(xiàn), 設(shè)定一個目標(biāo)區(qū)域Ω=100×100, 在區(qū)域中隨機地分布著成百的用戶, 每個用戶都在使用移動設(shè)備, 并對無線網(wǎng)絡(luò)有需求, 希望能夠連接到該區(qū)域提供的無線網(wǎng). 同時, 考慮異質(zhì)網(wǎng)絡(luò), 即每一個用戶之間存在差異, 因為其使用的設(shè)備不盡相同, 在一些接受參數(shù)上也難免產(chǎn)生一些差異. 設(shè)定的參數(shù)與第二部分中日常生活中的參數(shù)相近, 這樣能更加貼近現(xiàn)實, 具體設(shè)定如表 1 所示.
表 1 網(wǎng)絡(luò)模型參數(shù)設(shè)定Tab.1 Setting on network model parameter
進行仿真實驗來探究最速下降算法對于區(qū)域內(nèi)用戶體驗度的影響. 對于傳統(tǒng)的網(wǎng)絡(luò)部署問題, 大多采用網(wǎng)格的形式對部署位置的候選集合進行限定, 之后利用組合優(yōu)化算法選擇相應(yīng)的部署位置, 在這里, 也采用網(wǎng)格部署法進行對比, 通過在區(qū)域內(nèi)設(shè)置網(wǎng)格點, 利用貪心策略選擇有限個數(shù)的無線中繼節(jié)點.
首先, 利用無線中繼器個數(shù)對于網(wǎng)絡(luò)中用戶體驗度進行研究, 將用戶數(shù)目設(shè)定為200人, 在一個無線基站的基礎(chǔ)上, 可以部署5~10個無線中繼節(jié)點, 擴大整個區(qū)域無線網(wǎng)絡(luò)的覆蓋范圍, 則在這個網(wǎng)絡(luò)中用戶的體驗度之和隨著無線中繼器數(shù)目的增加而增加, 如圖 1 所示. 可以看到, 利用最速下降法得到的部署方案要優(yōu)于網(wǎng)格部署法得到的結(jié)果, 這是因為網(wǎng)格部署法會局限于有限的候選位置, 無法進行一定范圍的調(diào)整, 而通過最速下降法得到的位置, 沒有特定集合的限制, 反而能夠得到更優(yōu)的結(jié)果. 同時, 由于邊際效應(yīng)或用戶體驗度函數(shù)是一個次模集合函數(shù), 隨著無線中繼器數(shù)目的增加, 用戶體驗度之和的增量會逐漸遞減[15].
圖 1 用戶體驗度隨中繼器個數(shù)變化圖Fig.1 Influence of relays number on QoE
圖 2 用戶體驗度隨用戶人數(shù)變化圖Fig.2 Influence of users number on QoE
當(dāng)用戶數(shù)目增加時, 用戶的體驗度之和也會隨之上升, 這是由于用戶的基數(shù)增大, 從而導(dǎo)致整體的體驗度之和也會上升, 如圖 2 所示. 由此可以看出, 本文提出的最速下降法也是網(wǎng)格部署法, 整體來看, 用戶體驗度基本與用戶人數(shù)呈線性關(guān)系, 用戶的平均體驗度平穩(wěn)中有上升的趨勢, 這是因為用戶數(shù)目的增多, 導(dǎo)致用戶密度的增加, 從而使得更多用戶獲得了較好的用戶體驗.
圖 3 為無線中繼器布置的分布圖, 圖3(a)中為在區(qū)域內(nèi)放置1個無線基站與5個無線中繼器來盡可能滿足100個用戶的分布情況, 圖3(b)中為放置1個無線基站和7個無線中繼器來滿足200個用戶的分布情況. 其中, 淺色節(jié)點表示用戶位置, 空心節(jié)點表示無線設(shè)備放置位置, 黑色大圓圈表示無線設(shè)備能夠服務(wù)的范圍, 可以看到無線設(shè)備之間形成了一個連通分支, 并覆蓋了一些用戶密集的區(qū)域, 而在現(xiàn)實場景中, 也能夠很好地根據(jù)人流分布, 決策出相應(yīng)的部署方案.
圖 3 中繼器分布圖Fig.3 Relay distribution circumstance
統(tǒng)計表明, 利用無線中繼設(shè)備擴大無線網(wǎng)絡(luò)的覆蓋范圍, 在圖3的場景下, 能夠覆蓋超過65%的用戶, 由于算法是優(yōu)化用戶體驗度, 因此這些用戶中的絕大多數(shù)都能得到較優(yōu)的服務(wù)質(zhì)量, 也可以看到, 無線中繼器會放置在用戶密集的位置, 且距離一些用戶特別近, 使其獲得更好的用戶體驗, 而不是單純地覆蓋更多的用戶, 為他們提供服務(wù).
本文主要研究了無線中繼網(wǎng)絡(luò)中無線中繼器部署問題, 通過深入學(xué)習(xí)無線信號的傳輸過程, 建立了無線中繼網(wǎng)絡(luò)模型, 考慮了無線網(wǎng)絡(luò)的諸多特性, 使得該模型更加符合實際情況. 之后又提出了最速下降法來布設(shè)無線中繼器的位置, 通過確定無線中繼器的位置, 來提升用戶在區(qū)域內(nèi)的體驗度, 并在仿真實驗中取得了比較好的結(jié)果. 本文的研究內(nèi)容結(jié)合了前人的研究基礎(chǔ), 建立了一套完整的無線中繼網(wǎng)絡(luò)模型, 對以后的工作具有一定的指導(dǎo)意義.
[1] Ma L, Teymorian A Y, Cheng X. A hybrid rogue access point protection framework for commodity Wi-Fi networks[C]∥The 27th Conference on Computer Communications, IEEE, 2008: 1220-1228.
[2] Zhou H, Ji Y, Gu Y, et al. A resource allocation algorithm for SVC multicast over wireless relay networks based on cascaded coverage problem[C]∥Global Communications Conference (GLOBECOM), IEEE, 2012: 5681-5686.
[3] Jing T, Zhu S, Li H, et al. Cooperative relay selection in cognitive radio networks[J]. IEEE Transactions on Vehicular Technology, 2015, 64(5): 1872-1881.
[4] Gueguen C, Rachedi A, Guizani M. Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 797-808.
[5] Ono H, Takeyoshi H. Mobile node, packet relay device and packet forwarding method: U.S., 10/786,411[P]. 2004-02-26.
[6] Nosratinia A, Hunter T E, Hedayat A. Cooperative communication in wireless networks[J]. IEEE communications Magazine, 2004, 42(10): 74-80.
[7] Zhou H, Ji Y, Gu Y, et al. A resource allocation algorithm for SVC multicast over wireless relay networks based on cascaded coverage problem[C]∥Global Communications Conference (GLOBECOM), IEEE, 2012: 5681-5686.
[8] Mohammed A H, Dai B, Huang B, et al. A survey and tutorial of wireless relay network protocols based on network coding[J]. Journal of Network and Computer Applications, 2013, 36(2): 593-610.
[9] Dai M, Wang P, Zhang S, et al. Survey on cooperative strategies for wireless relay channels[J]. Transactions on Emerging Telecommunications Technologies, 2014, 25(9): 926-942.
[10] Jiang J, Wen J, Wu G, et al. Constructing minimum relay connected sensor cover in heterogeneous wireless sensor networks[C]∥International Conference on Ad Hoc Networks. Springer Berlin Heidelberg, 2009: 477-492.
[11] Lang E, Redana S, Raaf B. Business impact of relay deployment for coverage extension in 3GPP LTE-Advanced[C]∥IEEE International Conference, 2009: 1-5.
[12] Pervin N, Layek D, Das N. Localized algorithm for connected set cover partitioning in wireless sensor networks[C]∥Parallel Distributed and Grid Computing (PDGC), 2010 1st International Conference on IEEE, 2010: 229-234.
[13] Ma C, Liang W, Zheng M, et al. A novel local search approximation algorithm for relay node placement in wireless sensor networks[C]∥Wireless Communications and Networking Conference (WCNC), IEEE, 2015: 1518-1523.
[14] Gueguen C, Rachedi A, Guizani M. Incentive scheduler algorithm for cooperation and coverage extension in wireless networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(2): 797-808.
[15] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I[J]. Mathematical Programming, 1978, 14(1): 265-294.
DeploymentStrategyDesigninWirelessRelayNetworks
WANG Yong-jie1, CHEN Jing2
(1. College of Business, Shanxi University, Taiyuan 030031, China;2. No.706 Institute, The Secnod Academy of China Aerospace Science and Industry Corporation, Beijing 100854, China)
Based on the demand of extending the wireless coverage area and improving the networks quality with wireless relay, a deployment strategy for wireless relay was presented to increase the users' quality of experience (QoE). Wireless relay network model was built, and the transmission process of wireless signal was quantified. The QoE was defined according to the signal strength that users receive. By using the steepest descent method, the wireless relay could move adaptively to some ideal locations, and deployment point could be determined. The results of simulation experiment show that our algorithm can improve the QoE of users in the region, and has strong application value.
wireless relay network; signal transmission; QoE; steepest descent method
1673-3193(2017)05-0633-06
2016-12-21
王勇杰(1967-), 男, 副教授, 主要從事計算機網(wǎng)絡(luò), 數(shù)據(jù)挖掘研究.
TP301
A
10.3969/j.issn.1673-3193.2017.05.022