（应用数学专业论文）图的连通度、强定向及无线传感器网络.pdf

图的连通度、强定向及无线传感器网络 中文摘要中又摘要 图论是一门富有趣味性和应用极为广泛的学科，它在化学、生物学、计算 科学以及通信网络等方面都有广泛的应用本文主要研究图的强定向和最优 强( k ，d ) 定向以及图论在无线传感器网络中的应用等课题。 无线传感器网络( w s n ) 是由部署在监测区域内大量的微型传感器节点通 过无线电通信形成的一个网络系统传感器节点由传感单元、处理单元、无线 收发单元和电源单元等几部分组成无线传感器网络的出现引起了全世界广泛 关注，其应用已经由军事国防领域扩展到环境监测、交通管理、医疗健康、工商 服务和反恐抗灾等诸多领域 在无线传感器网络中，传感器节点的能量通常是电池。由于网络成本及环 境因素，这些电池能量耗尽后，就无法再充电或更换电池而继续使用因此，在 保证网络覆盖以及网络畅通的基础上，如何延长网络的工作时间，是目前无线 传感器网络研究的一个重要方面。 在本文中，我们提出了一种新型的无线传感器网络在此网络中，假设已 知所有监控的离散目标的具体位置，并在每个目标周围部署大量的传感器节点， 而后将节点所监测到的信息传输给一个或多个信息中心将所有的传感器节点 分成最大数量的不相交的传感器节点的集合，其中每个集合所包含的传感器节 点能完全覆盖所有目标，并且将监测到的信息有效地传输给信息中心然后将 这些集合所包含的传感器节点依次激活。使得在任何时刻，都恰好只有处于活 跃状态的节点负责监控与信息传输，而其余节点能量耗尽或处于睡眠状态这 种方法足延长无线传感器网络工作时间的一种较有效的方式因此，我们的目 标就是找出最大数量的不相交的传感器节点集合 将无线传感器网络的每个节点看成图g 的一个顶点，并且乱口e ( g ) 当且 仅当乱和秒所对应的传感器节点在彼此的传感范围之内通常称g 为网络图 我们考虑此类型无线传感器网络的三种不同的模型 1 假设无线传感器网络的每个传感器节点恰好只监控一个目标设l ，2 ， 赴分别为z 个需要监控的目标，a l ，a 2 ，a 为图g 的顶点子集，其中若顶点可 所对应的传感器节点监控目标i ，则口a ，从而ana f = d ，l i 歹z 在 这个模型下，我们将无线传感器网络的覆盖与能量有效性问题归结为图的不交 c h i n e s ea b s t r a c t 集合覆盖与连通问题( d s c c p r o b l e m ) 定义1 不交集合覆盖与连通问题p s c d p m 6 f e 叫：设( a l ，a 2 ，a z ) 为图g 的顶点划分。是否存在最大的整数七，使得存在g 的两两点不交的连通子 图g 1 ，g 2 ，g 七满足，| y ( g ) na j i 1 ，其中1 i 七和1 j z ? 我们证明该问题是n p 完全的，进而给出一个相关的近似算法最后，我们 给出该近似算法的理论分析及实验估计。 2 有时两个需监测的目标之间或目标与信息中心之间的距离较远，为了保 证网络的畅通，需要部署一些只负责信息传输的传感器节点在此模型中，假 设无线传感器网络的某些传感器节点同时负责监控与信息传输，其余的传感器 节点只负责信息传输 在网络图g 中，称信息中心节点所对应的顶点为中心顶点假定无线传感 器网络有! 个离散的监控目标，每个目标可同时处于奄个传感器节点的监控范 围之内。设4 l 为g 中对应于监控第i 个目标的传感器节点所对应的顶点的集 合，其中1 i z ；设s 为g 的中心顶点集合，那么a ins = 仍和a tna f = d ， 其中1 i 歹z g 的包含s 的一个顶点以及每个a 的一个顶点的连通子 图，对应于无线传感器网络中监控所有目标，并且将监测到的信息传输给至少 一个信息中心的节点的集合。因此，无线传感器网络的最大数量的不相交的传 感器节点集合的数目，就是g 中最大数量的这样的连通子图的数目。进一步地， 包含多个信息中心节点的无线传感器网络的覆盖与能量有效性问题可归化为只 包含一个信息中心节点的覆盖与能量有效性问题因此，我们假设网络图g 只 有一个中心顶点s 我们找到图的一个参数一连通度来达到无线传感器网络的 覆盖与能量有效性 定理1 设a l ，a 2 ，a z 为图g 的两两点不交的顶点子集，并且i a i i = 七，1 i z ，s y ( g ) u 1 月 如果后= 2 和g 是h m a x ( 1 ，z 一4 ) 连通的，或者七23 和g 是z ( 七一1 ) + 1 连通的，那么存在七个连通子图g 1 ，g 南，使得 ( o ) f y ( g ) na i = 1 ，其中l i 七和l 歹z ； ( 6 ) y ( g i ) ny ( g j ) = f s ) ，1 i 歹七 c h i n e s ea b s t r a c t 由定理1 ，如果忌= 2 ，并且无线传感器网络所对应的网络图g 是z + m a ) ( l ，z 一4 连通的，或者七芝3 和g 是z ( 七一1 ) + l 连通的，那么可以找到七 个( 最大数量) 传感器节点的不相交的集合，其中每个集合所包含的传感器节点 完全覆盖所有目标，并且将监测到的信息有效地传输给信息中心，也就足可使无 线传感器网络的工作时间提高老倍。同时，我们还证明了连通度条件z ( 奄一1 ) + 1 连通是紧的，并且我们猜想当后= 2 时，f + l 连通是足够的 猜想1 设a 1 ，a 2 ，a f 为图g 的两两点不交的顶点子集，并且 a i = 2 ，1 i z ，s y ( g ) u 匕1a 如果g 是f + l 连通的，那么存在连通子图g 1 ，g 2 ，使 得 ( n ) l y ( g t ) n i = 1 ，其中i = 1 ，2 和l 歹l ； ( 6 ) y ( g z ) ny ( g 2 ) = s 最后，我们也给出了相应的算法来找出这七个传感器节点的集合 3 通常情况下，同时负责信息传输与监控的传感器节点的能量消耗比只负 责信息传输的传感器节点的能量消耗来得快些在模型2 的基础上，假设那些 只负责信息传输的传感器节点的工作时问，是那些同时负责监控与信息传输的 节点的工作时间的d 倍设同时负责信息传输与监控的传感器节点的工作时间 为一单位时间 同模型1 与2 一样的考虑，我们将全部传感器节点划分为多个集合，使得 每个节点的集合既能监控所有目标，又能保证将监测到的全部信息传输给信息 中心。但是，某个只负责信息传输的传感器节点可能会同属于两个或多个不同 的传感器节点的集合。而且由于环境因素及成本考虑，在每个传感器节点上安 装开关是不太可能实现的因此，我们假设每个传感器节点一旦被激活就不能 被关闭，直到能量耗尽从而，那些含有共同传感器节点的任意两个集合，它 们所含的传感器节点被激活的时间间隔不能超过d 个单位时问特别的，如果 一个节点已被激活，若它还属于另一个即将被激活的节点集合，则该传感器节 点无需再次激活。我们的目标就是寻找最大数量的有序的节点的集合，使得每 个集合所含的传感器节点的传感范围能完全覆盖所有目标，并保证将监测到的 全部信息传输给信息中心，而且对于任两个含有共同传感器节点的集合，它们 的序号之差不能超过d 对应于网络图g ，我们的目标就是寻找最大数量的包 i i i c h i n e s ea b s t r a c t 含点s 且包含每个a t 的顶点的有序连通子图g l ，g 2 ，g 口，使得任意两个子 图g 和g ，如果它们包含除s 外的共同顶点，那么l i 一歹l d 一1 我们证明了，即使无线传感器网络所对应的网络图满足一定的连通度的条 件，要找出无线传感器网络的最优工作时间仍是n p 完全的我们给出一个近 似算法来提高无线传感器网络的工作时间，并且给出该算法的理论分析与实验 估计 众所周知，在交通系统中应用单行道，不仅会减少交通事故，而且可以简化 交通控制管理。单行道问题的图论模型最初是由r a b b i n s 5 1 】引入的。单行道问 题是一个关于图的定向的问题目前已有很多结果 2 ，1 4 ，2 4 ，3 4 ，5 2 ，5 3 ，5 4 ，5 5 】 基于不同的指标来研究与单行道问题相关的图的定向c h a r t r a n d 等人 9 】引入 了强有向图和强定向图的强距离、强半( 直) 径的新概念，它们成为图的定向的 新的重要指标。 设t z 和 是强定向图d 的两个顶点，d 中包含乱和t ，的最小强有向子图的弧 数称为u 和u 的强距离s 而( u ，u ) d 的任一顶点 的强离心率s e ( u ) 为u 与d 中 其它所有顶点的强距离的最大值d 的强半径s r 口d ( d ) ( 强直径5 出口仇( d ) ) 为d 中所有顶点的强离心率的最小值( 最大值) 对于无向图，l a i 等人 3 6 给出了图 的最小( 大) 强半径及最小( 大) 强直径的定义设g 是一个连通图。g 的最小 强半径s r o d ( g ) ( 最大强半径s r a d ( g ) ) 为g 的所有强定向图的强半径的最小 值( 最大值) 。类似地，g 的最小强直径s 施n m ( g ) ( 最大强直径s j ) ，4 m ( g ) ) 为g 的所有强定向图的强直径的最小值( 最大值) 。对于图g 的任一强定向图d ，都 有仡( d ) 【圪( g ) 2 j 和s d i n m ( d ) s 出口m ( g ) 成立，其中圪( d ) ( k ( g ) ) 为d 的 强连通度( g 的连通度) 。通常，并不足所有的强定向图能同时满足两个等号我 们将同时使两个等号成立的定向称为图g 的一个最优强( ，c ，d ) 定向。 本文基于强距离、强半( 直) 径、强连通度等指标，研究特殊图类的强定向 问题，得到以下结果。 1 设k ( m 1 ，m 2 ，m 詹) 为完全七部图，其中m 1 ，m 2 ，m 分别为其顶点 集的后部划分的子集的基数我们研究了完全七部图的强定向图的强半径与强 直径的一些性质 引理2 设后3 为任一整数，1 = 仇1 = = m ， m 七时， s r o d ( k ) = 3 和s 出。仇( k ) = 4 ； 当仇1 + m 2 + + m 七一l m 岛时，s r n d ( k ) = 3 和s 以n 仇( k ) = 5 i v c h i i l e s ea b s t r a c t 引理3 设七3 为任一整数，2 m 1 m 2 m | l c 那么存在一个完全七部 图k ( m 1 ，m 2 ，m 七) 的强定向图五使得 当m 1 + m 2 + + m 七一i2 竹k 时，s r n d ( k ) = s 垅o m ( ) = 4 ； 当m 1 + m 2 + + m 七一1 ( l 攀j ) r c h i n e s ea b s t r a c t 定理7 设尼3 和m 1 = m 2 = = m 七= 1 那么， s 出口m ( k ( m 。，忱，m 七) ) ： 3 ， 4 七4 ， 后= 4 定理8 设七3 和l m l m 2 m 七，且m 七2 令仇= m 1 + m 2 + + m 七一1 。那么， s 如n m ( k ( m 。，m ：，m 南) ) ： 4 ， 5 ( 【攀j ) ( 【攀j ) 仇知， m 屉 定理9 设后3 和1 m 1 m 2 仇知，且令m ，= m 1 + m 2 + + 一1 那么 s 。，a m ( k ( m 。，m 。，仇南) ) ： 2 m + 2 ， m + m 七+ 1 ， m m 七， m m 七 定理1 0 设七3 ，1 m l m 2 m 七和m = 仇l + 仇2 + + m 七一1 那么 s r a d ( k ( m 1 ，m 2 ，m 凫) ) f m + l ， 、【篙产j + 1 ， s r a d ( k ( m l ，m 2 ，m 南) ) m m 知， m m 七； m i n 2 m + 2 ，仇+ m 南 ， m + 仇七， 3 我们证明了任一完全七部图均存在最优强( 仡，d ) 定向 m m 七， 仇m 知 定理1 1 设七2 ，仇l m 2 m 七，m 船2 ，且令m = m 1 + m 2 + + m 南一1 2 那么k ( 。1 ，m 2 ，”) 存在一个最优强( k ，d ) 定向。 关键诃：连通度；无线传感器网络；能量有效性；n p 完全问题；完全后部 图；强距离；最小( 大) 强半径；最小( 大) 强直径；最优强( ，c ，d ) 定向 v i c o n n e c t i v i t y s t r o n go r i e n t a t i o no fg r 印h sa n d w i r e l e s ss e n s o rn e t w o r k s a b s t r a c t g r 印ht h e o vi sav e r yp o p u l a ra r e ao fd i s c r e t em a t h e m a t i c s 丽t hn o to n l y n u m e r o u st h e o r e t i c a ld e v e l o p m e n t s ， b u ta l s oc o u n t l e s 8 印p l i c a t i o n st op r a c t i c a l p r o b l e i i l s ，s u c ha s ，c h e m i s t 吼b i o l o g ) r ，c o m p u t e rs c i e n c e ，c o m m u n i c a t i o nn e t 、阳r l 【s t h i st h e s i si sm a i n l ya b o u tt h es t r o n go r i e n t a t i o na n dt h eo p t i m a ls t r o n g ( 仡，d ) - o r i e n t a t i o no fg r a p l l s ，a n ds o m e 印p l i c a t i o i l si n 而r e l e s ss e l l s o rn e t 、m r l ( s aw i r e l e s ss e n s o rn e t w d r k ( w s n ) i saw i r e l e s sn e t 、v o r kc o m p r i s e do fal a r g e n u m b e ro fs e n s o rn o d e s 、柚i c ha r ed e p l o y e dr a n d o m l y w i r e l e s ss e l l s o rn e t 、舯r k s h a v ea t t r a c t e dag o o dd e a lo fr e s e a r c ha t t e n t i o n 嬲t h e yu s e di nm a n ya p p l i c a t i o n a r e a s ，i n c l u d i n gb a t t l e 6 e l ds u r v e i l l a n c e ，e n v i r o i 珈e n ta n dh a b i t a tm o n i t o r i n g ，h o m e a u t o m a t i o n ，i n v e r l t o r yt r a c k i n g ，a n dh e a i t h c a r ea p p l i c a t i o n ( 5 6 】 i nw i r e l e s ss e n s o rn e t w o r l ( s ，e n e r g ) rs o u r c ei su s u a l l yb a t t e r yc e l l ，w h i c hi s i m p o s s i b l et or e c h a r g ew h i l ew s n sa r e 、釉r l ( i n g t h e r e f o r e ，o n eo ft h em a i ni s s u e s i nw i r e l e s ss e n s o rn e t 、o r k si sh o wt op r 0 1 0 n gt h en e t w o r kl i f e t i m eo fw s n sw i t h c e r t a i ne n e r g ys o u r c ea sw e l la sh o wt om a i n t a i l lc o v e r a g ea n dc o 肌e c t i v i t y w ea d d r e s sa na p p l i c a t i o nw h i c hm o n i t o r sas e to ft a r g e t sw i t hk n o w nl o c a t i o 璐al a r g en u n l b e ro fs e n s o rn o d e sa r ed i s p e r s e dr a n d o m l yi nc l o s ep r o x i m i t yt o t h es e to ft a r g e t s ，a n ds e n dt h em o n i t o r e di i l f o r m a t i o nt oo n eo rm o r ec e n t r a lp r 伊 c e e d i n gn o d e s a ne m c i e n tm e t h o dt oe x t e n dt h e ，i r e l e s ss e n s o rn e t w d r kl i f e t i m e i ss p l i t t i n gt h es e 璐o ri l o d e si n t oam a ) ( i m a ln u m b e ro fd i s j o i n ts e t se a c ho fw h i c h c o m p l e t e l yc o 、r sa l lt h et a r g e t sa n ds e n dt h em o n i t o r e di n f o r m a t i o nt ot h ec e n t r a l p r o c e e d i n gn o d e s ，a n dt h es e t sa r ea c t i v a t e ds u c c e s s i v e l y o n l yt h es e n s o rn o d e s f r o mt h ea c t i v es e t sa r er e s p o n s i b l ef o rm o n i t o ra nt h et a r g e t sa s 、v e ua se a c ha c t i v a t e ds e tr e m a i n sc o n n e c t e df b rd a t ac o u e c t i o n w ec o n s i d e rt h r e ed i 任b r e n tm o d e l s f o rt h i sa p p l i c a t i o n 1 s u p p o s et h a te a c hs e n s o rn o d e sm o n i t o r se x a c to n et a r g e t w bp r e s e n tt h i s m o d e la st h ed 埘o i n ts e t sc o v e r a g ea n dc o n n e c t i v i t y ( d s c c ) p r o b l e m ，a n dp r o v ei t i sn p c o m p l e t e a n d r ed e s i g na na p p r o x i m a t ea l g o r i t h ma n dp r e s e n ta ne m c i e n t x i x e n g l i s ha b s t r a c t i m p l e m e n t a t i o no fh e u r i s t i cf u n c t i o 璐f o rt h i sa l g o r i t h m t h e o r e t i c a la n a l ”i sa n d e x p e r i m e n t a le v a l u a t i o n sa r ea l s og i v e n 2 s u p p o s et h e 、) l r i r e l e s ss e n s o rn e t 、0 r l ( ss a t i s f y i n gt h a ts o m en o d e se a c ho f w h i c hm o n i t o r so n et a r g e ta n dt r a n s f e r si n f o r m a t i o n ，t h eo t h e r sj u s tf o rc o n n e c t i o n a s s u m et h e r i r e l e s ss e n s o rn e t 、：l ，o r kh a szt a r g e t s ，a r l de a c hi sm o n i t o r e db y 七s e n s o r n o d e s 、es h o wi f 后= 2a n dt h eg r a p hgc o r r e s p o n d i n gt ot h e 祈r e l e s ss e l l s o r n e t 、o r ki s ( z + m a x 1 ，z 一4 ) ) 一c o n n e c t e d ，o r 七3a n dg i s ( f ( 七一1 ) + 1 ) 一c o n n e c t e d ， t h e n 陀c a nf i n d 七( t h em a x i i i l u mn u m b e r ) d 埘o i n ts e t se a c ho fw h i c hc o m p l e t e l y c o v e r sa ut h et a r g e t sa n dr e m a i n sc o n n e c t e dt oo n eo ft h ec e n t r a lp r o c e s s i n gn o d e 8 t h e s ed 蚓o i n ts e t sa r ea c t i v a t e ds u c c e s s i v e l y ，a n do n l yt h es e l l s o rn o d e sf r o mt h e a c t i v es e ta r er e s p o 璐i b l ef o rm o n i t o r i n gt h et a r g e t sa n dc o n n e c t i v i t y a l lo t h e r n o d e s 甜ei n t oas l e e pm o d e a n d 陀a l s og i v et h er e l a t e da l g o r i t h m st of i n dt h e 七 d i s j o i n ts e t s 3 b a s eo nt h em o d e l2 ，a u s s u m et h e 、v o r k i n gt i m eo ft h en o d eo n l yf o rc o n - n e c t i o ni sdt i m e sa st h eo n eb o t hf o rm o n i t o r i n ga n dc o n n e c t i o n w 宅s h o wt h a ti t i 8n p c o m p l e t et oo r g a n i z e 址屹r l o d e si n t om a x i m u mn u m b e ro fd i f f c r e l l ts c t s ，e v e n t h o u g ht h en e t 、v o r kg r 印h ss a t i s 矽s o m ec o n d i t i o n so fc o n n e c t i v i t y a n 印p r o 癌 m a t ea l g o r i t h mi sd e s i g n e dt oi m p r o v et h el i f e t i m eo fw s n s t h e o r e t i c a la n a l y s i s a n de x p e r i m e n t a le v a l u a t i o 璐a r ea l s op r e s e n t e d i ti s r e l l k n o w nt h a ti n t r o d u c t i o no fo n e - 倍ys t r e e tu s u a l l yd e c r e a s e st h e n u m b e ro fc a ra c c i d e n t sa n da l l o w so n et os i m p l i 移t h et r a 伍cc o n t r 0 1 g r a p h t h e o r e t i c a lm o d e lo ft h eo n e - w a ys t r e e tp r o b l e mc a nb et r a c e db a c kt ot h ec l a s s i c a l p a p e ro f 弛b b i n s 5 1 】o n e w a y8 t r e e tp r o b l e mi sap r o b l e mo fo r i e n t a t i o n ，i n w h i c hm a n yc r i t e r i a 、e r ei n t r o d u c e d 【2 ，1 4 ，2 4 ，3 4 ，5 2 ，5 3 ，5 4 ，5 5 】t h ed e f i i l i t i o l l s o fs t r o n gd i s t a n c e ，s t r o n gr a d i u s ( d i a m e t e r ) o fs t r o n gd i g r a p h sa n ds t r o n go r i e n t e d g r a p h s 、v e r ei 1 1 t r o d u c e db yc h a r t r a n de n f 【9 】f b rt w ov e r t i c e su a n dui na s t r o n go r i e n t e dg r a p hd ，t h es t r o n gd i s t a n c es d d ( u ， ) b e t 、) l ，e e n 乱a n d i st h e m i i l i m u ms i z e ( t h e 肌m b e ro fa r c s ) o fas t r o n gs u b _ d i g r a p ho fdc o n t a i n i n g 乱 a n du f b rav e r t e xuo fd ，t h es t r o n ge c c e n t r i c i t ys e d ( 口) i st h e8 t r o n gd i s t a n c e b e t ，e e n 秽a n dav e r t e xf a r t h e s tf r o m 可t h es t r o n gr a d i u ss r n d ( d ) ( r e s p s t r o n g d i a m e t e rs 也口m ( d ) ) i st h em i n i m u m ( r e s p m a ) ( i l u m ) s t r o n ge c c e n t r i c i t ya m o n g t h ev e r t i c e so fd f b rg e n e r a lg r a p h ，l a ie 口z 3 6 】g a et h ed e f i n i t i o n so ft h e e n g l i s ha b s t r a c t l o 、v e ra n du p p e ro r i e n t a b l es t r o n gr a d i u sa n dd i a m e t e r t h el o w r e r ( r e s p u p p e r ) o r i e n t a b l es t r o n gr a d i u ss r o d ( g ) ( r e s p s 冗a d ( g ) ) o fag r a p hgi st h em i n i m u m ( r e s p 。m a ) ( i m u m ) s t r o n gr a d i u so v e ra 1 1s t r o n go r i e n t a t i 0 i l so fg t h el o 观r ( r e 印。 u p p e r ) o r i e n t a b l es t r o n gd i a m e t e rs 出n m ( g ) ( r e s p s d ，a m ( g ) ) o fag r a p hg i st l l em i n i m l l i n ( r e s p m a x i m u m ) s t r o n gd i a m e t e ro v e ra l ls t r o n go r i e n t a t i o n so f g f b ra n ys t r o n go r i e n t a t i o ndo fag r a p hg ，i ts a t i s f i e sk ( d ) 【k ( g ) 2 ja n d s 反口m ( d ) s 旋8 m ( g ) ，w h e r e 托( p ) ( r e s p 。芄( g ) ) i st h es t r o n gc o n n e e t i v i t yo f d ( r e s p c o n n e c t i v i t yo fg ) u s u a l l y n o ta l lt h es t r o n go r i e n t a t i o 瑚o fg c a n s a t i s 匆b o t ho ft h e s ee q u a l i t i e s 、d e f i n et h es t r o n go r i e n t a t i o no fg 8 a t i s f i e sb o t h e q u a l i t i e sa st h eo p t i m a ls t r o n g ( k ，d ) 一o r i e n t a t i o n b a s eo nt h ec r i t e r i a ，1 i k es t r o n gd i s t a n c e ，s t r o n gr a d i u s ( d i a m e t e r ) ，w ef o e u so n t h es t r o n gd i s t a n c ea n ds t r o n gr a d i u s ( d i a m e t e r ) i ns o m es p e c i a lo r i e n t e dg r a p h s w bg e tt h ef o l l o 丽n gr e s u l t s 1 w 宅s h o wt h a t ，f o ra i l yi n t e g e r sj ，r ，dw i t ho 6 f 后2 1 1 ，3 7 【凳2 j + l ，4 ds 膏，t h e r ea r eo r i e n t e dc o m p l e t e 肛p a r t i t eg r a p h s ，k ”，k ”7 s u c ht h a ts 出口仃。( k 7 ) 一s r o d ( k 7 ) = 6 ，s 7 n 矗( ”) = r ，a i l ds 班o m ( k ”7 ) = d 2 w ed e t e r m i n et h el o 、7 l ，e ro r i e n t a b l es t r o n gr a d i u sa n dd i a m e t e ro fc o m p l e t e 七一p a r t i t eg r a p h s ，a n dg i v et h eu p p e ro r i e n t a b l es t r o n gd i a m e t e ra n dt h eb o u n d so n t h eu p p e ro r i e n t a b l es t r o n gr a d i u so fc o m p l e t e 肛p a r t i t eg r a p l l s w ea i s of i n da n e r r o ra b o u tt h el o w e ro r i e n t a b l es t r o n gd i a m e t e ro fc o m p l e t eb i p a r t i t eg r a p h t l g i v e ni n 【3 6 】，a n dg i v ear i g o r o u sp r o o fo far e v i s e dc o n c l u s i o na b o u ts d i 口7 n ( ，n ) 3 w es h o wt h a te a c hc o m p l e t e 缸p a r t i t eg r a p hh a sa no p t i m a ls t r o n g ( k ，d ) 一 o r i e n t a t i o n i na d d i t i o n ，、ep r e s e n ts o m ep r o b l e i i 】旧a n dc o n j e c t u r e st ob ec o n s i d e r e di n f l l t u r er e s e a r c h k e y w o r d s ：c o n n e c t i 、，i t y ；w i r e l e s ss e n s o rn e t w o r k ；e n e r g ye 伍c i e n c y ；n p c o m p l e t e ； c o m p l e t e 七一p a r t i t eg r a p h ；s t r o n gd i s t a n c e ；l o 、e ra n du p p e ro r i e n t a b l es t r o n gr a d i u sa n ds t r o n gd i a m e t e r ；o p t i m a ls t r o n g ( 尤，d ) 一o r i e n t a t i o n x c o n n e c t i x i t 6 ，f o r t eo r i e n t a t i o nd e sg r a p h e se t r 6 s e a u xd ec a p t e u r ss a n sf i l r 6 s u m 6 l at h 6 0 r i ed e sg r a p h e se s tu n ed o m a i n eb i e nc o 皿u ed e sm a t h 6 m a t i q u e sd i s c r 色 t 6 ，a n t1 1 0 ns e u l e i i l 吼td ei l o i n b r e u xd 6 v e l o p p e n l e i l t st h 6 0 r i q u e s ，m a i sa u s s id i u n 伊 m l n a t t e sa p p l i c a t i o n sad e sp r o b l 6 m e sp r a t i q u e st e l sq u ei ac h i m i e ，l ab i o l o g i e ， l ：i n f o r m a t i q u ee tl e sr b e a u xd ec o m m u n i c a t i o n c e t t et h 资e6 t u d i ep r i n c i p a l e m e n t q 1 1 e l q u e sp a r a m a t r e s n o t r et r a v a i ls ed 6 c o m p o s ee n7c h a p i t r e 8 u n ei n t r o d u c t i o n b r 6 v e ，m a i sr e l a t i v e m e n tc o m p l 爸t ee s td o n n 6 ee nc h a p i t r e1 u nr 白e a ud ec a p t e u r ss a n sf i l ( w s n ) e s tu n er 6 s e a uc o m p r e n a n tu ng r a n d i l o i i l b r ed ec a p t e u r sd i s t r i b u 6 sa uh a s a r d c e sr 6 s e a u xs o n tu 乞i l i s 6 sd a n sd en o i i 卜 b r e u xd o m a i n e s l e sc a r a c t 6 r i s t i q u e sd u nr 6 s e a ud ec a p t e u r ss a n s 矗ls o n td e sr e s s o u r c e s1 i m i t 6 e s ， d e sr 6 s c a u xg r a n d se td e n s e s e n9 6 n 6 r a l c ，p h l sd en o e u d ss o n td 6 p l o y 6 sq l l e c e u xq u is o n tn 6 c e s s a i r e s ( p a rr a p p o r t 赢l u t i l i s a t i o no p t i m a l e ) p o u re h e c t u e ru n e t a c h ep r o p o s e d a n sl eb u td ec o m p e n s e rl a b s e n c ed ep o s i t i o n n e m e n te x a c te t d a i l l 6 l i o r cl at o l 6 r a i l c ef a u s s 6 e l at a i l l cd u nr 6 s e a ud ec a p t e u _ r ss a i l sf i lp c u t a t t e i n d r ed e sc e n t a i n e s v o i r ed e sm i l l i e r sd en o e u d s d a n sl ed o m a i n ed e sr 6 s e a u xd ec a p t e u r ss a n sf i l ，u nd e sp r i n c i p a u xe i l j e u xe s t d cs a v o i rc o n l m e n td ep r o l o n g e rl ad u r 6 ed e 讥cg l o b a l ed ur 6 s e a ut o u te nu t i l i s a n t u n ef a i b l e n e r g i e u n es o l u t i o n6 v i d e n t ep o u rr 6 9 l e rl ep r o b l 爸m e 白e r 9 6 t i q u er e p o s e s u rl e 伍c a c ed eg e s t i o nd el 6 n e r 百e 。p l a 血f i a 腻d e sn c i e u d se nm o d ea c t i fe te nm o d e