李紹帥，文　鴻，趙子龍，沈小建，歐陽旻

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

基于孤立點的全局最小MPR集選擇算法

李紹帥，文鴻，趙子龍，沈小建，歐陽旻

（湖南工業(yè)大學(xué) 計算機與通信學(xué)院，湖南 株洲 412007）

針對OLSR協(xié)議中采用貪婪算法選擇最小MPR集存在的冗余問題，提出了基于孤立點的全局最小MPR集選擇算法。通過逐步剔除可達數(shù)最小的一跳節(jié)點，產(chǎn)生新孤立點，獲取最小MPR集；當(dāng)可達數(shù)最小的一跳節(jié)點不唯一時，考慮全局MPR節(jié)點的影響，優(yōu)化整個網(wǎng)絡(luò)的MPR節(jié)點數(shù)量。仿真結(jié)果表明：本文所提的MPR選擇算法相對于基于貪心策略的MPR選擇算法，整個網(wǎng)絡(luò)MPR節(jié)點數(shù)量減少7%，控制消息開銷明顯降低，網(wǎng)絡(luò)性能得到提高。

孤立點；最小MPR集；優(yōu)化鏈路狀態(tài)路由協(xié)議；冗余；全局最優(yōu)

0　引言

優(yōu)化鏈路狀態(tài)路由（optimized link state routing，OLSR）協(xié)議是在經(jīng)典鏈路狀態(tài)路由協(xié)議的基礎(chǔ)上，專門為移動Ad-Hoc網(wǎng)絡(luò)開發(fā)的表驅(qū)動路由協(xié)議［1］。OLSR協(xié)議相對于經(jīng)典鏈路狀態(tài)路由協(xié)議所做的優(yōu)化主要體現(xiàn)為：一是采用多點中繼（multipoint relay， MPR）機制，節(jié)點選擇其鄰節(jié)點中的部分節(jié)點作為MPR節(jié)點，再通過MPR節(jié)點轉(zhuǎn)發(fā)拓撲控制消息（topology control，TC），從而減少相同控制消息的重復(fù)轉(zhuǎn)發(fā)，避免廣播風(fēng)暴；二是縮減控制消息的大小，從而降低網(wǎng)絡(luò)開銷。由此可知，在OLSR協(xié)議中，MPR集越小，控制消息開銷越低，網(wǎng)絡(luò)性能越好。

目前關(guān)于MPR節(jié)點選擇的研究分為2類：一種是在貪心算法［2-5］的基礎(chǔ)上進行優(yōu)化；另一種是采用新策略［6-13］尋找MPR集。文獻［5］利用貪心策略獲得滿足條件的MPR集，再對MPR節(jié)點進行排序，消除冗余節(jié)點，該算法簡單高效，能在當(dāng)前解中消除冗余，但不一定能獲得最優(yōu)解。文獻［10］提出了基于遺傳算法的MPR選擇算法，先通過實驗獲得變異參數(shù)，再使用啟發(fā)式策略和有針對性的遺傳策略找到最優(yōu)解，該算法的缺陷是變異操作需要由實驗條件確定。文獻［11］提出了基于候選解的改進蟻群算法，通過候選解更新信息素，在較短時間內(nèi)收斂到最優(yōu)解，但是算法初期，由于缺少足夠的全局信息，盲目搜索所占的時間較長。文獻［12］提出了將組合數(shù)和按位與運算相結(jié)合的方法來尋找最小冗余MPR集，但該算法的解空間搜尋時間復(fù)雜度很高。文獻［13］提出了將全局因素加入MPR選擇判據(jù)中，逐步消除剩余節(jié)點的MPR集冗余，但是該全局策略會造成部分MPR節(jié)點被長時間選用，從而得不到最小MPR集。

本廠風(fēng)電試驗站，被試驗雙饋風(fēng)力發(fā)電機需要配套轉(zhuǎn)子變頻器才能運行，而轉(zhuǎn)子變頻器就屬于典型的電力電子類非線性負載。為此設(shè)計上選擇了使用機組電源。

綜上所述，本文提出了基于孤立點的全局最小MPR集選擇算法（global minimum MPR set selection algorithm based on isolatedpoints，IGMPR），剔除冗余一跳節(jié)點，得到最小MPR集。該算法是在保證單個節(jié)點的最小MPR集前提下，再對MPR集作進一步優(yōu)化，即當(dāng)多個節(jié)點的可達數(shù)一樣時，引入全局MPR節(jié)點。

