一种求解最小连通支配集的分布式算法

一种求解最小连通支配集的分布式算法

1基于misb的最小连通支配集算法广播是无线传感器网络和移动自组织网络的一种常见通信模式，可以用于连接所有路径、业务信息和参数配置。广播通常执行泛流（flooding）。这是简单的，但它会导致大量的网络捐款，导致通信风暴等问题。由于资源高度有限，发送数据非常高，网络上的传输流量非常高，因此不可避免地消耗了资源不足。为了避免flooding方法的缺点，网络中的冗余节点应该减少。也就是说，当所有网络节点都接收到并且接收到数据包时，网络中的节点数应该减少。在无线网络广播中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价.而在任意图中求解最小连通支配集是NP完全问题,所以在实际应用中常用启发式算法来求其近似解.求解的过程可以采用集中式方法和分布式方法.采用集中式方法虽然能够得到较小的连通支配集,但在多数无线应用中,使用整个图的拓扑信息来构造连通支配集并不可取,一般应采用分布式方法,相应的算法有MPR及其扩展算法和其它算法.这些算法大多是利用两跳内节点信息,采用分布式方法构造连通支配集,但也有例外,如文献是利用三跳内节点信息构造连通支配集,且只有在节点密度极大的条件下才有较好的性能.为在无线传感器网络和移动自组织网络中进行更为有效的广播,本文仅利用两跳内节点信息提出了基于极大独立集的最小连通支配集的分布式算法(称为MISB).MISB算法不是采用直接构造连通支配集的方式,而是首先利用分布式贪心算法,选举具有极大度(Maximaldegree)的节点为独立点,构造出一种特殊的无任何两个节点相邻的极小支配集,即极大独立集;然后利用独立点作为锚点,利用分治的思想添加非独立点来连通极大独立集.实际上,MISB是通过剔除不破坏网络连通性的节点来达到添加非独立点的目的,而网络连通性的判断只依赖两跳内节点.此外,在不破坏连通支配集的条件下,独立点也可放弃自身的支配点地位.与同样利用两跳内节点信息构造连通支配集的算法MPR和EMPR相比,MISB算法能够得到较小的连通支配集.2misb算法2.1vd的非空子集定义1图的相关定义一个无向图是一个有序的二元组(V,E),记作G.其中,V是一个非空集合,称为点集,其元素称为点、顶点或节点;E是由V中的点组成的无序点对构成的多重集合,称为边集,其元素称为边.在不引起歧义的情况下,无向图简称为图.图中的边e记为uv,即e=uv.称u、v为e的端点,称u(或v)与e关联,并称节点u、v相邻.连接两个相同点的边的条数称为边的重数,重数大于1的边称为重边.端点重合为一点的边称为环.只有一个点的图称为平凡图.设Vd是V的非空子集.以Vd为点集、以两端点都在Vd的边的全体为边集构成的子图,称为G的由Vd导出的子图.G中点u的度是指G中与u关联的边的数目,记为d(u).没有环也无重边的图称为简单图.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中的节点称为独立点.设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节点选举算法MISB算法是在极大独立集的基础上来构造连通支配集,所以首先应构造极大独立集.直觉上具有较大度的点支配性好,所以使用贪心算法选择具有极大度的点来构造极大独立集.如果相邻节点具有相同的极大度,则利用标号来打破僵局.设图G=(V,E)为简单连通非平凡图.G中所有点都唯一标号,节点vi的标号记为id(vi),并且若vi≠vj,那么id(vi)>id(vj)或id(vi)<id(vj)之一必成立.节点u、v∈V,当且仅当(d(u)>d(v))∨((d(u)=d(v))∧(id(u)<id(v)))时,定义u≻vu≻v.由于节点唯一标号,显然(V,≻)(V,≻)是一个全序集.设Z+为非负整数集合,定义函数fi:V→Z+,其值的确定方法及意义见下述构造极大独立集算法过程.定义函数fe:V→{true,false},fe(v)=true表示节点v已进行了自我选举,否则fe(v)=false.算法1构造极大独立集的算法(1)所有节点u∈V,初始化u.fi(u)←0,u.fe(u)←false.(2)相邻节点进行邻居发现,节点u的邻节点集记为N(u).(3)相邻节点交换邻居信息,节点u获得了d(x),其中x∈N(u).(4)所有节点u∈V,初始化u.fe(x)←false,其中x∈N(u).(5)所有节点u∈V,对{u}∪N(u)按照运算符≻≻进行本地排序,然后按序选举.选举规则如下:若节点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)所有节点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能正常开始和结束.且在选举规则中,每个节点的仅需发送1个消息,计算复杂度可忽略.并且网络中所有节点u∈V都获得了其邻节点的fi(x)值,x∈N(u).选举结束后,记Vi={v|(fi(v)=0)∧(v∈V)};记Vn={v|(fi(v)=1)∧(v∈V)},其元素称为普通节点;记Vg={v|(fi(v)>1)∧(v∈V)},其元素称为网关节点.在图1中,设id(vi)>id(vj),当且仅当i>j.图1表示了算法1的选举结果.由算法1,可得以下定理:定理1集合Vi={v|(fi(v)=0)∧(v∈V)}是图G=(V,E)的极大独立集.证明算法1中,相邻节点在本地排序,然后按序选举.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中加入任一节点w(w∉Vi),而fi(w)>0,fi(w)表示与节点w相邻的Vi节点数,故w必与Vi中fi(w)个节点相邻,因此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节点自身保护在得到极大独立集Vi后,以此为基础来构造最小连通支配集.首先确定在图中不是独立点、且不是割点的节点为非支配点,从而构造出连通支配集;然后对独立点进行检查,剔除不破坏连通性和支配性的独立点,使之为非支配点.在确定节点是否为支配点时,算法利用了与节点相邻的两跳内节点信息.为便于讨论,使用如下符号:Vi(u)表示与节点u相邻的独立点集,Vi(u,2)表示与节点u相距2跳的独立点集,令Ni(u,2)=Vi(u)∪Vi(u,2);Vg(u)表示与节点u相邻的网关节点集,Vg(u,2)表示与节点u相距2跳、且与Vi(u)中任一节点相邻的网关节点集,令Ng(u,2)=Vg(u)∪Vg(u,2);Vn(u)表示与节点u相邻的普通节点集.定义函数fc:V→{true,false}.其值的确定方法及意义见下述构造最小连通支配集算法过程.算法2构造最小连通支配集的算法(1)所有节点u∈V-Vi,初始化u.fc(u)←true,u.fe(u)←false.(2)所有节点u∈Vi,初始化u.fc(u)←true,u.fe(u)←true.(3)所有节点u∈V-Vi,本地通告u的Vi(u)信息.x∈N(u)保存通告信息.(4)所有节点u∈Vi,本地通告u的Vg(u)信息.x∈N(u)保存通告信息.(5)所有节点u∈V-Vi,计算Ni(u,2)、Ng(u,2).(6)所有节点u∈Vi,计算Vi(u,2).(7)所有节点u∈Vn,进行支配点选举.选举规则如下: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)所有节点u∈Vg,对{u}∪Ng(u,2)按照运算符进行本地排序,然后按序选举.选举规则如下:Rule(2):若节点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);并转发通告.接收到直接通告或转发通告的节点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)所有节点u∈Vi,在其邻节点选举结束后,对{u}∪Vi(u,2)按进行本地排序,初始化u.fe(u)←false,u.fe(x)←false,其中x∈Vi(u,2),然后按序选举.选举规则如下:Rule(3):若节点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)}接收到通告后,进行转发.接收到转发通告的节点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)下,节点u仅需发送1个消息,计算复杂度最坏的情况是判断图的连通性.u在判断Vd={v|v∈(Ni(u,2)∪Ng(u,2))}导出的子图Gd=(Vd,Ed)是否连通时,如果采用邻接表为存储形式,使用深度优先的遍历算法,计算复杂度为O(|Vd|+|Ed|).在Rule(2),Rule(3)下,节点u至多发送|N(u)|+1个消息,计算复杂度最坏的情况也是判断图的连通性.设需要判断连通性的子图为Gd=(Vd,Ed),如果采用邻接表为存储形式,使用深度优先的遍历算法,计算复杂度同样为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}导出的子图中,存在节点u0、v0∈V-{u}且不连通,所以在图G中u0,v0间的通路必具有如下形式:p=u0e1v1e2…xeiuei+1y…vk-1ekv0.其中v1,v2,…,vk-1∈V-{u},e1,e2,…ek∈E.且在点边交错序列中,边的前驱和后继节点分别是边的两个端点,且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,所以节点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为锚点,通过选举规则Rule(1)、Rule(2)和Rule(3)依次作用来构造连通支配集.初始化时所有节点都属于Vc,即fc(u)=true,u∈V.每个选举规则就是非支配点剔除规则,即如果剔除非支配节点v,则令fc(v)=false.最终剩余的节点集即为Vc,记Vc的导出子图为Gc.下面按序证明经过选举规则Rule(1)、Rule(2)、Rule(3)依次作用后,得到的集合Vc是G的连通支配集.(1)Rule(1)在Rule(1)下剔除的是普通节点,设有N个节点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只有一个邻节点,则ni1显然不是割点,即G-{ni1}是连通图.设节点ni1的邻节点中有m个普通节点u1,u2,…,um,n个网关节点v1,v2,…,vn和1个独立点w1.由于{v1,v2,…,vn}∪{w1}⊆{v|v∈(Ni(ni1,2)∪Ng(ni1,2))},且普通节点与且仅与一个独立点相邻,而与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))}不包含任何普通节点,即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)下剔除的是网关节点,设有M个网关节点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)下规定的本地顺序,且按节点自我选举顺序排列.当剔除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为网关节点)或(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}中剔除节点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个独立节点,即令fc(d1)=false,…,fc(dL)=false,且d1,…,di…dL∈Vi.设di1,di2,…,diL是d1,d2,…,dL的任一排列,满足在Rule(3)下规定的本地顺序,且按节点自我选举顺序排列.在剔除di1时,保证了点di1不是图G-{n1,…,nN}-{g1…,gM}的割点,且确保原来在图G中与di1相邻且不属于V-{n1,…,nN}-{g1…,gM}的节点能够与节点x相邻,其中节点x是与di1相邻或相距两跳的节点,且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算法的性能,我们仿真了仅利用两跳内节点信息构造连通支配集的算法,包括MISB、MPR和EMPR,对各算法在不同实验条件下得到的连通支配集大小进行了比较.MPR与EMPR的计算复杂度为O(Δ2),Δ为网络节点最大度.假设节点为全向通信.如果两节点间的距离小于等于通信半径,则两节点相邻.如果构造的网络未连通,则须重新构造.我们根据网络区域范围、节点数目、通信半径的不同,分别做了以下3个仿真实验.实验结果以列表的方式给出.实验1节点的通信半径为1,在1×1、2×2、3×3、4×4、5×5、6×6、7×7的区域上分别随机均匀放置100个节点构造连通网络各100个,比较各算法在不同区