基于改進(jìn)貪婪算法的測(cè)量節(jié)點(diǎn)選擇優(yōu)化方法

吳 上，盛益強(qiáng)，鄧浩江

(1.中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京 100190; 2.中國(guó)科學(xué)院大學(xué)，北京 100049)

0 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展和工業(yè)化水平的不斷進(jìn)步，人們對(duì)于確定性時(shí)延需求越來(lái)越大。然而現(xiàn)有名字解析系統(tǒng)(Name Resolution System, NRS)中普遍沒有進(jìn)行針對(duì)性設(shè)計(jì)。如何在一定規(guī)模的真實(shí)網(wǎng)絡(luò)場(chǎng)景中構(gòu)建網(wǎng)絡(luò)模型，并進(jìn)行快速測(cè)量節(jié)點(diǎn)選點(diǎn)計(jì)算，就成了一個(gè)值得研究的問(wèn)題。本文將測(cè)量節(jié)點(diǎn)選點(diǎn)問(wèn)題抽象為最小點(diǎn)覆蓋問(wèn)題，并結(jié)合具體場(chǎng)景對(duì)傳統(tǒng)貪婪算法進(jìn)行改進(jìn)，從迭代周期、排序算法以及方案評(píng)價(jià)方面進(jìn)行設(shè)計(jì)與實(shí)現(xiàn)，具有一定的應(yīng)用價(jià)值。

1 背 景

互聯(lián)網(wǎng)一直保持以主機(jī)為中心的模型。早期互聯(lián)網(wǎng)在網(wǎng)設(shè)備數(shù)量少，設(shè)備之間可信度較高。互聯(lián)網(wǎng)的設(shè)計(jì)原則使得互聯(lián)網(wǎng)規(guī)模迅速增加?；ヂ?lián)網(wǎng)的沙漏結(jié)構(gòu)中增加了應(yīng)用和服務(wù)的擴(kuò)展性。不斷發(fā)展的各種新應(yīng)用和服務(wù)的發(fā)展帶來(lái)了可擴(kuò)展內(nèi)容分發(fā)、移動(dòng)性、安全性、可信性等問(wèn)題。為了解決這些問(wèn)題，互聯(lián)網(wǎng)架構(gòu)陷入了不斷打補(bǔ)丁的泥潭。未來(lái)網(wǎng)絡(luò)會(huì)存在越來(lái)越多的信息傳播需求，而非主機(jī)間的成對(duì)通信需求。為此，信息中心網(wǎng)絡(luò)(Information Centric Networking, ICN))應(yīng)運(yùn)而生。ICN通過(guò)在網(wǎng)絡(luò)層對(duì)名字命名，天然地支持網(wǎng)內(nèi)緩存、多播和移動(dòng)性需求，能夠應(yīng)對(duì)未來(lái)網(wǎng)絡(luò)需求[1]。

物聯(lián)網(wǎng)(Internet of Things, IoT)特別是工業(yè)互聯(lián)網(wǎng)(Industrial Internet of Things, IIoT)的快速發(fā)展，對(duì)現(xiàn)有網(wǎng)絡(luò)架構(gòu)也提出了更高的要求，不僅要求具有較低的平均網(wǎng)絡(luò)延時(shí)，更要求實(shí)現(xiàn)確定性網(wǎng)絡(luò)時(shí)延保障。盡管人們采用了包括邊緣計(jì)算在內(nèi)的新技術(shù)降低計(jì)算時(shí)延，但變化不定的網(wǎng)絡(luò)傳輸時(shí)延仍是亟待優(yōu)化的關(guān)鍵因素。因此，第5代通信技術(shù)(The Fifth Generation Communication Networks, 5G)作為下一代通信技術(shù)，其憑借超大規(guī)模并發(fā)連接，超低延時(shí)的特點(diǎn)受到了工業(yè)界的廣泛關(guān)注和應(yīng)用嘗試[2]。