1　OLSR協(xié)議的MPR集

1.1MPR集的定義

摘 要：為了適應(yīng)社會經(jīng)濟發(fā)展的需要，我國教育部曾提出要將一些本科院校轉(zhuǎn)型為應(yīng)用型本科院校，目前將近80%的本科院校已經(jīng)將應(yīng)用型人才的培養(yǎng)作為人才培養(yǎng)的目標(biāo)。新形勢下應(yīng)用型本科財務(wù)管理專業(yè)課程的設(shè)置成為我們需要思考的新內(nèi)容，不但要滿足學(xué)生學(xué)習(xí)財務(wù)、金融管理方面的內(nèi)容，還要使學(xué)生能夠具備財務(wù)分析、解決金融問題的能力。

4）利用信息化手段，全員全過程全方位參與生涯規(guī)劃。信息化社會，全球一體化進程加快，“兩耳不聞窗外事，一心只讀圣賢書”的做法早已經(jīng)不適合當(dāng)今社會的發(fā)展。如果不緊追時代發(fā)展，關(guān)注社會的需求，恐怕大學(xué)四年還沒有讀完，所學(xué)知識已經(jīng)無用武之地了。如之前BB機曾經(jīng)盛行過一段時間，但是很快手機出現(xiàn)了，那些學(xué)習(xí)BB機專業(yè)的學(xué)生還沒畢業(yè)，BB機就被淘汰了。

1）計算N1（i）中節(jié)點的可達數(shù)。

預(yù)制性詞塊教學(xué)法的重點是培養(yǎng)學(xué)生構(gòu)建和應(yīng)用預(yù)制性詞塊的能力，由于這兩種能力與學(xué)生的外語交際能力直接相關(guān)，所以該教學(xué)法的主要作用也體現(xiàn)在這方面，能有效提升實際的語言交際能力。另外，學(xué)生想要構(gòu)建預(yù)制性詞塊，必須有較強的語感和足夠的詞匯量，所以該教學(xué)法也能反向加強學(xué)生的語感，同時增強學(xué)生學(xué)習(xí)單詞的積極性。[2]又因為預(yù)制性詞塊的應(yīng)用與語境有很大的關(guān)系，語境是選擇預(yù)制性詞塊的決定性因素之一，所以學(xué)生對語境的了解和感受能力也可以通過該教學(xué)法加以提高。綜上可知，預(yù)制性詞塊教學(xué)法對外語教學(xué)的優(yōu)化作用是多方面的。

1.2最小MPR集的選擇

步驟4若N2（i）都已被S所覆蓋，算法結(jié)束。

圖1為中心節(jié)點i計算MPR集的拓撲示意圖。其中｛a， b， c， d， e， f｝為一跳節(jié)點集N1（i），｛1， 2， 3， 4， 5， 6， 7， 8，9， 10， 11， 12， 13｝為二跳節(jié)點集N2（i）。根據(jù)GMPR算法，節(jié)點a提供到1的唯一可達性，此時將節(jié)點a加入MPR集；剩下的節(jié)點依據(jù)貪心策略，選擇覆蓋二跳節(jié)點最多的節(jié)點d為MPR；此時，二跳節(jié)點集還沒有被完全覆蓋，而剩下的節(jié)點可達數(shù)都為2，選密度大的節(jié)點c和e加入MPR集；二跳節(jié)點集被完全覆蓋，節(jié)點i的MPR集為｛a， c， d， e｝。顯然，該拓撲中節(jié)點i的最優(yōu)MPR集為｛a， c， e｝。因此，由GMPR算法得到的MPR集存在冗余節(jié)點，不是最優(yōu)解。

網(wǎng)絡(luò)中某節(jié)點i的MPR集必須滿足以下條件：該節(jié)點MPR集的每個節(jié)點均為一跳節(jié)點；該節(jié)點通過MPR集能覆蓋所有的二跳節(jié)點。由此可抽象出，最小MPR集合問題為最小集合覆蓋問題。定義N1（i）為節(jié)點i的一跳節(jié)點集，N2（i）為節(jié)點i的二跳節(jié)點集，節(jié)點i的MPR集為S，則所求的MPR集應(yīng)滿足以下條件：

