車(chē)輛WiFi接入互聯(lián)網(wǎng)中基于軌跡的下載任務(wù)調(diào)度研究.pdf

1、車(chē)載網(wǎng)絡(luò)是車(chē)輛間、車(chē)輛與路邊基礎(chǔ)設(shè)施之間通過(guò)無(wú)線(xiàn)連接形成的一種拓?fù)鋭?dòng)態(tài)變化的無(wú)線(xiàn)移動(dòng)網(wǎng)絡(luò)。路邊基礎(chǔ)設(shè)施分為兩類(lèi)，一類(lèi)通過(guò)有線(xiàn)接入Internet，通常簡(jiǎn)稱(chēng)為AP(Access Point)，另一類(lèi)只提供簡(jiǎn)單的存儲(chǔ)轉(zhuǎn)發(fā)，簡(jiǎn)稱(chēng)RSU(RoadSide Unit)。在車(chē)載網(wǎng)絡(luò)中，車(chē)輛之間、車(chē)輛與RSU之間主要通過(guò)Ad Hoc方式相連，而車(chē)輛與路邊基礎(chǔ)設(shè)施之間則主要通過(guò)WiFi方式連接。
　　車(chē)載用戶(hù)通過(guò)車(chē)載網(wǎng)絡(luò)接入 Internet獲得

2、各種信息服務(wù)，如查詢(xún)商場(chǎng)、飯店、加油站、交通管理、路況及最新的天氣、新聞等。當(dāng)然，車(chē)載用戶(hù)也可以通過(guò)3G或衛(wèi)星獲得上述服務(wù)，但其費(fèi)用比較昂貴，而通過(guò)AP一般可以免費(fèi)獲得高性能的Internet鏈接。因此，如何充分利用AP為車(chē)載用戶(hù)提供Internet接入服務(wù)、尤其是數(shù)據(jù)下載服務(wù)是目前車(chē)載網(wǎng)絡(luò)中的重要研究?jī)?nèi)容。
　　雖然各國(guó)政府都在投入大量資金部署各種 AP，但仍無(wú)法滿(mǎn)足日益增長(zhǎng)的車(chē)載用戶(hù)對(duì)Internet的下載請(qǐng)求。目前，即使在較

3、發(fā)達(dá)的城市中，AP的通信范圍也還不能完全覆蓋街道上行駛的車(chē)輛，我們將兩個(gè)相鄰 AP之間未被AP通信覆蓋的區(qū)域稱(chēng)為鏈接空洞。進(jìn)入鏈接空洞的車(chē)載用戶(hù)將無(wú)法通過(guò)WiFi方式接入Internet，但可以通過(guò)Ad Hoc方式通過(guò)其周?chē)钠渌?chē)載節(jié)點(diǎn)經(jīng)多跳接入Internet。
　　在AP不能完全滿(mǎn)足車(chē)載用戶(hù)下載請(qǐng)求的條件下，各個(gè) AP可以通過(guò)對(duì)其接收到的下載請(qǐng)求進(jìn)行調(diào)度，以便提高整個(gè)車(chē)載網(wǎng)絡(luò)的服務(wù)能力。顯然，那些可以為更多相鄰節(jié)點(diǎn)提供轉(zhuǎn)發(fā)服

4、務(wù)的車(chē)載節(jié)點(diǎn)的請(qǐng)求應(yīng)該被優(yōu)先調(diào)度執(zhí)行，因此，AP調(diào)度的核心任務(wù)就是為其覆蓋范圍內(nèi)的車(chē)載節(jié)點(diǎn)確定一種優(yōu)先級(jí)，優(yōu)先級(jí)高的節(jié)點(diǎn)的請(qǐng)求將被優(yōu)先調(diào)度執(zhí)行。
　　車(chē)載節(jié)點(diǎn)的調(diào)度優(yōu)先級(jí)主要取決于相鄰節(jié)點(diǎn)的下載請(qǐng)求類(lèi)別及車(chē)載網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，由于下載請(qǐng)求的類(lèi)別比較容易判別，而車(chē)載網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)卻是動(dòng)態(tài)變化的，因此如何獲取車(chē)載網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)并利用其確定節(jié)點(diǎn)的調(diào)度優(yōu)先級(jí)就是AP調(diào)度的一個(gè)關(guān)鍵問(wèn)題。
　　本文主要研究基于動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)涞能?chē)載節(jié)點(diǎn)下載任