隨著IMT-2020的不斷推進(jìn)，ICN也在不斷地標(biāo)準(zhǔn)化以增強(qiáng)5G網(wǎng)絡(luò)，例如文獻(xiàn)[3]中要求，NRS必須實(shí)現(xiàn)低時(shí)延與擴(kuò)展性的要求以滿足IMT-2020中URLLC(Ultra Reliable and Low Latency Communication)和mMTC(Massive Machine Type Communication)的應(yīng)用場(chǎng)景。同時(shí)還應(yīng)具備移動(dòng)性支持、路由支持和互操作性(Inter-operation)支持。文獻(xiàn)[4]提出了確定性時(shí)延名字解析(Deterministic Latency Name Resolution, DLNR)，通過(guò)將物理網(wǎng)絡(luò)劃分為層級(jí)嵌套的層次彈性結(jié)構(gòu)(Hierarchical Elastic Area, HEA)并為每個(gè)HEA部署服務(wù)于本層級(jí)的名字解析服務(wù)節(jié)點(diǎn)。在對(duì)物理網(wǎng)絡(luò)的劃分過(guò)程中，節(jié)點(diǎn)間時(shí)延是重要依據(jù)之一。

為了獲取節(jié)點(diǎn)間時(shí)延，可以考慮在每個(gè)節(jié)點(diǎn)都部署測(cè)量程序，這在小規(guī)模的網(wǎng)絡(luò)是可行的，但是測(cè)量成本會(huì)隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大指數(shù)級(jí)別上升。文獻(xiàn)[5-6]討論了內(nèi)容中心網(wǎng)絡(luò)中少數(shù)關(guān)鍵節(jié)點(diǎn)是否在線會(huì)影響整個(gè)網(wǎng)絡(luò)的連通性。為此，考慮到信息中心網(wǎng)絡(luò)的特點(diǎn)及其時(shí)延測(cè)量的需求，本文將網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)部署問(wèn)題映射成為最小點(diǎn)覆蓋問(wèn)題，并基于傳統(tǒng)的貪婪算法提出一種面向網(wǎng)絡(luò)測(cè)量節(jié)點(diǎn)選取的改進(jìn)貪婪算法，優(yōu)化傳統(tǒng)貪婪算法的迭代模塊和排序算法以改進(jìn)其在實(shí)際應(yīng)用中的適配性，實(shí)驗(yàn)表明取得了預(yù)期的效果。

2 現(xiàn)有最小頂點(diǎn)覆蓋求解算法

很多文獻(xiàn)將非圖論問(wèn)題抽象為最小頂點(diǎn)覆蓋問(wèn)題求解，比如文獻(xiàn)[7]將現(xiàn)實(shí)生活中的共享單車投放問(wèn)題映射為求解圖的覆蓋問(wèn)題，文獻(xiàn)[8]利用子圖分解研究了多運(yùn)動(dòng)目標(biāo)視頻跟蹤問(wèn)題，文獻(xiàn)[9]利用圖表示學(xué)習(xí)方法解決了動(dòng)態(tài)網(wǎng)絡(luò)異常檢測(cè)問(wèn)題等。

圖的頂點(diǎn)覆蓋指的是在圖G=(V,E)中選出部分點(diǎn)的集合，使得圖中所有的邊都與之相連。最小頂點(diǎn)覆蓋問(wèn)題(Minimum Vertex Cover, MVC)是求解滿足上述要求的最小點(diǎn)集。最小頂點(diǎn)覆蓋有著非常多的應(yīng)用場(chǎng)景，如文獻(xiàn)[10]設(shè)計(jì)了一種掃描測(cè)試向量生成算法。如果按照解決問(wèn)題的時(shí)間復(fù)雜度分類，不能在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題叫做NP問(wèn)題。對(duì)于這類問(wèn)題，在待求解問(wèn)題規(guī)模很大的情況下時(shí)間開銷是難以接受的。NP完全問(wèn)題包括2個(gè)基本要求，一個(gè)要求是問(wèn)題本身必須為NP問(wèn)題，另一個(gè)要求是應(yīng)當(dāng)可以在多項(xiàng)式時(shí)間內(nèi)歸約為NP問(wèn)題[11]。文獻(xiàn)[12]完成了最小頂點(diǎn)覆蓋問(wèn)題是NP完全問(wèn)題的證明。因此，最小頂點(diǎn)覆蓋問(wèn)題可以通過(guò)精確算法和近似算法求解。雖然前者最終會(huì)得到精確的結(jié)果，但是在求解大規(guī)模問(wèn)題時(shí)所耗費(fèi)的計(jì)算能力和時(shí)間是難以接受的，故該類精確算法只適用于解決小規(guī)模問(wèn)題。而后者則在犧牲了一定精度的情況下能夠在多項(xiàng)式時(shí)間內(nèi)求解相應(yīng)問(wèn)題，在實(shí)際中受到廣泛應(yīng)用。常見的近似算法有以下幾種：