圖1　計算MPR集的拓撲示意圖Fig.1　The schematic topology of calculating MPR set

2　基于孤立點的全局最小MPR集選擇算法介紹

GMPR算法選擇可達數(shù)最大的節(jié)點，易導(dǎo)致MPR集冗余，致使網(wǎng)絡(luò)開銷增多。針對上述問題，本文從孤立點的特性出發(fā)，并加入全局MPR因素，來選擇MPR集。

步驟2若N2（i）中存在孤立點，則將孤立點對應(yīng)的一跳節(jié)點加入S。

只能通過唯一的一跳節(jié)點到達中心節(jié)點的二跳節(jié)點為孤立點［15］。孤立點所對應(yīng)的一跳節(jié)點必須添加進MPR集，因為除孤立點所對應(yīng)的一跳節(jié)點，其它任一一跳節(jié)點被剔除時，在剩余的一跳節(jié)點集合中均能找到MPR集。在一跳節(jié)點中，可達數(shù)最小的節(jié)點往往是冗余節(jié)點，因此，本文將其剔除。當(dāng)剔除一個或多個一跳節(jié)點時，其對應(yīng)的二跳節(jié)點將會成為新孤立點。因此，基于孤立點的最小MPR集選擇策略為：首先將所有孤立點對應(yīng)的一跳節(jié)點加入MPR集；再通過不斷剔除可達數(shù)最小的一跳節(jié)點來形成新孤立點，并將所產(chǎn)生的新孤立點所對應(yīng)的一跳節(jié)點加入MPR集，直到所有二跳節(jié)點被MPR集完全覆蓋。

下面用圖1來說明基于孤立點的最小MPR集選擇策略的處理過程。二跳節(jié)點中的節(jié)點1是孤立點，因此將節(jié)點1所對應(yīng)的一跳節(jié)點a加入MPR集。剩下的二跳節(jié)點中沒有孤立點，則選擇可達數(shù)最小的一跳節(jié)點進行處理。一跳節(jié)點b和f的可達數(shù)都為2，此時剔除節(jié)點b，則出現(xiàn)孤立點3和4。將孤立點3對應(yīng)的一跳節(jié)點c加入MPR集。在剩下的一跳節(jié)點中，d的可達數(shù)為3，e的可達數(shù)為5，f的可達數(shù)為2，剔除可達數(shù)最小的節(jié)點f，此時出現(xiàn)孤立點11和12，將11對應(yīng)的一跳節(jié)點e加入MPR。此時，所有二跳節(jié)點都已被覆蓋。節(jié)點i的MPR集為｛a， c， e｝，沒有冗余節(jié)點，為該拓撲的最優(yōu)解。

中頻電爐的溫度檢測范圍較高，因此采用K型熱電偶，為使測量準(zhǔn)確，采用電橋補償法自動補償熱電偶參考端溫度變化引起的測量誤差。采用典型的儀用放大電路放大熱電偶的差動輸入信號，將熱電偶的輸入信號調(diào)整為0-5V的模擬電壓信號。

2.2考慮全局因素的最小MPR集選擇算法

中心節(jié)點i在選擇MPR集時，N1（i）中已被其它節(jié)點選入其MPR集的節(jié)點為全局MPR節(jié)點。文獻［13］提出的基于全局優(yōu)化的MPR選擇算法，首先將全局MPR節(jié)點加入自己的MPR集，然后在除去全局MPR節(jié)點的剩余一跳節(jié)點集合中尋找最小MPR集，但是該算法容易使單個節(jié)點無法獲得最小MPR集。本文對此進行改進，首先利用基于孤立點的最小MPR集選擇策略以保證單節(jié)點的MPR集最小。在此基礎(chǔ)上，當(dāng)剔除可達數(shù)最小的節(jié)點不唯一時，將全局因素加入MPR的選擇中。若被處理節(jié)點為非全局MPR節(jié)點，則直接剔除；否則保留。若非全局MPR節(jié)點都被剔除時，剩余一跳節(jié)點均為全局MPR節(jié)點，此時逐次剔除該集合中節(jié)點。本算法通過剔除最小可達數(shù)的一跳節(jié)點，可以找到最小MPR集，當(dāng)最小可達數(shù)的一跳節(jié)點不唯一時，考慮全局MPR節(jié)點，以減少全局MPR節(jié)點的數(shù)量。

