一種車輛異構(gòu)網(wǎng)絡(luò)選擇最新算法
相關(guān)鏈接： 中國安全網(wǎng) 中國質(zhì)量網(wǎng) 中國論文網(wǎng) 中國資訊網(wǎng)
作者：鄭曉蒙
1 引言
隨著無線通信技術(shù)的快速發(fā)展，移動接入網(wǎng)絡(luò)的多樣化和異構(gòu)性將成為智能交通系統(tǒng)(intelligent transportationsystem，ITS)的重要特征。在流動性大、拓撲變化快的車輛通信網(wǎng)絡(luò)中，單一網(wǎng)絡(luò)無法滿足多種車輛應用的服務質(zhì)量需求，而在異構(gòu)網(wǎng)絡(luò)環(huán)境下，車輛可根據(jù)網(wǎng)絡(luò)特性選擇適合自身需求的接入網(wǎng)絡(luò)，從而獲得較高的服務質(zhì)量。因此，如何尋求最佳的車輛異構(gòu)網(wǎng)絡(luò)選擇策略，使得車輛選擇最合適、最有效的接入網(wǎng)絡(luò)已成為智能交通領(lǐng)域的一個熱點問題。
目前，車輛自組織網(wǎng)絡(luò)(vehicular Ad Hoc network，VANET)是一種應用廣泛的通信接入網(wǎng)絡(luò)，它基于移動自組織網(wǎng)絡(luò)技術(shù)，可以靈活地實現(xiàn)車輛間( vehicle-to-vehicle，V2V)以及車輛與路邊單元間(vehicle-to-RSU，V2R)的數(shù)據(jù)通信。除此之外，以3G(WCDMA/TD-SCDMA/cdma2000)、4G(TDD/FDD LTE)等通信技術(shù)為代表的通用移動通信系統(tǒng)(universal mobile telecommunications system,UMTS)，基于IEEE 802.lla/b/g/n/ac標準的無線局域網(wǎng)絡(luò)(wirelesslocal area network,WLAN)和基于IEEE 802.16系列標準的無線城域網(wǎng)也逐步成為車輛接入網(wǎng)絡(luò)的幾種主要方式，各異構(gòu)接入網(wǎng)絡(luò)適用于不同的應用場景并提供不同質(zhì)量
的服務，如圖1所示。異構(gòu)網(wǎng)絡(luò)環(huán)境下的網(wǎng)絡(luò)選擇是指在多種覆蓋網(wǎng)絡(luò)中選擇一種最優(yōu)的網(wǎng)絡(luò)接入方式，使得系統(tǒng)在此方式下目標值（帶寬、時延、服務質(zhì)量等）可以達到最佳。傳統(tǒng)的異構(gòu)網(wǎng)絡(luò)選擇機制通常以用戶為中心，通過考慮用戶滿意度或效用函數(shù)，基于某些特定性能參數(shù)的特點，采取不同的選擇標準以決定網(wǎng)絡(luò)選擇判決策略。此外，為了克服傳統(tǒng)判決策略不夠靈活的特點，參考文獻[14，15]將網(wǎng)絡(luò)選擇建模為博弈問題，從網(wǎng)絡(luò)側(cè)以博弈方式對用戶進行分配，并引入網(wǎng)絡(luò)容量和效率等以解決可能的沖突問題；在此基礎(chǔ)上，參考文獻[16]引入了經(jīng)濟學模型中的定價機制來解決網(wǎng)絡(luò)的資源分配問題。
上述研究大都只著眼于一個角度，進行網(wǎng)絡(luò)選擇時要么只考慮用戶側(cè)，要么只考慮網(wǎng)絡(luò)側(cè)，從而降低了網(wǎng)絡(luò)的整體收益。因此，在限定條件下，車輛和網(wǎng)絡(luò)如何進行有效的相互選擇成為車輛異構(gòu)網(wǎng)絡(luò)一個重要的研究方向。本文提出了一種新的基于穩(wěn)定匹配博弈的車輛異構(gòu)網(wǎng)絡(luò)選擇算法，將網(wǎng)絡(luò)選擇過程建模為一對多雙邊匹配問題，通過博弈使用戶側(cè)和網(wǎng)絡(luò)側(cè)實現(xiàn)雙向選擇，從而達到穩(wěn)定匹配提升異構(gòu)網(wǎng)絡(luò)選擇整體性能的目的。
2 匹配博弈相關(guān)概念
2.1 匹配博弈問題
匹配博弈起源于男女婚配問題及大學錄取問題的相關(guān)研究，在婚配問題中，每位男士最多只能與一位女士匹配，反之亦然，這種情形下的匹配稱為一對一雙邊匹配。在大學錄取問題中，每所學�？烧惺斩嗝麑W生，而每位學生只能進入一所學校，這種情形下的匹配稱為一對多雙邊匹配。匹配博弈的雙方隸屬于兩個互不相交的主體集合，且位置不能互換，相互間只有經(jīng)過雙方一致同意才能形成匹配。若每一個參與者的匹配對象都是可接受的，且不存在一對匹配參與者，他們都偏好于匹配其他未匹配者，則這樣的匹配為穩(wěn)定匹配。Gale等人分別于1962年和1985年證明了匹配博弈中穩(wěn)定匹配的存在性以及穩(wěn)定匹配就是匹配博弈的均衡點；Roth和Demange等人的研究表明，對于網(wǎng)絡(luò)選擇的匹配博弈模型，通過參與人的獨立決策，最終能夠收斂于穩(wěn)定匹配；Irving等人在此基礎(chǔ)上著重分析了一對多雙邊匹配中強穩(wěn)定性的概念；Martinez等人研究了在個體理性條件一對多雙邊匹配的穩(wěn)定匹配條件，并給出阻礙穩(wěn)定對相關(guān)定理；Wang等人的研究進一步表明穩(wěn)定匹配是一種納什均衡狀態(tài)。
車輛異構(gòu)網(wǎng)絡(luò)場景包含多種接入網(wǎng)絡(luò)和眾多車輛用戶，每種接入網(wǎng)絡(luò)都可以為多個車輛提供接入服務，而每個用戶同時只能接入單一網(wǎng)絡(luò)，那么車輛異構(gòu)網(wǎng)絡(luò)選擇問題可以建模為一對多雙邊匹配博弈。為了便于分析，記網(wǎng)絡(luò)側(cè)為甲方，用戶為乙方，在第2.2節(jié)和第2.3節(jié)中通過給出相關(guān)定義來闡述一對多雙邊匹配和穩(wěn)定一對多雙邊匹配的概念。
2.2 -對多雙邊匹配
設(shè)甲方主體集合為A={A．A2，…A,，…A。}，其中A。代表第i個甲方主體，i∈，；乙方主體集合為B={B．，B：，…，Bj，…，B。)，其中B，代表第j個乙方主體，j EJ;A．期望匹配的乙方主體數(shù)目為c：
；令，：{1，2，…，m），J={l，2，…，n），z：(1，2，…，d)。根據(jù)參考文獻[25，26]，給出如下定義，對一對多雙邊匹配的相關(guān)概念進行描述。
由定義5和定義6可知，在雙方主體集合間所有的穩(wěn)定一對多雙邊匹配中，甲方的最優(yōu)穩(wěn)定匹配是使甲方序值和最小的匹配，乙方的最優(yōu)穩(wěn)定匹配是使乙方序值和最小的匹配。由于序值越小，其對應的滿意度越高，因此也可認為甲方最優(yōu)穩(wěn)定匹配是使甲方滿意度最高的穩(wěn)定匹配，乙方最優(yōu)穩(wěn)定匹配是使乙方滿意度最高的穩(wěn)定匹配。
3基于匹配博弈的網(wǎng)絡(luò)選擇算法
3.1 系統(tǒng)模型
為實現(xiàn)車輛在任何地區(qū)任何時間靈活、高效地接入網(wǎng)絡(luò)，車聯(lián)網(wǎng)中的異構(gòu)網(wǎng)絡(luò)場景通常包含多個接入網(wǎng)絡(luò)，例如公眾WLAN、3 G/4G移動蜂窩網(wǎng)絡(luò)、車載Ad Hoc網(wǎng)絡(luò)(VANET)、WiMAX網(wǎng)絡(luò)等，每種類型的接入網(wǎng)絡(luò)都能為用戶（車輛）提供接人服務，車輛可以接人任何單一網(wǎng)絡(luò)但不限制于特定網(wǎng)絡(luò)。這樣，網(wǎng)絡(luò)側(cè)和用戶側(cè)構(gòu)成互不相交的兩個主體集合，分別由A =(A。l/=l，2，3，4)和B=(Bjlj=l，2，…，凡)表示，其中A。代表上述4種接入網(wǎng)絡(luò)，B，代表位于覆蓋區(qū)的車輛用戶。由第2節(jié)分析可知，車輛異構(gòu)網(wǎng)絡(luò)的接入選擇為一對多雙邊匹配博弈過程，如圖2所示，用戶集合和網(wǎng)絡(luò)集合之間在一定的決策條件下進行雙向的相互選擇，同時用戶側(cè)和網(wǎng)絡(luò)側(cè)由于都有各自的需求及目標，每個決策或動作都可以被認為是理性的。假設(shè)某個時刻在異構(gòu)網(wǎng)絡(luò)的多重覆蓋區(qū)域內(nèi)存在多個車輛用戶，為了便于分析，認為車輛可選擇接入的網(wǎng)絡(luò)集合是相同的，每個車輛用戶每時刻只能接人單一網(wǎng)絡(luò)，而每個接入網(wǎng)絡(luò)每時刻能夠接人多個車輛用戶。在此場景下，影響網(wǎng)絡(luò)和用戶雙方選擇的因素有很多，在用戶側(cè)，車輛需要根據(jù)自身的參數(shù)及需求選擇一個最優(yōu)的接入網(wǎng)絡(luò)，同樣網(wǎng)絡(luò)側(cè)也需要根據(jù)自身的信道及資源狀態(tài)來選擇合適的車輛用戶。同時，每種因素對接人選擇的影響程度也不同，因此需要確定每個因素的權(quán)重系數(shù)，進而綜合考慮得到各主體元素的滿意度序值。本文所提出的網(wǎng)絡(luò)選擇算法核心思想是在穩(wěn)定匹配的條件下，通過層次分析法給出網(wǎng)絡(luò)側(cè)和用戶側(cè)的滿意度序值矩陣，并．利用此序值矩陣求解出使得雙方主體滿意度都盡可能大的一對多雙邊匹配結(jié)果。
其中，
分別為網(wǎng)絡(luò)側(cè)和用戶側(cè)各判決參數(shù)的影響權(quán)重，為了達到最優(yōu)化的選擇，本文采用層次分析法來賦予不同的權(quán)重系數(shù)。
(1)建立層次結(jié)構(gòu)模型
分析網(wǎng)絡(luò)選擇問題，根據(jù)有關(guān)參數(shù)的屬性劃分不同的層次，一般將問題分為目標層、準則層和方案層，同一層中的參數(shù)從屬于上層參數(shù)同時支配下層參數(shù)。本文建立的層次結(jié)構(gòu)模型如圖3所示，由于網(wǎng)絡(luò)側(cè)和用戶側(cè)的判決參數(shù)一致，故均可按此分層模型計算權(quán)重值。
(2)構(gòu)造判斷矩陣
對圖3的層次模型，設(shè)全部判決參數(shù)變量X={x1，X2，…，z。}，每次選取兩個變量Xi和Xj，兩兩比較其相對重要程度，得到兩兩比較判斷矩陣。
其中，Q中元素應滿足
。
經(jīng)大量實驗得出，關(guān)于喲通常以1～9作為標度得到的結(jié)果最優(yōu)，見表1。
表1判斷矩陣中標度及含義
(3)計算權(quán)重
(4)-致性檢驗
由于判斷矩陣Q的確定具有主觀性，因此需對其進行一致性檢驗，分別計算矩陣的一致性指標C．和隨機一致性比率CR。
多目標優(yōu)化模型(19)可轉(zhuǎn)化為如下單目標優(yōu)化模型：
其中，w，和w：分別為目標uy1和uy2的權(quán)重，w-≥0，0)2≤1，∞．+w2=1反映了雙方主體在匹配決策過程中的偏重程度。在實際車輛異構(gòu)網(wǎng)絡(luò)的接入選擇問題中，考慮到網(wǎng)絡(luò)側(cè)和用戶側(cè)雙方博弈的公平性，一般取C01=C02=0.5。由于式(21)（目標函數(shù)）和式(22)（約束條件）均為線性，故可通過整數(shù)規(guī)劃方法對此優(yōu)化模型進行求解，若網(wǎng)絡(luò)選擇問題的主體規(guī)模較大，也可采用智能優(yōu)化算法或啟發(fā)式搜索來求解匹配結(jié)果。
4仿真分析及結(jié)果
本文通過仿真實驗對所提算法的正確性和有效性進行驗證，仿真場景為圖l中的異構(gòu)網(wǎng)絡(luò)重疊覆蓋區(qū)，區(qū)域內(nèi)有多個車輛用戶，且存在UMTS、WiMAX、WLAN以及VANET 4種網(wǎng)絡(luò)，不同網(wǎng)絡(luò)的狀態(tài)參數(shù)各不相同，考慮在此場景下，車輛和網(wǎng)絡(luò)進行雙向網(wǎng)絡(luò)選擇的情況。根據(jù)參考文獻[31]所進行的相關(guān)研究，假設(shè)有n個車輛用戶均勻分布在異構(gòu)網(wǎng)絡(luò)覆蓋區(qū)域，其運行速度均為40 km/h，車輛用戶有4種類型的業(yè)務服務需求：會話類業(yè)務、流媒體業(yè)務、交互類業(yè)務和背景類業(yè)務，不同業(yè)務類型的典型應用和QoS特性見表2。
在某網(wǎng)絡(luò)選擇時刻，為獲得穩(wěn)定雙邊匹配，需要對網(wǎng)絡(luò)和用戶雙方的參數(shù)進行分析，假設(shè)每個用戶隨機分配表2中的4種業(yè)務之一，首先給出車輛用戶的業(yè)務需求和各網(wǎng)絡(luò)的狀態(tài)信息，見表3和表4。
在給定用戶業(yè)務和網(wǎng)絡(luò)狀態(tài)參數(shù)后，對網(wǎng)絡(luò)和用戶雙方主體的滿意度偏好值進行分析，采用層次分析法分別對雙方主體的參數(shù)權(quán)重進行計算。需要注意的是，在計算層次結(jié)構(gòu)中的第二層權(quán)重時，需區(qū)分不同的用戶業(yè)務和網(wǎng)絡(luò)類型，根據(jù)業(yè)務對QoS的需求等相關(guān)信息調(diào)整判決參數(shù)的比較矩陣。以會話類業(yè)務為例，最終所求得的網(wǎng)絡(luò)側(cè)和用戶側(cè)參數(shù)主判斷矩陣見表5和表6。
采用層次分析法獲得相應參數(shù)權(quán)重后，可計算得到網(wǎng)絡(luò)和用戶各主體的滿意度及排序后的序值向量，圖4和圖5分別給出了在不同業(yè)務類型條件下，用戶選擇網(wǎng)絡(luò)和網(wǎng)絡(luò)選擇用戶的滿意度偏好值。算法利用此滿意度序值向量，通過求解最優(yōu)化模型得到網(wǎng)絡(luò)選擇的穩(wěn)定匹配結(jié)果。
為了分析基于匹配博弈的網(wǎng)絡(luò)選擇算法的性能，將算法與參考文獻[10]和參考文獻[14]中的兩種經(jīng)典算法進行了仿真對比，其中一種算法是由用戶主導進行網(wǎng)絡(luò)接入決策，另一種是由網(wǎng)絡(luò)主導進行網(wǎng)絡(luò)接人決策，比較結(jié)果如圖6和圖7所示�？梢钥吹剿崴惴ǖ钠骄鶟M意度位于兩種經(jīng)典算法之間，表明其綜合考慮了網(wǎng)絡(luò)方的利益以及用戶的服務體驗，在用戶主導和網(wǎng)絡(luò)主導的兩種算法中找到一個均衡點，得到了使網(wǎng)絡(luò)和用戶雙方滿意度最優(yōu)化的網(wǎng)絡(luò)接入模式，提高了網(wǎng)絡(luò)資源的利用率。
5結(jié)束語
本文提出了一種適用于車輛異構(gòu)網(wǎng)絡(luò)場景的網(wǎng)絡(luò)選擇算法，不同于傳統(tǒng)的僅考慮用戶側(cè)或網(wǎng)絡(luò)側(cè)的選擇判決策略，該算法基于一對多雙邊匹配博弈模型和層次分析法，充分考慮車輛移動性、業(yè)務服務質(zhì)量需求、服務價格和網(wǎng)絡(luò)帶寬等影響車輛異構(gòu)網(wǎng)絡(luò)選擇的因素，獲得相應權(quán)重分配，以給出滿意度函數(shù)，并構(gòu)建多目標優(yōu)化模型，將一對多匹配轉(zhuǎn)化為一對一匹配問題，通過用戶側(cè)與網(wǎng)絡(luò)側(cè)的雙向選擇得到網(wǎng)絡(luò)選擇博弈模型的穩(wěn)定匹配。通過仿真驗證表明，基于穩(wěn)定匹配的博弈模型相對傳統(tǒng)決策模型能夠使網(wǎng)絡(luò)和用戶側(cè)雙方的滿意度最優(yōu)化，從而達到博弈的均衡狀態(tài)。該算法可以充分提高資源的利用率，實現(xiàn)負載均衡，在同時存在多個可選網(wǎng)絡(luò)的車輛異構(gòu)網(wǎng)絡(luò)環(huán)境中具有一定的實用前景。
6摘要：
針對車輛在異構(gòu)網(wǎng)絡(luò)覆蓋環(huán)境下的網(wǎng)絡(luò)接入選擇問題，基于雙邊匹配博弈中穩(wěn)定匹配的相關(guān)概念，提出一種車輛異構(gòu)網(wǎng)絡(luò)選擇博弈模型，通過用戶側(cè)與網(wǎng)絡(luò)側(cè)的雙向選擇得到異構(gòu)網(wǎng)絡(luò)選擇的穩(wěn)定匹配。算法首先利用層次分析法獲得相應權(quán)重分配以給出滿意度函數(shù)，然后將網(wǎng)絡(luò)側(cè)的一對多匹配轉(zhuǎn)化為一對一匹配問題，在穩(wěn)定匹配條件下構(gòu)建多目標優(yōu)化模型，并求解最優(yōu)匹配結(jié)果。相關(guān)性能分析及仿真實驗表明，基于穩(wěn)定匹配的博弈模型相對于傳統(tǒng)決策模型，能夠使網(wǎng)絡(luò)和用戶側(cè)雙方的滿意度最優(yōu)化，從而得到雙向網(wǎng)絡(luò)選擇的均衡狀態(tài)。