1)貪婪算法。貪婪算法是解決點(diǎn)覆蓋問(wèn)題的經(jīng)典算法之一，最早在文獻(xiàn)[13]中提出，后來(lái)文獻(xiàn)[14]提出了MDA(Maximum Degree Algorithm)算法。其核心思想在于求解度最大的節(jié)點(diǎn)并依次迭代刪去。文獻(xiàn)[15]提出了VSA(Vertex Support Algorithm)算法，其主要工作在于設(shè)計(jì)了頂點(diǎn)支撐參數(shù)，定義頂點(diǎn)鄰居的度數(shù)之和作為頂點(diǎn)支撐。文獻(xiàn)[16]基于貪婪算法提出了MAMA(Maximum Adjacent Minimum degree Algorithm)算法，通過(guò)利用頂點(diǎn)支撐參數(shù)排序求解最小頂點(diǎn)覆蓋問(wèn)題，在小規(guī)模網(wǎng)絡(luò)中有著較好的實(shí)驗(yàn)效果。

2)蟻群算法。文獻(xiàn)[17]最早通過(guò)模擬螞蟻經(jīng)過(guò)路徑上的信息素，使得群體具備一定的智能，經(jīng)過(guò)一段時(shí)間，連續(xù)不斷的正反饋就能形成一個(gè)近似解。文獻(xiàn)[18]將分布式網(wǎng)絡(luò)測(cè)量中的測(cè)量節(jié)點(diǎn)部署問(wèn)題抽象為最小頂點(diǎn)覆蓋，并基于蟻群算法提出了求解，以性能上的部分代價(jià)換取了更低的近似比。

3)遺傳算法。文獻(xiàn)[19]模擬了生物學(xué)中的“物競(jìng)天擇，適者生存”，能夠同時(shí)處理多個(gè)研究對(duì)象，有效擴(kuò)大搜索范圍，避免了陷入局部最優(yōu)。

類似的還有基于膜系統(tǒng)的解決方法，如文獻(xiàn)[20]。由于篇幅所限，不再一一說(shuō)明。

以上算法大多只考慮了算法的一個(gè)方面，例如大多算法都在比較小規(guī)模場(chǎng)景中的近似比，試圖將近似比向1逼近；部分算法考慮的應(yīng)用范圍過(guò)于局限，無(wú)法結(jié)合ICN名字解析系統(tǒng)的物理網(wǎng)絡(luò)劃分實(shí)際情況。為此，本文基于傳統(tǒng)貪婪算法，通過(guò)優(yōu)化算法結(jié)構(gòu)，結(jié)合實(shí)際應(yīng)用場(chǎng)景提出一種改進(jìn)的貪婪算法(Improved Greedy Algorithm, IGA)。

3 算法內(nèi)容

廣義上來(lái)說(shuō)，貪婪算法，其核心是通過(guò)迭代的方式，不斷尋找當(dāng)前的最優(yōu)解，直到收斂為止。這是一個(gè)雖然簡(jiǎn)單但是十分有效的近似算法，試圖以不斷的局部最優(yōu)結(jié)果逼近全局最優(yōu)結(jié)果。本章分別介紹傳統(tǒng)貪婪算法和改進(jìn)的貪婪算法。

3.1 傳統(tǒng)貪婪算法