算法描述如下。

步驟1定義中心節(jié)點i的MPR集為S，且初始化S為空。

2.1基于孤立點的MPR集選擇策略

3）若可達數(shù)最小的節(jié)點有多個。當(dāng)被處理節(jié)點為非全局MPR節(jié)點時，則剔除該節(jié)點，返回步驟2。

可知，MPR集問題轉(zhuǎn)換為求滿足上述條件的S集合最小值問題。求解最小MPR集是一個完全多項式復(fù)雜程度的非確定性問題［14］，要找到最優(yōu)解，需要一個指數(shù)時間算法來實現(xiàn)。OLSR協(xié)議采用基于貪心策略的MPR選擇算法（MPR selection algorithm based on greedy strategy，GMPR），在較短的時間內(nèi)能找到一個較好的解。

2）若可達數(shù)最小的節(jié)點唯一，則不論該節(jié)點是否為全局MPR節(jié)點，都直接剔除該節(jié)點，返回步驟2。

步驟3若N2（i）中仍有未被S所覆蓋的節(jié)點，作如下處理。

當(dāng)被處理節(jié)點為全局MPR節(jié)點時，則繼續(xù)處理下一個節(jié)點，若處理到最后一個節(jié)點發(fā)現(xiàn)都是全局MPR節(jié)點時，則剔除第一個節(jié)點，返回步驟2。

GMPR算法思想如下：首先將N1（i）中到N2（i）的唯一可達節(jié)點加入MPR集，然后在N1（i）的剩余節(jié)點中依次選擇可達數(shù)最大的節(jié)點加入到MPR集，直到N2（i）被完全覆蓋。該策略的優(yōu)點是計算簡單、快速，易于實現(xiàn)，但選擇可達數(shù)最大的節(jié)點會造成MPR集可能存在大量冗余。

腦膠質(zhì)瘤是惡性腫瘤疾病,因為現(xiàn)代人的生活習(xí)慣和飲食習(xí)慣不健康,導(dǎo)致了臨床中越來越多的人患有該疾病。腦膠質(zhì)瘤的生長部位是腦內(nèi)中樞神經(jīng)系統(tǒng),沒有特意的地點,不及時的進行治療或者治療不當(dāng),患者的術(shù)后生活受到嚴(yán)重的影響,甚至?xí)尰颊咚劳觥?/p>

此輪印度招標(biāo)，中國貨源占到了一半，雖然標(biāo)價基本與國內(nèi)出廠價格相當(dāng)，但如此大批量的出口，依舊為國內(nèi)市場提供了支撐。加之前期行情的持續(xù)走低，使尿素價格已逐漸達到下游的心理預(yù)期，在印標(biāo)確定后，新單立即跟進，止住了行情的頹勢。

該算法以全局優(yōu)化來避免局部最優(yōu)，在選擇本節(jié)點的MPR集時，考慮了一跳節(jié)點是否已被其他節(jié)點選為MPR節(jié)點。因此，獲取一跳節(jié)點的全局MPR參數(shù)信息是算法實現(xiàn)的前提。相鄰節(jié)點可通過廣播的Hello消息得到相互的信息。因此，本文在Hello消息中定義MSC字段即攜帶該節(jié)點的MPR選擇器個數(shù)，實現(xiàn)全局MPR信息的傳播。初始階段，不存在全局MPR信息，MPR計算按照基于孤立點的MPR選擇策略執(zhí)行。網(wǎng)絡(luò)出現(xiàn)全局MPR節(jié)點后，算法逐步進行全局優(yōu)化，每當(dāng)網(wǎng)絡(luò)中某個節(jié)點的相鄰區(qū)域和二跳相鄰區(qū)域發(fā)生變化時，就會重新計算該節(jié)點的MPR集，并為其單獨發(fā)送一條Hello消息，更新整個網(wǎng)絡(luò)拓撲。

3　仿真分析