5、務(wù)調(diào)度問(wèn)題，車(chē)載網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)主要跟車(chē)輛的行駛軌跡有關(guān)。有些車(chē)輛(如出租車(chē))會(huì)定期向服務(wù)器發(fā)送其GPS信息，這類(lèi)車(chē)輛形成的軌跡信息是確定的，而其他車(chē)輛的軌跡信息則往往是不確定的，因此，本文基于車(chē)輛軌跡信息確定和不確定兩種情況對(duì)AP下載任務(wù)調(diào)度開(kāi)展了如下幾個(gè)方面的研究：
　　首先，在車(chē)輛軌跡信息確定的情況下，研究了基于鏈接空洞區(qū)域車(chē)輛間Ad Hoc連接的AP下載任務(wù)調(diào)度問(wèn)題。
　　由于進(jìn)入鏈接空洞的車(chē)載用戶(hù)只能通過(guò)那些已經(jīng)獲得

6、所需信息的相鄰節(jié)點(diǎn)下載所需信息，因此進(jìn)入鏈接空洞后能為更多相鄰車(chē)輛提供轉(zhuǎn)發(fā)服務(wù)的節(jié)點(diǎn)應(yīng)該具有更高的調(diào)度優(yōu)先級(jí)。為此，本文研究了使鏈接空洞區(qū)域數(shù)據(jù)下載總量最大的AP任務(wù)調(diào)度集求解問(wèn)題，并證明了該問(wèn)題是NP-完全的，于是，本文提出了一種JAS近似算法來(lái)對(duì)該問(wèn)題進(jìn)行求解，實(shí)驗(yàn)結(jié)果表明該算法是有效的。
　　然后，在車(chē)輛軌跡信息不確定的情況下，研究了基于鏈接空洞區(qū)域車(chē)輛間機(jī)會(huì)鏈接的AP下載任務(wù)調(diào)度問(wèn)題。
　　雖然車(chē)輛軌跡信息不確定時(shí)無(wú)

7、法確定鏈接空洞區(qū)域車(chē)輛間的連接情況，但利用車(chē)輛的當(dāng)前行駛情況可以預(yù)測(cè)下一時(shí)段前方車(chē)輛間的鏈接情況，基于這種通過(guò)預(yù)測(cè)建立起來(lái)的機(jī)會(huì)可達(dá)圖，本文研究了使鏈接空洞區(qū)域數(shù)據(jù)下載成功率最高的AP任務(wù)調(diào)度集求解問(wèn)題，并證明了該問(wèn)題是 NP-完全的，為此，本文提出了一種基于機(jī)會(huì)可達(dá)圖的任務(wù)調(diào)度近似算法，實(shí)驗(yàn)結(jié)果表明該算法是有效的。
　　其次，在車(chē)輛行駛過(guò)程中不經(jīng)過(guò) AP的情況下，研究了基于節(jié)點(diǎn)間機(jī)會(huì)鏈接歷史統(tǒng)計(jì)信息的無(wú)AP任務(wù)調(diào)度問(wèn)題。

8、　　如果車(chē)輛在行駛過(guò)程中不經(jīng)過(guò)任何 AP，仍然可以通過(guò)多跳攜帶-轉(zhuǎn)發(fā)的方式獲得所需要的信息，但需要其他車(chē)輛充當(dāng)它的移動(dòng)網(wǎng)關(guān)(簡(jiǎn)稱(chēng)MG)，路線(xiàn)固定、運(yùn)行特征可預(yù)測(cè)的公交車(chē)就是最理想的移動(dòng)網(wǎng)關(guān)。本文研究了基于公交車(chē)移動(dòng)網(wǎng)關(guān)的無(wú) AP下載任務(wù)調(diào)度問(wèn)題，提出了一種最小化傳輸延遲期望的下載任務(wù)調(diào)度方法，實(shí)驗(yàn)結(jié)果表明該方法在滿(mǎn)足下載成功率閾值前提下，能夠獲得最小傳輸延遲期望。
　　最后，為了解決車(chē)載網(wǎng)絡(luò)中 AP負(fù)載不均衡的問(wèn)題，本文研究了基于