傳統(tǒng)貪婪算法通過(guò)計(jì)算各節(jié)點(diǎn)度數(shù)，將度數(shù)排序，循環(huán)選取度數(shù)最大的節(jié)點(diǎn)作為最小點(diǎn)覆蓋集合，直至覆蓋全部邊。偽代碼如下：

Input: G=(V, E)

Output: C

Begin:

1.C←?; //一開始最小點(diǎn)覆蓋為空集

2.While E≠? do {

3.n←|G(V,E)|

4.for i←1 to n {

5.d(vi) //計(jì)算每個(gè)節(jié)點(diǎn)的度數(shù)d

6.}

7.D←d(vi) //對(duì)所有點(diǎn)的度數(shù)進(jìn)行排序

8.t←Δ(G) //選出一個(gè)節(jié)點(diǎn)度數(shù)最大的節(jié)點(diǎn)t

9.V←V-{t} //從全部節(jié)點(diǎn)中刪除節(jié)點(diǎn)t

10.C←C∪{t} //將節(jié)點(diǎn)t加入最小點(diǎn)覆蓋集中

11.Go to 2 }

12.Return C

End

以上偽代碼對(duì)傳統(tǒng)貪婪算法的原理做了詳盡的說(shuō)明。使用該算法對(duì)圖1進(jìn)行求解，可以推理出一種最小點(diǎn)覆蓋的近似解。其中灰色節(jié)點(diǎn)為傳統(tǒng)貪婪算法的求解結(jié)果。

圖1 傳統(tǒng)貪婪算法求解結(jié)果

經(jīng)過(guò)分析，圖1中的節(jié)點(diǎn)并非最小節(jié)點(diǎn)覆蓋的精確結(jié)果。最小點(diǎn)覆蓋集合如圖2中灰色節(jié)點(diǎn)所示，對(duì)比可以發(fā)現(xiàn)：在給定圖例中，傳統(tǒng)貪婪算法求解結(jié)果比最優(yōu)求解方案多出了14%的節(jié)點(diǎn)數(shù)量，說(shuō)明即便在小規(guī)模圖的求解精度上，傳統(tǒng)貪婪算法也不是理想的選擇。

圖2 最小覆蓋集最優(yōu)結(jié)果

此外，該算法的擴(kuò)展性較差，在最壞情況下運(yùn)行復(fù)雜度為O(E2)，即便在中等規(guī)模驗(yàn)證中也不理想。計(jì)算時(shí)間與節(jié)點(diǎn)數(shù)量的關(guān)系如圖3所示。

圖3 節(jié)點(diǎn)數(shù)量與計(jì)算時(shí)間的關(guān)系

3.2 改進(jìn)后的貪婪算法

下面從迭代周期優(yōu)化，面向BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的排序算法優(yōu)化和方案選擇等相關(guān)工作進(jìn)行說(shuō)明。

3.2.1 迭代周期優(yōu)化

圖3可以說(shuō)明，若求解一定規(guī)模下的應(yīng)用問(wèn)題，選擇傳統(tǒng)貪婪算法進(jìn)行計(jì)算是不切實(shí)際的。經(jīng)實(shí)際代碼分析，其擴(kuò)展性差、運(yùn)算開銷大的原因是迭代過(guò)程開銷過(guò)大。具體地，在求解Δ(G)的過(guò)程中涉及大量的排序計(jì)算，傳統(tǒng)貪婪算法中每次循環(huán)過(guò)后都要重新求解度排序，這會(huì)消耗大量的計(jì)算資源。但事實(shí)上這樣僅適用于小規(guī)模場(chǎng)景，當(dāng)實(shí)驗(yàn)規(guī)模較大、節(jié)點(diǎn)數(shù)量較多時(shí)，刪去某個(gè)特定節(jié)點(diǎn)及其邊的過(guò)程并不會(huì)導(dǎo)致節(jié)點(diǎn)度排序的大量變化，從而不需要對(duì)節(jié)點(diǎn)度數(shù)再次排序，因此很多的排序過(guò)程是可以省略的。本文結(jié)合實(shí)際應(yīng)用場(chǎng)景對(duì)迭代周期進(jìn)行探索優(yōu)化，通過(guò)設(shè)計(jì)合適的迭代周期，在提高計(jì)算速度的同時(shí)盡量降低迭代次數(shù)，減少對(duì)精度的不利影響，從而提高模型的求解速度。