本文通過修改基于IGMPR選擇算法的OLSR協(xié)議（IGMPR_OLSR）的相關(guān)數(shù)據(jù)結(jié)構(gòu)和功能，實現(xiàn)一跳節(jié)點是否為全局MPR節(jié)點的信息傳遞，為MPR集的選擇提供依據(jù)?；贜 S 2平臺，對2種協(xié)議IGMPR_OLSR協(xié)議和基于GMPR選擇算法的OLSR協(xié)議（GMPR_OLSR）進行仿真分析，測試了網(wǎng)絡(luò)的整體MPR數(shù)、收發(fā)TC消息分組數(shù)、網(wǎng)絡(luò)延時等性能。仿真場景設(shè)置為：在600 m×800 m的范圍內(nèi)有50個節(jié)點，使用cbrgen產(chǎn)生隨機cbr數(shù)據(jù)流，cbr封包的大小為512 B，最大聯(lián)機數(shù)為10，發(fā)包率為10個/s，仿真時間為30 s。在仿真過程的記錄文件中，使用awk工具統(tǒng)計并分析出各項數(shù)據(jù)隨時間的變化曲線，如圖2～ 4所示。

在教學(xué)活動中突出學(xué)生自主學(xué)習(xí)能力培養(yǎng)，通過教師的主導(dǎo)來發(fā)揮學(xué)生的主體作用。開學(xué)初，學(xué)生領(lǐng)完教材，就開始引導(dǎo)同學(xué)們將教材內(nèi)容粗略的進行瀏覽，使他們對教材內(nèi)容有了初步的了解，同時也引導(dǎo)他們與自己的知識結(jié)構(gòu)進行比較，對學(xué)習(xí)這門課有一個明確的目標(biāo)，做好學(xué)習(xí)的計劃，提前發(fā)現(xiàn)自己學(xué)習(xí)這門課可能遇到的問題，為學(xué)好本這門課提前做好心理準(zhǔn)備。

圖2　MPR節(jié)點數(shù)量對比圖Fig.2　The contrast diagram of MPR node numbers

由整個網(wǎng)絡(luò)中的MPR節(jié)點數(shù)量對比圖（見圖2）可知：仿真進行到11 s時，路由協(xié)議收斂，網(wǎng)絡(luò)達到穩(wěn)定狀態(tài)；GMPR_OLSR協(xié)議的全局MPR節(jié)點數(shù)為29，本文所提的IGMPR_OLSR協(xié)議的MPR節(jié)點個數(shù)為27，此時IGMPR_OLSR協(xié)議的全局MPR節(jié)點數(shù)降低了7%。

TC消息的發(fā)送數(shù)體現(xiàn)了網(wǎng)絡(luò)中TC消息的洪泛初始規(guī)模，數(shù)值越小說明MPR集節(jié)點越少，冗余性越??；TC消息的接收數(shù)反應(yīng)了MPR集對TC消息洪泛的影響，網(wǎng)絡(luò)中接收的TC消息越少，則中間MPR節(jié)點轉(zhuǎn)發(fā)TC消息數(shù)就越少。圖3為收發(fā)TC消息分組數(shù)對比圖。

圖3　收發(fā)TC消息分組數(shù)對比圖Fig.3　The comparison diagram for number of packets to send and receive TC messages

由圖3a可知，IGMPR_OLSR協(xié)議發(fā)送TC消息數(shù)少于GMPR_OLSR協(xié)議，而且差值越來越大，仿真到30 s時，GMPR_OLSR協(xié)議發(fā)送TC消息數(shù)為903，IGMPR_OLSR協(xié)議發(fā)送TC消息數(shù)為846，減少了57，減少量達6.3%。這說明IGMPR_OLSR協(xié)議優(yōu)化了MPR集的選擇，通過減少全局MPR節(jié)點數(shù)，降低了TC消息的洪泛規(guī)模。由圖3b可知，IGMPR_OLSR協(xié)議接收的TC消息數(shù)始終少于GMPR_OLSR協(xié)議；仿真進行到30 s時，GMPR_OLSR協(xié)議接收TC消息數(shù)為17 106個分組，IGMPR_OLSR協(xié)議接收TC消息數(shù)為14 754個分組，減少了2 352個分組，減少量達13.8%，這說明IGMPR_OLSR協(xié)議減少了中間MPR節(jié)點轉(zhuǎn)發(fā)TC消息數(shù)，也意味著減少了TC消息的洪泛次數(shù)。2種TC消息數(shù)明顯減少，也進一步說明了IGMPR_OLSR協(xié)議對MPR集的優(yōu)化效果。

