一種求解最小連通支配集的分布式算法

一種求解最小連通支配集的分布式算法

1基于misb的最小連通支配集算法廣播是無線傳感器網絡和移動自組織網絡的一種常見通信模式，可以用于連接所有路徑、業(yè)務信息和參數配置。廣播通常執(zhí)行泛流（flooding）。這是簡單的，但它會導致大量的網絡捐款，導致通信風暴等問題。由于資源高度有限，發(fā)送數據非常高，網絡上的傳輸流量非常高，因此不可避免地消耗了資源不足。為了避免flooding方法的缺點，網絡中的冗余節(jié)點應該減少。也就是說，當所有網絡節(jié)點都接收到并且接收到數據包時，網絡中的節(jié)點數應該減少。在無線網絡廣播中最小化參與轉發(fā)節(jié)點數問題與圖論中求解最小連通支配集問題等價.而在任意圖中求解最小連通支配集是NP完全問題,所以在實際應用中常用啟發(fā)式算法來求其近似解.求解的過程可以采用集中式方法和分布式方法.采用集中式方法雖然能夠得到較小的連通支配集,但在多數無線應用中,使用整個圖的拓撲信息來構造連通支配集并不可取,一般應采用分布式方法,相應的算法有MPR及其擴展算法和其它算法.這些算法大多是利用兩跳內節(jié)點信息,采用分布式方法構造連通支配集,但也有例外,如文獻是利用三跳內節(jié)點信息構造連通支配集,且只有在節(jié)點密度極大的條件下才有較好的性能.為在無線傳感器網絡和移動自組織網絡中進行更為有效的廣播,本文僅利用兩跳內節(jié)點信息提出了基于極大獨立集的最小連通支配集的分布式算法(稱為MISB).MISB算法不是采用直接構造連通支配集的方式,而是首先利用分布式貪心算法,選舉具有極大度(Maximaldegree)的節(jié)點為獨立點,構造出一種特殊的無任何兩個節(jié)點相鄰的極小支配集,即極大獨立集;然后利用獨立點作為錨點,利用分治的思想添加非獨立點來連通極大獨立集.實際上,MISB是通過剔除不破壞網絡連通性的節(jié)點來達到添加非獨立點的目的,而網絡連通性的判斷只依賴兩跳內節(jié)點.此外,在不破壞連通支配集的條件下,獨立點也可放棄自身的支配點地位.與同樣利用兩跳內節(jié)點信息構造連通支配集的算法MPR和EMPR相比,MISB算法能夠得到較小的連通支配集.2misb算法2.1vd的非空子集定義1圖的相關定義一個無向圖是一個有序的二元組(V,E),記作G.其中,V是一個非空集合,稱為點集,其元素稱為點、頂點或節(jié)點;E是由V中的點組成的無序點對構成的多重集合,稱為邊集,其元素稱為邊.在不引起歧義的情況下,無向圖簡稱為圖.圖中的邊e記為uv,即e=uv.稱u、v為e的端點,稱u(或v)與e關聯,并稱節(jié)點u、v相鄰.連接兩個相同點的邊的條數稱為邊的重數,重數大于1的邊稱為重邊.端點重合為一點的邊稱為環(huán).只有一個點的圖稱為平凡圖.設Vd是V的非空子集.以Vd為點集、以兩端點都在Vd的邊的全體為邊集構成的子圖,稱為G的由Vd導出的子圖.G中點u的度是指G中與u關聯的邊的數目,記為d(u).沒有環(huán)也無重邊的圖稱為簡單圖.G中點與邊的交替序列W=v0e1v1e2…ekvk,稱為點v0到點vk的通路,其中vi-1、vi是ei的端點.設G=(V,E).對于所有u,v∈V,若u,v間存在通路,則稱u,v是連通的.若G是平凡圖或G中任何兩點都是連通的,稱G為連通圖.在連通圖G中,若去掉點u及與u關聯的邊,剩余的圖記為G-{u}.若G-{u}不連通,稱u為圖G的割點.定義2極大獨立集設G=(V,E),I?V.若I中任意兩點皆不相鄰,稱I為G的獨立集,I中的節(jié)點稱為獨立點.設I為獨立集,若在I中加入任何其它點,使得I不再是獨立集,稱I為極大獨立集.定義3最小連通支配集設G=(V,E),C?V.若對于任意u∈V-C,都存在v∈C,使得uv∈E成立,稱v為支配點,并稱C為G的一個支配集.如果C為G的支配集,但C的任何真子集都不是支配集,則稱C為極小支配集.點數最小的支配集稱為最小支配集.若由支配集C導出的子圖是連通圖,稱C為連通支配集.點數最小的連通支配集稱為最小連通支配集.2.2節(jié)點選舉算法MISB算法是在極大獨立集的基礎上來構造連通支配集,所以首先應構造極大獨立集.直覺上具有較大度的點支配性好,所以使用貪心算法選擇具有極大度的點來構造極大獨立集.如果相鄰節(jié)點具有相同的極大度,則利用標號來打破僵局.設圖G=(V,E)為簡單連通非平凡圖.G中所有點都唯一標號,節(jié)點vi的標號記為id(vi),并且若vi≠vj,那么id(vi)>id(vj)或id(vi)<id(vj)之一必成立.節(jié)點u、v∈V,當且僅當(d(u)>d(v))∨((d(u)=d(v))∧(id(u)<id(v)))時,定義u?vu?v.由于節(jié)點唯一標號,顯然(V,?)(V,?)是一個全序集.設Z+為非負整數集合,定義函數fi:V→Z+,其值的確定方法及意義見下述構造極大獨立集算法過程.定義函數fe:V→{true,false},fe(v)=true表示節(jié)點v已進行了自我選舉,否則fe(v)=false.算法1構造極大獨立集的算法(1)所有節(jié)點u∈V,初始化u.fi(u)←0,u.fe(u)←false.(2)相鄰節(jié)點進行鄰居發(fā)現,節(jié)點u的鄰節(jié)點集記為N(u).(3)相鄰節(jié)點交換鄰居信息,節(jié)點u獲得了d(x),其中x∈N(u).(4)所有節(jié)點u∈V,初始化u.fe(x)←false,其中x∈N(u).(5)所有節(jié)點u∈V,對{u}∪N(u)按照運算符??進行本地排序,然后按序選舉.選舉規(guī)則如下:若節(jié)點u是集合{v|(v∈{u}∪N(u))}的最小元,則u為獨立點,賦值u.fi(u)←0,u.fe(u)←true,并將選舉結果u.fi(u)通告N(u).x(x∈N(u))接收到通告后,賦值x.fi(x)←fi(x)+1,x.fe(u)←true,x.fi(u)←0;如果x.fe(x)=false,那么x.fe(x)←true,并將x.fi(x)通告N(x).y(y∈N(x))接收到通告后,賦值y.fi(x)←x.fi(x),y.fe(x)←true;如果y.fe(y)=false且y是{v|(v∈{y}∪N(y))∧(fe(v)=false)}的最小元,則y為獨立點,并采取與前述u同樣的處理方式進行賦值、通告.(6)所有節(jié)點u∈{v|(fi(v)>1)∧(v∈V)},將最終選舉結果u.fi(u)通告N(u).x(x∈N(u))接收到通告后,賦值x.fi(u)←u.fi(u).(7)結束.由于在算法1中,V在運算符??下是有限全序集,V的非空子集也是有限全序集,因而必存在最小元,所以算法1能正常開始和結束.且在選舉規(guī)則中,每個節(jié)點的僅需發(fā)送1個消息,計算復雜度可忽略.并且網絡中所有節(jié)點u∈V都獲得了其鄰節(jié)點的fi(x)值,x∈N(u).選舉結束后,記Vi={v|(fi(v)=0)∧(v∈V)};記Vn={v|(fi(v)=1)∧(v∈V)},其元素稱為普通節(jié)點;記Vg={v|(fi(v)>1)∧(v∈V)},其元素稱為網關節(jié)點.在圖1中,設id(vi)>id(vj),當且僅當i>j.圖1表示了算法1的選舉結果.由算法1,可得以下定理:定理1集合Vi={v|(fi(v)=0)∧(v∈V)}是圖G=(V,E)的極大獨立集.證明算法1中,相鄰節(jié)點在本地排序,然后按序選舉.u∈Vi,當且僅當fi(u)=0;u與Vi中n(n>0)個元素相鄰,當且僅當fi(u)=n.當u∈Vi時,fi(u)=0,若v∈N(u),則fi(v)≠0,故Vi是獨立集.若在集合Vi中加入任一節(jié)點w(w?Vi),而fi(w)>0,fi(w)表示與節(jié)點w相鄰的Vi節(jié)點數,故w必與Vi中fi(w)個節(jié)點相鄰,因此Vi∪{w}不是獨立集.所以Vi是G的極大獨立集.證畢.定理2對于任一u∈Vi,所有x∈(N(u)∩Vn),滿足d(u)≥d(x).對于任一v∈Vg,則至少存在一個y∈(N(v)∩Vi),滿足d(y)≥d(v).證明從算法1易見,略.證畢.2.3節(jié)點自身保護在得到極大獨立集Vi后,以此為基礎來構造最小連通支配集.首先確定在圖中不是獨立點、且不是割點的節(jié)點為非支配點,從而構造出連通支配集;然后對獨立點進行檢查,剔除不破壞連通性和支配性的獨立點,使之為非支配點.在確定節(jié)點是否為支配點時,算法利用了與節(jié)點相鄰的兩跳內節(jié)點信息.為便于討論,使用如下符號:Vi(u)表示與節(jié)點u相鄰的獨立點集,Vi(u,2)表示與節(jié)點u相距2跳的獨立點集,令Ni(u,2)=Vi(u)∪Vi(u,2);Vg(u)表示與節(jié)點u相鄰的網關節(jié)點集,Vg(u,2)表示與節(jié)點u相距2跳、且與Vi(u)中任一節(jié)點相鄰的網關節(jié)點集,令Ng(u,2)=Vg(u)∪Vg(u,2);Vn(u)表示與節(jié)點u相鄰的普通節(jié)點集.定義函數fc:V→{true,false}.其值的確定方法及意義見下述構造最小連通支配集算法過程.算法2構造最小連通支配集的算法(1)所有節(jié)點u∈V-Vi,初始化u.fc(u)←true,u.fe(u)←false.(2)所有節(jié)點u∈Vi,初始化u.fc(u)←true,u.fe(u)←true.(3)所有節(jié)點u∈V-Vi,本地通告u的Vi(u)信息.x∈N(u)保存通告信息.(4)所有節(jié)點u∈Vi,本地通告u的Vg(u)信息.x∈N(u)保存通告信息.(5)所有節(jié)點u∈V-Vi,計算Ni(u,2)、Ng(u,2).(6)所有節(jié)點u∈Vi,計算Vi(u,2).(7)所有節(jié)點u∈Vn,進行支配點選舉.選舉規(guī)則如下:Rule(1):若由{v|v∈(Ni(u,2)∪Ng(u,2))}導出的子圖是連通的,那么u.fc(u)←false,否則u.fc(u)←true;并將選舉結果u.fc(u)通告N(u).x(x∈N(u))接收到通告后,賦值x.fe(u)←true,x.fc(u)←u.fc(u).(8)所有節(jié)點u∈Vg,對{u}∪Ng(u,2)按照運算符進行本地排序,然后按序選舉.選舉規(guī)則如下:Rule(2):若節(jié)點u是集合{v|(v∈{u}∪Ng(u,2))}的最大元,u.fe(u)←true;如果由{v|(v∈(Ni(u,2)∪Ng(u,2)))∧((fe(v)=false)∨((fe(v)=true)∧(fc(v)=true)))}導出的子圖是連通的,那么u.fc(u)←false,否則u.fc(u)←true;并將選舉結果u.fc(u)通告N(u).x(x∈Vi(u))接收到通告后,賦值x.fe(u)←true,x.fc(u)←u.fc(u);并轉發(fā)通告.接收到直接通告或轉發(fā)通告的節(jié)點y(y∈Ng(u,2))賦值y.fe(u)←true,y.fc(u)←u.fc(u);如果y.fe(y)=false且y是{v|(v∈{y}∪Ng(y,2))∧(fe(v)=false)}的最大元,則y采取與前述u同樣的處理方式進行賦值、通告.(9)所有節(jié)點u∈Vi,在其鄰節(jié)點選舉結束后,對{u}∪Vi(u,2)按進行本地排序,初始化u.fe(u)←false,u.fe(x)←false,其中x∈Vi(u,2),然后按序選舉.選舉規(guī)則如下:Rule(3):若節(jié)點u是集合{v|(v∈{u}∪Vi(u,2))}的最大元,u.fe(u)←true;如果由{v|(v∈(Vi(u,2)∪Vg(u)))∧(fc(v)=true)}導出的子圖是連通的,且對任何x∈{v|(v∈N(u))∧(fc(v)=false)},存在y∈{v|(v∈(Vi(u,2)∪Vg(u)))∧(fc(v)=true)},使得x、y相鄰,那么u.fc(u)←false;通告u.fc(u).x∈{v|(v∈Vg(u))∧(fc(v)=true)}接收到通告后,進行轉發(fā).接收到轉發(fā)通告的節(jié)點y(y∈Vi(u,2))賦值y.fe(u)←true,y.fc(u)←u.fc(u);如果y.fe(y)=false且y是{v|(v∈{y}∪Vi(y,2))∧(fe(v)=false)}的最大元,則y采取前述u同樣的處理方式進行賦值、通告.(10)結束.在Rule(1)下,節(jié)點u僅需發(fā)送1個消息,計算復雜度最壞的情況是判斷圖的連通性.u在判斷Vd={v|v∈(Ni(u,2)∪Ng(u,2))}導出的子圖Gd=(Vd,Ed)是否連通時,如果采用鄰接表為存儲形式,使用深度優(yōu)先的遍歷算法,計算復雜度為O(|Vd|+|Ed|).在Rule(2),Rule(3)下,節(jié)點u至多發(fā)送|N(u)|+1個消息,計算復雜度最壞的情況也是判斷圖的連通性.設需要判斷連通性的子圖為Gd=(Vd,Ed),如果采用鄰接表為存儲形式,使用深度優(yōu)先的遍歷算法,計算復雜度同樣為O(|Vd|+|Ed|).綜合算法1、算法2,即是MISB算法的全部過程.圖2表示了通過MISB算法得到的連通支配集.2.4misb算法原理下面通過證明MISB算法得到的集合是連通支配集,論證MISB算法的正確性.由定理1可知,MISB算法構造了極大獨立集Vi={v|(fi(v)=0)∧(v∈V)},下面在此基礎上證明MISB算法得到的集合Vc={v|(v∈V)∧(fc(u)=true)}是連通支配集,從而證明MISB算法是正確的.引理1設G=(V,E)為非平凡連通圖.Vi為G中極大獨立集,則Vi是G中極小支配集.證明由于Vi為極大獨立集,對任意u∈V-Vi,必存在v∈Vi,使得uv∈E成立;否則存在u0∈V-Vi,對所有v∈Vi,使得u0v?E成立,那么Vi∪{u0}是獨立集,這與Vi是極大獨立集相矛盾,所以Vi是支配集.又由于Vi是獨立集,所以對任意U?Vi,所有v∈Vi-U,不存在u∈U,使得uv∈E成立,所以Vi是G中極小支配集.證畢.引理2設G(V,E)為非平凡連通圖.Vi為G中支配集,Vp?Vi,則Vp是G中支配集.證明由于Vp?Vi,所以V-Vi?V-Vp.因而若任意u∈V-Vp,則u∈V-Vi,且存在v∈Vi,使得uv∈E成立.由于Vp?Vi,故v∈Vp.所以對任意u∈V-Vp,存在v∈Vp,使得uv∈E成立.所以Vp是G中支配集.證畢.引理3設G=(V,E)為非平凡連通圖,u∈V.記G中與u相鄰的頂點集合為N(u).存在頂點集合Vd,且Vd?V,N(u)?Vd,u?Vd.Gd為由Vd導出的子圖,記Gd=(Vd,Ed).在Gd中若任意x,y∈N(u)是連通的,則u不是圖G的割點.證明使用反證法.設u為圖G的割點,則在V-{u}導出的子圖中,存在節(jié)點u0、v0∈V-{u}且不連通,所以在圖G中u0,v0間的通路必具有如下形式:p=u0e1v1e2…xeiuei+1y…vk-1ekv0.其中v1,v2,…,vk-1∈V-{u},e1,e2,…ek∈E.且在點邊交錯序列中,邊的前驅和后繼節(jié)點分別是邊的兩個端點,且x,y∈N(u).由于N(u)?Vd,且x,y在圖Gd中是連通的,即存在通路xf1u1f2…um-1fmy,其中u1,u2,…um-1∈Vd.而f1,f2,…fm-1∈Ed,所以p0=u0e1v1e2…xf1u1f2…um-1fmy…vk-1ekv0是圖G中的u0,v0間通路.由于u?Vd,所以節(jié)點u不出現在通路p0中,即p0不具有p的形式,但仍然是u0,v0間通路,這與p0應具有p的形式矛盾.所以u不是圖G的割點.證畢.定理3MISB算法得到的集合Vc={v|(v∈V)∧(fc(u)=true)}是G=(V,E)的連通支配集.證明由定理1可知,MISB算法得到的集合Vi={v|(fi(v)=0)∧(v∈V)}是圖G=(V,E)的極大獨立集.在得到Vi后,MISB算法又分為三個階段,即以Vi為錨點,通過選舉規(guī)則Rule(1)、Rule(2)和Rule(3)依次作用來構造連通支配集.初始化時所有節(jié)點都屬于Vc,即fc(u)=true,u∈V.每個選舉規(guī)則就是非支配點剔除規(guī)則,即如果剔除非支配節(jié)點v,則令fc(v)=false.最終剩余的節(jié)點集即為Vc,記Vc的導出子圖為Gc.下面按序證明經過選舉規(guī)則Rule(1)、Rule(2)、Rule(3)依次作用后,得到的集合Vc是G的連通支配集.(1)Rule(1)在Rule(1)下剔除的是普通節(jié)點,設有N個節(jié)點n1…ni,…nN∈Vn被剔除,且{v|v∈(Ni(ni,2)∪Ng(ni,2))}在圖G中導出的子圖是連通圖.算法令fc(n1)=false,…,fc(nN)=false.在Rule(1)作用后,得到Vc=V-{n1…,nN},且Vi?Vc,Vi為MISB算法構造得到的極大獨立集.由于Vi?Vc,由引理1、2,可知Vc是支配集.下面用歸納法證明Vc導出的子圖Gc=G-{n1…,nN}是連通圖.設ni1,ni2…,niN是n1,n2…,nN的任一排列.當剔除ni1時,如ni1只有一個鄰節(jié)點,則ni1顯然不是割點,即G-{ni1}是連通圖.設節(jié)點ni1的鄰節(jié)點中有m個普通節(jié)點u1,u2,…,um,n個網關節(jié)點v1,v2,…,vn和1個獨立點w1.由于{v1,v2,…,vn}∪{w1}?{v|v∈(Ni(ni1,2)∪Ng(ni1,2))},且普通節(jié)點與且僅與一個獨立點相鄰,而與u1,u2,…,um相鄰的獨立點集必是Ni(ni1,2)的子集,所以由Vd={u1,u2,…,um}∪{v|v∈(Ni(ni1,2)∪Ng(ni1,2))}導出的子圖Gd=(Vd,Ed)是連通圖.而N(ni1)?Vd,由引理3推知,ni1不是圖G的割點,即G-{ni1}是連通圖.設在圖G中剔除點ni1,ni2,…nik(0<k<N)后,G-{ni1,ni2,…nik}是連通圖.當{v|v∈(Ni(ni(k+1),2)∪Ng(ni(k+1),2))}在圖G中導出的子圖是連通圖時,因為集合{v|v∈(Ni(ni(k+1),2)∪Ng(ni(k+1),2))}不包含任何普通節(jié)點,即ni1,ni2,…nik?{v|v∈(Ni(ni(k+1),2)∪Ng(ni(k+1),2))},所以{v|v∈(Ni(ni(k+1),2)∪Ng(ni(k+1),2))}在圖G-{ni1,ni2,…nik}中導出的子圖與{v|v∈(Ni(ni(k+1),2)∪Ng(ni(k+1),2))}在圖G中導出的子圖同構,也是連通圖.所以與在圖G中剔除點ni1后G-{ni1}仍然是連通圖同理,可證在圖G-{ni1,ni2,…nik}中剔除點ni(k+1)后G-{ni1,ni2,…nik}-{ni(k+1)}是連通圖,即G-{ni1,ni2,…nik,ni(k+1)}是連通圖.所以歸納可得,在經過Rule(1)作用后,Vc=V-{n1,…,nN}導出的子圖Gc=G-{n1…,nN}是連通圖.又因為Vc是支配集,所以Vc為G的連通支配集.(2)Rule(2)在Rule(2)下剔除的是網關節(jié)點,設有M個網關節(jié)點g1…gi,…gM∈Vg被剔除,且{v|(v∈(Ni(gi,2)∪Ng(gi,2)))∧((fe(v)=false)∨((fe(v)=true)∧(fc(v)=true)))}在圖G中導出的子圖是連通圖.算法令fc(g1)=false,…,fc(gM)=false.在Rule(1)、Rule(2)作用后,得到Vc=V-{n1…,nN}-{g1…,gM},且Vi?Vc.由于Vi?Vc,所以Vc是支配集.下面仍用歸納法證明Vc導出的子圖Gc=G-{n1…,nN}-{g1,…,gM}是連通圖.設gi1,gi2,…,giN是g1,g2,…,gN的任一排列,滿足在Rule(2)下規(guī)定的本地順序,且按節(jié)點自我選舉順序排列.當剔除gi1時,Vd={v|(v∈(Ni(gi1,2)∪Ng(gi1,2)))∧((fe(v)=false)∨((fe(v)=true)∧(fc(v)=true)))}在圖G中導出的子圖Gd是連通圖,且此時fe(x)=false(x為網關節(jié)點)或(fe(x)=true)∧(fc(x)=true)(x為獨立點)成立,其中x∈{v|(v∈(Ni(gi1,2)∪Ng(gi1,2)))},又n1…,nN?Vd,這等價于{v|(v∈(Ni(gi1,2)∪Ng(gi1,2)))}在圖G-{n1…,nN}中導出的子圖是連通圖.所以與在圖G中剔除ni1后G-{ni1}仍然是連通圖同理,可證圖G-{n1,…,nN}-{gi1}是連通圖.設在圖G-{n1…,nN}中剔除點gi1,gi2,…gik(0<k<M)后,G-{n1…,nN}-{gi1,gi2,…gik}是連通圖.當{v|(v∈(Ni(gi(k+1),2)∪Ng(gi(k+1),2)))∧((fe(v)=false)∨((fe(v)=true)∧(fc(v)=true)))}在圖G中導出的子圖是連通圖時,等價于{v|(v∈(Ni(gi(k+1),2)∪Ng(gi(k+1),2)))}在圖G-{n1,…,nN}-{gi1,gi2,…gik}中導出的子圖是連通圖.所以與在圖G-{ni1,ni2,…nik}中剔除節(jié)點ni(k+1)后G-{ni1,ni2,…nik}-{ni(k+1)}仍然是連通圖同理,可證G-{n1,…,nN}-{gi1,gi2,…gik}-{gi(k+1)}是連通圖,即G-{gi1,gi2,…gik,gi(k+1)}是連通圖.所以歸納可得,在經過Rule(1)、Rule(2)作用后,Vc=V-{n1,…,nN}-{g1,…,gM}導出的子圖Gc=G-{n1,…,nN}-{g1…,gM}是連通圖.又因為Vc是支配集,所以Vc為G的連通支配集.(3)Rule(3)在Rule(3)下,在連通圖G-{n1,…,nN}-{g1,…,gM}中剔除L個獨立節(jié)點,即令fc(d1)=false,…,fc(dL)=false,且d1,…,di…dL∈Vi.設di1,di2,…,diL是d1,d2,…,dL的任一排列,滿足在Rule(3)下規(guī)定的本地順序,且按節(jié)點自我選舉順序排列.在剔除di1時,保證了點di1不是圖G-{n1,…,nN}-{g1…,gM}的割點,且確保原來在圖G中與di1相鄰且不屬于V-{n1,…,nN}-{g1…,gM}的節(jié)點能夠與節(jié)點x相鄰,其中節(jié)點x是與di1相鄰或相距兩跳的節(jié)點,且x∈V-{n1,…,nN}-{g1,…,gM}-{di1}.這保證了連通性和支配性不被破壞,即V-{n1,…,nN}-{g1,…,gM}-{di1}是G的連通支配集.利用歸納法,與上面的證明過程同理,可證Vc=V-{n1,…,nN}-{g1,…,gM}-{d1,…,dL}是G的連通支配集.所以在經過Rule(1)、Rule(2)、Rule(3)作用后,得到的集合Vc是G的連通支配集.證畢.3實驗結果分析為評估MISB算法的性能,我們仿真了僅利用兩跳內節(jié)點信息構造連通支配集的算法,包括MISB、MPR和EMPR,對各算法在不同實驗條件下得到的連通支配集大小進行了比較.MPR與EMPR的計算復雜度為O(Δ2),Δ為網絡節(jié)點最大度.假設節(jié)點為全向通信.如果兩節(jié)點間的距離小于等于通信半徑,則兩節(jié)點相鄰.如果構造的網絡未連通,則須重新構造.我們根據網絡區(qū)域范圍、節(jié)點數目、通信半徑的不同,分別做了以下3個仿真實驗.實驗結果以列表的方式給出.實驗1節(jié)點的通信半徑為1,在1×1、2×2、3×3、4×4、5×5、6×6、7×7的區(qū)域上分別隨機均勻放置100個節(jié)點構造連通網絡各100個,比較各算法在不同區(qū)