3.2.2 面向BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的排序算法優(yōu)化

文獻(xiàn)[21-24]介紹了ICN的結(jié)構(gòu)，在此基礎(chǔ)上，文獻(xiàn)[25]介紹了一種ICN節(jié)點(diǎn)選擇方法，文獻(xiàn)[26]介紹了一種IoT環(huán)境下ICN名字解析方法。這些文獻(xiàn)都沒有考慮到現(xiàn)實(shí)網(wǎng)絡(luò)的規(guī)模效應(yīng)，常用的網(wǎng)絡(luò)模型包括ER隨機(jī)圖模型、WS小世界模型、Waxman網(wǎng)絡(luò)模型以及BA無(wú)標(biāo)度模型等。ER隨機(jī)圖模型指的是任意生成一個(gè)含有N個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)，其中節(jié)點(diǎn)間以概率p進(jìn)行鏈接，此時(shí)其度分布比較接近泊松分布。WS小世界模型指的是節(jié)點(diǎn)間存在非常豐富的短路徑，此時(shí)節(jié)點(diǎn)的度分布也比較接近泊松分布。Waxman網(wǎng)絡(luò)模型與ER隨機(jī)圖模型類似，也是先假設(shè)節(jié)點(diǎn)規(guī)模，再以一定的概率決定節(jié)點(diǎn)間是否存在連接。BA無(wú)標(biāo)度網(wǎng)絡(luò)模型是一種用來(lái)解釋復(fù)雜網(wǎng)絡(luò)的生長(zhǎng)型無(wú)尺度模型，指的是該網(wǎng)絡(luò)上節(jié)點(diǎn)的度符合冪指數(shù)為3的冪律分布，并且賦予該網(wǎng)絡(luò)一定量的初始節(jié)點(diǎn)，而后不斷有新的節(jié)點(diǎn)加入，其包含2個(gè)重要的概念：增長(zhǎng)(Growth)和鏈接傾向(Preferential Attachment)，二者均在現(xiàn)實(shí)世界中普遍存在。前者認(rèn)為網(wǎng)絡(luò)節(jié)點(diǎn)的數(shù)量隨著時(shí)間增長(zhǎng)而增長(zhǎng)，后者認(rèn)為如果一個(gè)節(jié)點(diǎn)所承擔(dān)的鏈接任務(wù)越多，那么在新鏈接建立的過(guò)程中，該節(jié)點(diǎn)就更可能參與新鏈接，即節(jié)點(diǎn)的度越高，其獲取新鏈接的能力越強(qiáng)[27]。BA無(wú)標(biāo)度模型基于真實(shí)大型網(wǎng)絡(luò)數(shù)據(jù)提出，因此本文采用BA無(wú)標(biāo)度模型對(duì)物理網(wǎng)絡(luò)進(jìn)行建模仿真。根據(jù)定義，假設(shè)BA無(wú)標(biāo)度網(wǎng)絡(luò)模型初始節(jié)點(diǎn)為m0，新節(jié)點(diǎn)依次加入，新節(jié)點(diǎn)鏈接到節(jié)點(diǎn)i的概率為：

其中，ki代表節(jié)點(diǎn)i的度數(shù)，j表示已存在的節(jié)點(diǎn)的個(gè)數(shù)。

使用BA無(wú)標(biāo)度模型構(gòu)建100萬(wàn)個(gè)節(jié)點(diǎn)的樣本，樣本平均度為2。節(jié)點(diǎn)的度分布如圖4所示。

圖4 節(jié)點(diǎn)度分布

圖4中橫坐標(biāo)表示節(jié)點(diǎn)度的數(shù)值，縱坐標(biāo)表示樣本中節(jié)點(diǎn)分布頻率。由于樣本數(shù)量已足夠大，因此可以用頻率估計(jì)概率，即大部分節(jié)點(diǎn)的度都集中在1～10之間，這其中大部分節(jié)點(diǎn)的度為1。而這也證實(shí)了BA無(wú)標(biāo)度模型中的鏈接傾向概念。

