傳統(tǒng)的中繼部署問題通常假定用戶位置已知且靜止不動,這種假設在實際部署場景中是不現(xiàn)實的。隨著移動設備的普及,收集用戶移動軌跡變得越來越容易,這使在部署中繼時考慮用戶歷史移動軌跡成為可能。在此背景下,本文定義了一個新問題—基于軌跡的中繼部署(Trajectory-Based Relay Deployment,TBRD)問題,旨在通過部署一定數(shù)量的中繼,最大化用戶在目標區(qū)域內(nèi)移動時的連接時間,同時部署的中繼服從中繼連通性約束。為了解決TBRD問題,本文首先提出了需求節(jié)點(Demand Node,DN)的概念,它是一些虛擬加權(quán)節(jié)點,代表用戶經(jīng)常經(jīng)過或長時間停留的位置。接下來,本文設計了需求節(jié)點生成(Demand Node Generation,DNG)算法,將連續(xù)的用戶歷史移動軌跡轉(zhuǎn)換為多個離散的需求節(jié)點。通過生成需求節(jié)點,本文將TBRD問題轉(zhuǎn)化為需求節(jié)點覆蓋(Demand Node Coverage,DNC)問題,并證明這個問題是NP-完全。之后,本文設計了一個近似比為1-1/(?)的近似算法——次模迭代部署算法(Submodular Iterative Deployment Algorithm,SIDA)來解決DNC問題,其中e是數(shù)學常數(shù),k是中繼數(shù)量約束。最后,本文利用5個真實用戶移動軌跡數(shù)據(jù)集來對算法進行評估。仿真結(jié)果表明,提出的算法能夠為移動用戶提供較高的覆蓋率,帶來更好的用戶體驗。除此之外,本文還分析了不同參數(shù)對覆蓋性能的影響。據(jù)了解,本文是第一個在無線網(wǎng)絡中利用用戶軌跡進行中繼部署的研究工作。
【學位單位】：上海交通大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：TN92
【部分圖文】：

圖 1–1 線中繼器商品示意圖[5]意義共場所 線 絡環(huán)境中的多跳中繼部署問題預先未知。由于傳輸功率和路徑損耗的限有 戶，或 戶可能會 出基站的覆蓋范圍最 限度地利 資源，本 希望部署有限可能長時間保持聯(lián) 狀態(tài)。這種需求在體育 戶不斷移動，但在這些領(lǐng)域提供持續(xù)的做到的。關(guān)注 線 絡中的中繼部署問題。很多研究絡覆蓋 積[6–8]，還有 些研究 作關(guān)注 需要以知道 戶在 標區(qū)域內(nèi)的確切位置過程中 戶是靜 的。顯 易見，這些約束 戶位置發(fā) 變化或存在 些偏差，采

[159]中，Tutschku 詳述了需求節(jié)點的 成算法，如圖 2–6 所 。其中，圖2–6(a)是作者當?shù)氐乩砗?分布數(shù)據(jù)，圖2–6(b)是 成的通信量矩陣，圖2–6(c)給出了劃分服務區(qū)的 意圖，并基于此 成圖 2–6(d) 所 的需求節(jié)點。這種需求節(jié)點的概念很快就被研究基站部署問題的學者采 。Mathar 等[160]分析了各種各樣的優(yōu)化問題，主要 的是為蜂窩 線 絡尋找最佳的基站部署位置。Molina等[161]考慮通過選擇基站位置來最 化所提供的遠程通信量，這是基于使 更復雜的信號追蹤 法以及不均勻的容量要求。Matthias 等[162]解決了針對特定的遠程通信需求從可能的基站位置選擇基站位置的問題，以便盡可能多地在 UMTS 絡中提供遠程通信。Gonzalez-Brevis 等[163]研究了基站位置和優(yōu)化分配的組合問題，以此優(yōu)化蜂窩 絡的能量效率。Nakayama 等[164]提出了 種具有射線反射回程架構(gòu)的自治基站（AutonomousBase Station with Optical Reflex Backhaul, ABSORB）的概念
【相似文獻】

相關(guān)期刊論文 前10條

1 崔國璋;;關(guān)于FTA中頂上事件發(fā)生概率的近似算法[J];鐵道勞動安全衛(wèi)生與環(huán)保;1987年01期

2 李致中,史峰;路網(wǎng)上無約束單組列車編組優(yōu)化方法[J];鐵道學報;1988年03期

3 楊延齡,戚文發(fā);關(guān)于最優(yōu)備件問題的近似算法的研究[J];工程數(shù)學學報;1989年01期

4 馬紹漢,王銳;Steiner樹問題的近似算法[J];計算機學報;1989年07期

5 李亮,葉尚輝;工程結(jié)構(gòu)可靠性分析中高維概率積分的一種近似算法[J];應用力學學報;1989年02期

6 馮定謨;在物理教學中培養(yǎng)學生運用近似算法的一些體會[J];物理通報;1957年02期

7 張佳男;肖鳴宇;;帶權(quán)混合支配問題的近似算法研究[J];計算機科學;2018年04期

8 陳鵬;何凱;余肖生;;基于證據(jù)等級的非主觀近似算法[J];重慶理工大學學報(自然科學);2018年09期

9 王敏;王蕾;馮曉兵;曹寶香;;基于頂點加權(quán)的介度中心近似算法研究[J];計算機研究與發(fā)展;2016年07期

10 申培萍;張永俊;梁彥超;;一類廣義分式規(guī)劃問題的ε-近似算法[J];計算數(shù)學;2014年03期

相關(guān)博士學位論文 前10條

1 張明會;在線裝箱與混合流水調(diào)度問題近似算法研究[D];大連理工大學;2019年

2 劉曉非;三類優(yōu)化問題的算法設計與分析[D];云南大學;2017年

3 冉穎麗;若干覆蓋問題的近似算法設計與分析[D];新疆大學;2018年

4 潘銳;設施選址與K-中間點問題的復雜性與近似算法[D];山東大學;2007年

5 陳仕平;若干組合優(yōu)化問題的近似算法設計與分析[D];浙江大學;2002年

6 趙曉凡;在線裝箱問題相關(guān)近似算法研究[D];北京交通大學;2016年

7 楊偉鈞;面向物聯(lián)網(wǎng)的QoS路由近似算法研究[D];廣東工業(yè)大學;2017年

8 丁紅林;限制性路由與網(wǎng)絡構(gòu)建問題[D];云南大學;2014年

9 彭茂;圖的控制集的一些相關(guān)問題的研究[D];上海交通大學;2008年

10 黎煜;帶次模特性的倉庫選址問題研究[D];北京交通大學;2012年

相關(guān)碩士學位論文 前10條

1 田世磊;無線網(wǎng)絡中多跳中繼的部署問題[D];上海交通大學;2018年

2 李秋琦;限制性路增廣問題[D];云南大學;2017年

3 張倫緯;具有邊長為1或2的最大貨郎問題[D];云南大學;2017年

4 王路凡;兩類非凸規(guī)劃問題的近似算法[D];河南師范大學;2018年

5 盛海云;[D];南京師范大學;2018年

6 孫建;[D];南京師范大學;2018年

7 李偉娟;堆場作業(yè)的兩個優(yōu)化模型與算法[D];杭州電子科技大學;2018年

8 黃浩;擬樹形圖構(gòu)建問題[D];云南大學;2017年

9 張崇蘭;平方度量的容錯設施布局問題的近似算法[D];北京工業(yè)大學;2018年

10 李曉婷;最小k-路點覆蓋問題的近似算法[D];浙江師范大學;2017年

本文編號：2880109