平均端到端延遲是報文從源節(jié)點到目的節(jié)點的平均傳輸時間。圖4為網(wǎng)絡(luò)平均延時對比圖。由圖可知，IGMPR_OLSR協(xié)議的網(wǎng)絡(luò)平均時延要小于GMPR_OLSR協(xié)議；仿真進行到11 s路由協(xié)議收斂后，IGMPR_OLSR協(xié)議的網(wǎng)絡(luò)平均延時減少量維持在0.5 ms左右，這說明IGMPR_OLSR協(xié)議通過減少全局MPR節(jié)點的數(shù)量，減少了網(wǎng)絡(luò)控制消息開銷，從而降低了網(wǎng)絡(luò)延時，提高了網(wǎng)絡(luò)性能。

圖4　網(wǎng)絡(luò)延時對比圖Fig.4　The comparison diagram of network delay

4　結(jié)語

本文針對OLSR協(xié)議中采用貪婪算法選擇最小MPR集存在的冗余問題，提出了基于孤立點的全局最小MPR選擇算法，通過不斷形成孤立點，找到最小MPR集，并從節(jié)點的全局MPR特性來優(yōu)化MPR集的選擇。利用NS2將本文所提IGMPR_OLSR協(xié)議與基于貪婪策略選擇MPR集的OLSR協(xié)議進行仿真分析，仿真結(jié)果表明：在全局M P R節(jié)點數(shù)量上，IGMPR_OLSR協(xié)議能有效減少，降低了7%；網(wǎng)絡(luò)中TC消息的發(fā)送量減少6.3%，接收量減少13.8%，降低了控制消息的開銷和網(wǎng)絡(luò)平均延時，提高了網(wǎng)絡(luò)的傳輸性能。在下一步的工作中，本課題組將研究在實際的網(wǎng)絡(luò)環(huán)境中本算法的性能，并結(jié)合負載均衡的觀點來嘗試新的優(yōu)化策略。

［1］陳林星，曾曦，曹毅.移動Ad Hoc網(wǎng)絡(luò)自組織分組無線網(wǎng)絡(luò)技術(shù)［M］.2版. 北京：電子工業(yè)出版社，2012：130-133. CHEN Linxing，ZENG Xi，CAO Yi. Mobile Ad Hoc Network：Self Organizing Packet Radio Network Technology［M］. 2nd ed. Beijing：Electronic Industry Press，2012：130-133.

［2］沈呈，陸一飛，夏勤，等.無線Mesh網(wǎng)中一種基于MPR當(dāng)選頻度的OLSR擴展路由協(xié)議［J］.計算機科學(xué)，2009，36（12）：93-96. SHEN Cheng，LU Yifei，XIA Qin，et al. MPR Election Frequency Based Extended OLSR Protocol in Wireless Mesh Networks［J］. Computer Science，2009，36（12）：93-96.

［3］BENABBOU A，BOUSHABA A，ZAHI A，et al. NCA：New Cooperative Algorithm for Reducing Topology Control Packets in OLSR［J］. Journal of Networks，2015，10（3）：125-133.

［4］蘭鵬，李二濤，何桂仙.基于改進OLSR路由協(xié)議的Mesh網(wǎng)絡(luò)的研究［J］.杭州電子科技大學(xué)學(xué)報，2013，33（4）：54-57. LAN Peng，LI Ertao，HE Guixian. Research of Mesh Network Based on the Improved OLSR Routing Protocol［J］. Journal of Hangzhou Dianzi University，2013，33（4）：54-57.

［5］趙健，孫俊鎖.OLSR路由協(xié)議的改進及其NS2仿真分析［J］.計算機仿真，2008，25（1）：161-163. ZHAO Jian，SUN Junsuo. Simulation and Analysis of an Improved OLSR Routing Protocol Based on NS2［J］. Computer Simulation，2008，25（1）：161-163.

［6］ECHCHAACHOUI A，OUACHA A，HABBANI A，et al. Enhanced MPR Selection Process in OLSR Based on Agitation of Nodes［J］. International Journal of Advancements in Computing Technology，2013，5（10）：166-174.