以上說(shuō)明了BA無(wú)標(biāo)度模型中節(jié)點(diǎn)度分布的特殊性，即大量節(jié)點(diǎn)的度為1，但是個(gè)別節(jié)點(diǎn)的度較高。而傳統(tǒng)貪婪算法對(duì)此并沒有區(qū)分，在每次迭代中都嘗試進(jìn)行節(jié)點(diǎn)度排序。為此本文在算法設(shè)計(jì)方面做了改進(jìn)，先對(duì)模型數(shù)據(jù)進(jìn)行預(yù)處理，再使用改進(jìn)貪婪算法進(jìn)行迭代，具體步驟如下：

1)獲取模型的鄰接矩陣。

2)將鄰接矩陣進(jìn)行降維處理，剔除全部度為1的節(jié)點(diǎn)和與之相連的邊，得到處理后的稀疏矩陣，此時(shí)經(jīng)處理后的稀疏矩陣規(guī)模相比初始矩陣已經(jīng)大大縮減。

3)對(duì)稀疏矩陣進(jìn)行壓縮、求解，得到節(jié)點(diǎn)度排序。

4)運(yùn)行貪婪算法求解最小點(diǎn)覆蓋。

5)在初始鄰接矩陣中刪去最小點(diǎn)覆蓋集合和與之相連的邊，再進(jìn)行迭代排序，一次即可獲得全部最小點(diǎn)覆蓋集合。

后續(xù)實(shí)驗(yàn)證實(shí)，該場(chǎng)景中優(yōu)化排序的時(shí)間復(fù)雜度僅為O(n)，具備良好的擴(kuò)展性。

3.2.3 方案對(duì)比

實(shí)際物理網(wǎng)絡(luò)測(cè)量中，決定節(jié)點(diǎn)是否為測(cè)量節(jié)點(diǎn)的因素除了度數(shù)之外，還應(yīng)考慮節(jié)點(diǎn)本身的硬件條件。定義節(jié)點(diǎn)m權(quán)重如下：

其中：α、β、γ為參數(shù)對(duì)應(yīng)的動(dòng)態(tài)權(quán)重，可根據(jù)需要進(jìn)行調(diào)整；Dm表示節(jié)點(diǎn)m的度數(shù)；Bm表示節(jié)點(diǎn)m的帶寬因子，用節(jié)點(diǎn)間的帶寬表示；Lm表示節(jié)點(diǎn)m的負(fù)載因子，用來(lái)表示節(jié)點(diǎn)的綜合負(fù)載情況，為節(jié)點(diǎn)機(jī)器CPU占用率(pc)、內(nèi)存利用率(pm)與磁盤利用率(ph)等因素加權(quán)表示，且：

Lm=pcm+pmn+phk,m+n+k=1

其中，m、n、k為參數(shù)對(duì)應(yīng)的動(dòng)態(tài)權(quán)重，可根據(jù)需要進(jìn)行調(diào)整。

由于前述2種方案對(duì)算法求解速度有了較大提高，算法求解時(shí)可提供多套方案進(jìn)行備選。本文定義了方案評(píng)價(jià)算法，能夠?qū)Ψ桨高x擇提供參考依據(jù)。

4 實(shí)驗(yàn)驗(yàn)證

4.1 具體實(shí)現(xiàn)

按照本文的設(shè)計(jì)，在實(shí)驗(yàn)平臺(tái)運(yùn)行改進(jìn)的貪婪算法及評(píng)價(jià)方案，并在最后展示最終算法與原始算法的性能對(duì)比。

4.2 實(shí)驗(yàn)環(huán)境

硬件環(huán)境：臺(tái)式計(jì)算機(jī)(Intel i7-8700K, 32 GB RAM, 1 TB SSD)及其相應(yīng)配件。軟件環(huán)境：Windows 10 64位平臺(tái)，Python 3.7.6。本文所屬實(shí)驗(yàn)均在相同硬件及軟件環(huán)境下完成，下面分別進(jìn)行說(shuō)明。

