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

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

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

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

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

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

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

4 馬紹漢,王銳;Steiner樹問題的近似算法[J];計(jì)算機(jī)學(xué)報(bào);1989年07期

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

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

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

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

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

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

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

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

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

3 冉穎麗;若干覆蓋問題的近似算法設(shè)計(jì)與分析[D];新疆大學(xué);2018年

4 潘銳;設(shè)施選址與K-中間點(diǎn)問題的復(fù)雜性與近似算法[D];山東大學(xué);2007年

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

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

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

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

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

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

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

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

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

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

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

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

6 孫建;[D];南京師范大學(xué);2018年

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

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

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

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

本文編號：2880109