［7］鐘珞，趙先明，夏紅霞.求解最小MPR集的蟻群算法與仿真［J］.智能系統(tǒng)學(xué)報，2011，6（2）：166-171. ZHONG Luo，ZHAO Xianming，XIA Hongxia. An Ant Colony Algorithm and Simulation for Solving Minimum MPR Sets［J］. CAAI Transactions on Intelligent Systems，2011，6（2）：166-171.

［8］WANG Anbao，ZHU Bin. Improving MPR Selection Algorithm in OLSR Protocol Based on Node Localization Technology［J］. Journal of Networks，2014，9（7）：1674-1681.

［9］KOTS A，KUMAR M. The Fuzzy Based QMPR Selection for OLSR Routing Protocol［J］. Wireless Networks，2014，20（1）：1-10.

［10］張信明，曾依靈，干國政，等.用遺傳算法尋找OLSR協(xié)議的最小MPR集［J］.軟件學(xué)報，2006，17（4）：932-938. ZHANG Xinming，ZENG Yiling，GAN Guozheng，et al. Finding the Minimum MPR Set in OLSR Protocol with Genetic Algorithms［J］. Journal of Software，2006，17（4）：932-938.

［11］張禾良，熊焰，苗付友.最小MPR集選取問題的改進蟻群優(yōu)化算法［J］. 小型微型計算機系統(tǒng)，2012，33（1）：126-129. ZHANG Heliang，XIONG Yan，MIAO Fuyou. Minimum MPR Set Selection：An Improved Ant Colony Optimization Approach［J］. Journal of Chinese Computer Systems，2012，33（1）：126-129.

［12］張洪，高楊.一種新型MPR集選擇算法［J］.成都大學(xué)學(xué)報（自然科學(xué)版），2015，34（1）：38-40. ZHANG Hong，GAO Yang. New Chosen Algorithm of MPRs［J］. Journal of Chengdu University（Natural Science Edition），2015，34（1）：38-40.

［13］劉杰，王玲，王杉，等.基于OLSR協(xié)議的最小MPR集選擇算法［J］. 計算機應(yīng)用，2015，35（2）：305-308，339. LIU Jie，WANG Ling，WANG Shan，et al. Minimum MPR Set Selection Algorithm Based on OLSR Protocol［J］. Journal of Computer Applications，2015，35（2）：305-308，339.

［14］QAYYUM A，VIENNOT L，LAOUITI A. Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks［C］//Proceedings of the 35th Annual Hawaii International Conference on System Sciences. Washington：IEEE，2002：3866-3875.

［15］BUSSON A，MITTON N，F(xiàn)LEURY E. Analysis of the Multi-Point Relay Selection in OLSR and Implications［M］. New York：Springer，2006：387-396.

（責(zé)任編輯：鄧彬）

Global Minimum MPR Set Selection Algorithm Based on Isolated Points

LI Shaoshuai，WEN Hong，ZHAO Zilong，SHEN Xiaojian，OUYANG Min
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

Aiming at the redundancy problem in the OLSR protocol， a global minimum MPR set selection algorithm based on the isolated points is proposed. The algorithm generates a new isolated point by eliminating step by step the minimum reachable number of nodes and obtains the minimum MPR set. At the same time， the effect of the global MPR node is considered when the minimum reachable number of nodes are not unique， so as to optimize the number of MPR nodes in the whole network. Experimental results show that compared with the MPR selection algorithm based on greedy strategy，the proposed MPR selection algorithm decreases the number of MPR nodes in the whole network by 7%， reduces the network control message overhead significantly and improves the network performance.

isolated points ；minimal MPR set ；optimized link state routing protocol ；redundancy ；global optimization

TP393

A

1673-9833（2016）02-0048-05

10.3969/j.issn.1673-9833.2016.02.009

2015-12-01

湖南省自然科學(xué)基金資助項目（14JJ3123），湖南省教育廳科研基金資助項目（15K035，15C0408，14A037）

李紹帥（1991-），男，河南新鄉(xiāng)人，湖南工業(yè)大學(xué)碩士生，主要研究方向為無線Mesh網(wǎng)絡(luò)，E-mail ：lss239@sina.cn

文鴻（1981-），男，湖南邵陽人，湖南工業(yè)大學(xué)副教授，博士，主要研究方向為下一代寬帶無線通信網(wǎng)，E-mail ：wenhhut@163.com