4.2.1 迭代周期優(yōu)化

使用生成節(jié)點(diǎn)數(shù)為5000的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型，橫向?qū)Ρ鹊螖?shù)p為1、5、10時(shí)，算法的求解速度不斷加快。通過(guò)不同的迭代次數(shù)p，說(shuō)明迭代次數(shù)的改進(jìn)對(duì)于效率的影響程度。實(shí)驗(yàn)結(jié)果見表1。

表1 迭代周期與求解速度

從實(shí)驗(yàn)數(shù)據(jù)來(lái)看，調(diào)大貪婪算法中迭代周期會(huì)減小迭代次數(shù)，從而加速貪婪算法的求解速度。平均優(yōu)化程度達(dá)到95%以上，但是可能會(huì)犧牲一定的求解精度。后續(xù)研究方向是尋找能夠補(bǔ)償求解精度的方法。

4.2.2 面向BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的排序算法優(yōu)化

使用BA無(wú)標(biāo)度網(wǎng)絡(luò)模型，分別創(chuàng)建3000、3500、4000、4500和5000個(gè)節(jié)點(diǎn)規(guī)模的網(wǎng)絡(luò)模型，測(cè)試普通排序方法和優(yōu)化后排序方法在本實(shí)驗(yàn)場(chǎng)景中不同規(guī)模下的性能差異。A代表普通排序算法，B代表優(yōu)化后排序算法。實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 排序算法優(yōu)化對(duì)比

從實(shí)驗(yàn)數(shù)據(jù)來(lái)看，在10組對(duì)比項(xiàng)中，改進(jìn)后的排序算法相對(duì)于普通排序算法在求解速度方面有較為明顯的進(jìn)步，取得了預(yù)期效果。但盡管如此，特定場(chǎng)景中可能存在更適合的排序算法。后續(xù)研究方向是進(jìn)一步嘗試優(yōu)化其他排序算法在本場(chǎng)景下的效率。

4.2.3 方案選擇優(yōu)化

節(jié)點(diǎn)的硬件配置也會(huì)對(duì)測(cè)量節(jié)點(diǎn)的部署產(chǎn)生影響。實(shí)驗(yàn)假定節(jié)點(diǎn)負(fù)載分布服從[0.5，1]的均勻分布。α、β、γ、m、n、k均暫定為1/3。求解不同迭代周期下的節(jié)點(diǎn)平均度數(shù)、平均加權(quán)度數(shù)等參數(shù)，如表3所示，可供決策人員參考?？梢婋S著迭代周期的增加，盡管計(jì)算時(shí)間在增加，但是節(jié)點(diǎn)平均度數(shù)和節(jié)點(diǎn)加權(quán)平均度數(shù)均在持續(xù)減少，這說(shuō)明產(chǎn)生了一定比例的冗余節(jié)點(diǎn)。因此，實(shí)際應(yīng)用中需要根據(jù)場(chǎng)景規(guī)模合理決定迭代周期的取值，適當(dāng)?shù)牡芷诳梢栽谌萑滩糠秩哂嗟那闆r下，加速問(wèn)題的求解。節(jié)點(diǎn)負(fù)載使用均勻分布建模，可能與實(shí)際情況有偏差，有待后續(xù)研究。

表3 方案選擇優(yōu)化

5 結(jié)束語(yǔ)

本文設(shè)計(jì)并實(shí)現(xiàn)了一種面向名字解析系統(tǒng)測(cè)量節(jié)點(diǎn)選擇求解最小點(diǎn)覆蓋的優(yōu)化方法，從算法迭代周期改進(jìn)和結(jié)合實(shí)際場(chǎng)景優(yōu)化排序算法以及方案評(píng)價(jià)方面對(duì)ICN中NRS前期測(cè)量節(jié)點(diǎn)的部署進(jìn)行了研究。實(shí)驗(yàn)結(jié)果表明，相對(duì)于傳統(tǒng)貪婪算法，改進(jìn)后的貪婪算法在求解速度上得到了較大提升，能夠達(dá)到預(yù)期效果。