（运筹学与控制论专业论文）信息系统中的组合优化问题研究.pdf

信息系统中的组合优化问题研究 孔淑兰 ( 山东大学数学与系统科学学院，济南，2 5 0 1 0 0 ) 中文摘要 在实际应用领域产生的许多组合优化问题，如工件的排序加工问题、旅行 售货员问题、装箱问题和频道分配问题都是n p 困难问题对于这类问题， 从数学的角度出发，需要考虑问题的模型，求解此问题在p 尸的假设 被人们广泛地认可下。在多项式时间内寻找此类问题的精确解是不可行的。 因此设计这类问题的近似算法，已成为计算机科学和数学中学术探讨的一个 无法抗拒的主题 本文研究了从实际应用中产生的两个组合优化问题；带频道负荷的频道 分配问题和带拒绝的装箱问题 首先研究了带频道负荷约束的私人移动通信的频道分配问题它产生 于频道分配问题，源于无线电通讯网络的不同类型中近几十年来，新型的无 线电服务( 如数字电缆电话网络) 的发展导致了通讯中最重要的资源一频道在 无线电光谱中的贫乏，正像所有紧缺的可用资源一样，频道利用的费用增加提 出了如何合理地、经济地利用可用频道的问题在同一个无线电网络中频道 的再利用可以节约相当的资源和经济费用为此产生了新型的频道分配问题- 带频道负荷约束的频道分配问题 目前文献中关于带有频道负荷约束的频道分配问题研究的理论结果还未 曾出现过，s h u r l e y 和r m w h i t a k e r 在1 1 】中将频道负荷约束划归为非二元 约束，讨论了在每个发射台t 满足频道负荷的情况下，网络所用频道的频道 跨度最小问题并应用现代优化方法之一一禁忌搜索算法得到了实际生活中 几个无线电网络实例的最好廨而对于这类含非二元约束的问题，在此之前未 曾以数学的严谨语言描述过本文考虑了频道负荷约束下网络所需最少频道 数的频道分配问题 假设私人移动通讯服务网络中的发射台为岛，我们给出频道的负荷条件， 并且表示为一个参数对( d ，m ) ，其中d 是给定的距离。m 表示频道所服务的 山东大学博士学位论文 移动客户的容量对每个发射台t ：与t ，距离小于等于d ( 包括t ，) 且用同一个 频道，的发射台所服务的移动客户的总量为l o a d ( t t ) ，这称为发射台如的频道 负荷若频道负荷小于等于m ，则发射台t 。的频道负荷被满足；否则，发射 台“的频道超负荷所求的目标是在每个发射台t ：满足频道负荷的情况下， 网络所用的频道数目最少 这一问题可以描述为一个组合优化问题。本文从不同的角度讨论了此问 题的图模型和数学规划模型对其图模型作了理论方面的探讨；并以其数学 规划模型为基础，设计了求解特殊网络的最优解的多项式时间算法其中主 要工作如下r 第二章讨论了一般网络的带频道负荷约束的频道分配问题 第一节首先从频道分配问题的研究背景和发展现状出发，引入了带频道 负荷约束的频道分配问题 第二节给出了此间题的图表示，定义了限制图的k m 限制多重染色，将 所讨论的问题转化为限制图的m 限制多重色数问题，并应用序列算法得到m 限制多重色数的上界和下界及特殊图上的m 限制多重色数当其中的参数取 不同的特殊值时，此限制多重染色分别是对应的顶点染色和多匿顶点染色 因此，此染色是顶点染色和多重顶点染色的推广 第三节给出此问题的整数规划模型，定义丁一个特殊的最优解一札- 定向最 优解此概念的出现为有效地设计算法提供了重要途径 第四节提出了求解树图最优解的一个精确算法，它可以在多项式时间内 完成第一部分给出了树的结构分解，将树分解为以树的顶点t 1 分别为树根 和树叶的两棵子树u 根树和t 叶树第二部分讨论了星上的札一定向最优解 的性质，以此为依据设计了求其札定向最优解的精确算法第三部分在树的 分解和星的札- 定向最优解的精确算法基础上，利用动态规划思想。从树的最 底层叶子开始，依次向上一层构造子树的伽定向最优解整个过程所用的时 间是以顶点数的多项式为界第四部分以星的小定向最优解为基础，利用固 定优先选择的分配方法得到了一般树图的一个多项式时间的精确算法 本章的主要定理有： 定理2 2 5 设g 。= ( v e ，w ) 是限制图，e 是g 。= g 。( 几) 的最大权团， 根据f i r s t f i t 原则，对g 。的任意顺序的顶点集进行m 限制多重染色，则有 k ( n ) f 兰型1 ， 一 t ，0 v , e v ( c ) i i 山东大学博士学位论文 其中w ( 0 i ) 是e 的顶点他的权，k ( 扎) 为所用颜色数 定理2 2 7 设顶点的顺序为 1 ，? j 2 ，7 2 n ，k m ( n ) 是输入图g 。在序列算 法下，根据f i , s t f i t 原则得到的颜色数，则有下列不等式成立： 定理2 2 9 设g 。= ( v e w ) 为限制图，则2 ( g 。) = l 的充要条件为 m a x f 型1 _ 1 “( 口o 。：不】m 定理2 2 1 0 设限制图g ，。= ( v e ，w ) 的基础图是一颗星，u 为中心， u l ，u 2 ，一， 为叶子。训) = 1 1 l a x ( 训( 2 h ) ，t u ( u 2 ) ，一， ( u k ) ，则 【掣j4 - 掣1 2 ( c m ) 掣掣 _ 定理2 2 1 l 设限制图g 。= ( ve ，w ) 的基础图是偶圈，其长度大于等 于3 ，顶点 - ，u 2 ，口2 。按顺时针顺序排列，则可以在多项式时间o ( i v l ) 内 最优地给g 。实行m 限制多重染色 推论2 2 s 7 0 ，7 1 若限制图g 。= ( ve ，w ) 的每个顶点矾的权w ( y i ) = 1 ，并且i l l 取值为1 ，则此图的7 叫哏制色数u ( g ) sx ( g 。) = xsa + 1 ，其 中u ( g ) 为g 。= ( ve ，w ) 的基础图的最大团的顶点数 推论2 2 1 5 【6 1 】设限制图g ，。= ( ve ，i , i ) 的基础图是偶圈，每个顶点“ 的权为训t ，若m 取值为1 ，则夏( g 。) = l l l a x ：( w i + w j ) ( ，”) e 推论2 2 1 0 7 1 】若限制图g 。= ( v e ，w ) 的每个顶点 u i 的权w ( v i ) = l ， 并且i n 取值为1 。且它的基础图为完全图，则此图的m 限制多重色数趸( g 。) = = a + 1 推论2 2 1 7 【7 1 设限制图g 。= e ，w ) 的基础图是一颗星，乱为中 心， l ，啦，v k 为叶子，若每个顶点饥的权w ( v ) = 1 ，并且i n 取值为1 ， 则此图的，1 i 限制色数趸( g 。) = = 2 推论2 4 2 若g 。是一颗星，s t a r ( u ) 算法可以找到规划问题的一个“ 定向最优解，并且此解可在时间o ( i v l ) 内找到 推论2 4 4 若g 。= ( ve ，w ) 是一棵毛毛虫树，且树的长度有限，则可 以在时间o ( 1 v 1 ) 内找到对应规划问题( 】p ) 的n 一定向最优解 i i i 掣 娜 鼢 一 山东大学博士学位论文 定理2 4 5 若g 。= ( k e ，w ) 是一棵树，t ( g 。) 算法找到了g 。对应规 划问题( i p ) 的一个最优解，并且此算法可以在时问o ( i y i 2 ) 内运行 其次，我们讨论了互联网信息组织和规划中的带拒绝装箱问题设有长 为c 的一维箱子，给定物品集u = “l ，“2 ，u 。) ，每个物品的长为 w 。( o ，d i f - f e r e n tt y p e so fw i r e l e s sc o m m u n i c a t i o nn e t w o r k s i nt h el a s t d e c a d e ，t h er a p i d d e v e l o p m e n to fn e w w i r e l e s ss e r v i c e sl i k ed i g i t a lc e t m a rp h o n en e t w o r k sr e s u l t e d i nar u no u to ft h em o s ti m p o r t a n tr e s o u r c e - f r e q u e n c i e si nt h er a d i os p e c t r u m l i k ea l ls c a r c e l ya v a i l a b l er e s o u r c e s ，t h ec o s to fd m n n e l - u s ep r o v i d e st h en e e df o r e ( o n o m i cu s eo ft h ea v a i l a b l ef r e q u e n c i e s r e u s eo f f r e q u e n c i e sw i t h i na w i r e l e s s c o l n m u n i c a t i o nn e t w o r kc a no f f e rc o n s i d e r a b l ee c o n o m i e s s ot h en e wt y p eo f c h a n n e la s s i g n m e n tp r o b l e m s - c h a n n e la s s i g n m e n tp r o b l e mw i t hc h a n n e ll o a d i n g c o n s t r a i n t si sp r o p o s e d v i 山东大学博士学位论文 c u r r e n t l yt h er e a l i g n m e n to fp r i v a t em o b i l er a d i on e t w o r k ss e r v i c e sh a sf o - c u s e da t t e n t i o no nt h e s ei m p o r t a n tc o n s t r a i n t s h o w e v e r ，t h e yh a v en o tb e e n c o n s i d e r e de x p l i c i t l yi nt h ep o i n to ft h e o r yi nt h ea c a d e m i cl i t e r a t u r e c h a n n e ll o a d i n gc o n s t r a i n t sa r ec l a s s i f i e da sn o n - b i n a r yc o n s t r a i n t sb ys 。h u r l e ya n d r m w h i t a k e ri nh t e r a t u r e 1 t h e yf o c u s0 1 2t h ea s p e c t so fa l g o r i t h m sf o rc h a n - n e ll o a d i n g ，t a b us e a r c ht e c h n i q u ei sd e v e l o p e da n dt h et e c h n i q u ei sc a p a b l eo f h a n d i n gi n s t a n c e so fg r e a tp r a c t i c a lr e l e v a n c ef o ro b t a i n i n gt h em i n i m u ms p a n v e r yf e wt h e o r e t i c a ls t u d i e so nn o n b i n a r yc o n s t r a i n t sa n dt h e i ra p p l i c a t i o nt o c h a n n e la s s i g n m e n tp r o b l e l n sh a v ea p p e a r e di nl i t e r a t u r e 。t h ec h a n n e la s s i g n - m e n tp r o b l e mw i t hc h a n n e ll o a d i n gc o n s t r a i n t sa n dt h eo b j e c t i v ef m m t i o no ft h e m i n i m u ms p a ni sd i s c u s s e d c h a n n e ll o a d i n gc o n d i t i o n sa r ei m p o s e do ne a c ht r a n s m i t t e r ，a n da r ef o r - m u l a t e df o rap a r a m e t e rp a i r ( d ，m ) ，w h e r edi sad i s t a n c ei nk i l o m e t r e sm i d mi n d i c a t e st h en u m b e ro fm o b i l e su s i n gac o m m o nc h a n n e l f o re a c ht i t h e t r a n s m i t t e r sw i t h i ndk mo ft i ( i n c l u s i v eo f 氐) w h i c ha r eo p e r a t i n go nc h a n n e l 五 w i l ls e r v eat o t a lo fl o a d t lm o b i l e s t h i si sc a l l e dt h ec h a n n e ll o a n i n ga tt i i f l o a d ( t t ) sm t h e nt h ec h a n n e ll o a d i n ga tt r a n s m i t t e rt ii ss a t i s f a c t o r y o t h e r w i s e t r a n s m i t t e rt 。i sd e e m e do v e r l o a d e db yl o a d t i mm o b i l e s o u ro b j e c t i v ei st o m i n i m i z et h et o t 8 ln u m b e ro fc h m m e hu s e di nt h en e t w o r kw h e na l ic h a n n e l so f t r a n s m i t t e rs a t i s f yt h ec h a n n e ll o a d i n g t h ec h a n n e la s s i g n m e n tp r o b l e mw i t hc h a n n e ll o a d i n gi sf o r m u l a t e da sa c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m t h eg r a p hm o d e l sa n dm a t h e m a t i c a lp r o - g r a m m i n gm o d e h a r ea d d r e s s e di nt h ep a p e r a n ds o m et h e o r e t i c a lc o n c l u s i o n s a r eo b t a i n e d a tt h es a m et i m ee x a c ta l g o r i t h m s8 r ed e s i g n e df o rs o m es p e c i a l n e t w o r k s i nc h a p t e r 2 ，w ed i s c u s st h ec h a n n e la s s i g n m e n tp r o b l e m w i t hc h a n n e ll o a d i n g w ei n t r o d u c et h ep r o b l e m f r o mt h e b a c k g r o u n da n dd e v e l o p m e n to fc h a n n e l a s s i g n m e n tp r o b l e m si nt h ef i r s ts e c t i o n i nt h es e c o n ds e c t i o na n dt h et h i r ds e c t i o n ，g r a p hf o r m u l a t i o n so ft h ep r o b - l e m a r ep r e s e n t e da n d 一m r e s t r i c t e dm u l t i c o l o r i n go ft h er e s t r i c t e dg r a p hg m i sd e f i n e d s ot h ep r o b l e mi sc h a n g e di n t ok mr e s t r i c t e dm u l t i c o l o r i n gp r o b - l e m t h es e q u e n t i a la l g o r i t h mi sa p p l i e dt ok mr e s t r i c t e dm u l t i c o l o r i n ga n d 山东大学博士学位论文 t h eu p p e ra n dl o w e rb o u n d so ft h em r e s t r i c t e dm u l t i c h r o m a t i cn u m b e r 戈( g 二) a r eo b t a i n e d f o rs o m es p e c i a lr e s t r i c t e dg r a p hg m ，更( g m ) c a nb eo b t a i n e di n t i m eo ( i v l ) i nf a c t ，k mr e s t r i c t e d m u l t i c o l o r i n gi sg e n e r a l i z e db yv e r t i c e s c o l o r i n ga n dm u t i c o l o r i n g ，a n di th a sc h a r a c t e r ss i m i l a rt ov e r t e xc o l o r i n ga n d m u t i c o l o r i n g i nt h et h i r d s e c t i o n ，i n t e g e rp r o g r a m m i n gf o r m u l a t i o no ft h ep r o b l e mi s p r e s e n t e da n d t h ec o n c e p to fu o r i e n t e do p t i m a ls o l u t i o ni sd e f i n e d t h eo p t i m a l s o l u t i o ni sq u i t ei m p o r t a n tf o rt h ed e s i g na n d a n a l y s i so f t h ep r o p o s e da l g o r i t h m a n di n1 t h ef o u r t hs e c t i o n ，a l le x a c ta l g o r i t h mi sf o u n df o rt r e e s t h ee x a c t a l g o r i t h mo ff i n d i n gt h eu o r i e n t e do p t i m a ls o l u t i o nf o rs t a r si sg a i n e di nt h es e c o n ds u b s e c t i o n o nt h eb a s eo ft h eu o r i e n t e do p t i m a ls o l u t i o nf o rs t a r s ，a ne x a c t a l g o r i t h mf o rc a t e r p i l l l a rt r e e si sf o u n db ya p p l y i n gt h ed y n a m i cp r o g r a m m i n g a l g o r i t h mi nt h et h i r ds u b s e c t i o n a ne x a c ta l g o r i t h mf o rt r e e si sf o u n db ya p p l y - i n gf i x e dp r e f e r e n c ea l l o c a t i o no fas u b g r a p hi nt h eg r a p hi nl a s ts u b s e c t i o n t h e a l g o r i t h mi si m p l e m e n t e di nt i m eo ( i v l 2 ) ( w h e nt h el e n g t ho ft r e ei sb o u n d e d ) t h em a i nc o n c l u s i o n si nt h ec h a p t e ra r ep r e s e n t e da sf o l l o w s ： t h e o r e m2 2 5 ：l e tg m = ( k e ，w ) b ear e s t r i c t e dg r a p ha n dcb e t h el a r g e s t w e i g h tc l i q u eo fg m l e tk m ) b et h en u m b e ro fc o l o r su s e db y t h es e q u e n t i a lc o l o r i n ga l g o r i t h mw h e na p p l i e dt og r a p hg mw h o s ev e r t i c e sa r e c o n s i d e r e di nt h eo r d e r ( v l ，u 2 ，v n ) a c c o r d i n gt of i r s tf i tr u l e ，t h e nw eh a v e 2 f 掣 ， w h e r ew ( v i ) i sd e n o t e dt h ew e i g h to ft h el a r g e s tc l i q u ec t h e o r e m 2 2 7l e tk ( 仡) b et h en u m b e ro fc o l o r su s e db yt h es e q u e n t i a l c o l o r i n ga l g o r i t h mw h e na p p l i e dt og r a p hg m w h o s ev e r t i c e sa r ec o n s i d e r e di nt h e o r d e r ( i y l ，v 2 ，一，) a c c o r d i n gt of i r s tf i tr u l e t h e n ，t h ef o l l o w i n gi n e q u a l i t y h o l d s 晰拯 删m a 刚x 乙赢，掣1 - t h e o r e m2 2 9l e tg m = ( v e ，w ) b e ar e s t r i c t e dg r a p h ，t h e n 删m a x r 。赢。掣1 - l t h e o r e m2 2 1 0l e tg m = ( v e ，w ) b e as t a rw i t hr o o tn o d eua n dl e a v e s 山东大学博士学位论文 v = ( 让， 1 ，v 2 ，) ，w ( p ) = n l a x ( 仉) ，u ，( u 2 ) ，- 一， ( 巩) ) ，t h e n 【等+ 掣1 兰耶。) sf - ”g h - 、1 + 掣1 t h e o r e m 2 2 1 ll e tg 。= ( v e ，w ) b eac y c l eo fe v e nl e n g t h2 n 3 t h e ng mc a nb e o p t i m a l l ym r e s t r i c t e dm u l t i e o l o r i n gw i t h 戈( g m ) c o l o r s f u r t h e r ， t h em u l i t c o l o r i n gc a nb eo b t a i n e di ut i m eo ( i v l ) c o r o l l a r y2 2 8 7 0 ，7 1 】l e tg m = ( ve ，w ) b e ar e s t r i c t e dg r a p hw i t h t h ew e i g h tio fe a c hv e r t e xa n dm = l ，t h e n u ( g ) 2 ( a m ) = x a + 1 ，w h e r e u ( g ) i st h en u m b e r o ft h ev e r t i c e so ft h el a r g e s tc l i q u ei ng m c o r o l l a r y2 2 1 5 1 6 1 】l e tg 。= e ，w ) b eac y c l eo fe v e nl e n g t h 2 n 3a n dm = 1 ， i sd e n o t e dt h ew e i g h to fv e r t e x 仇t h e n2 ( c m ) = m a x ( 铷t + 钍。) a n d g m e a nb eo p t i m a l l ymr e s t r i c t e dm u l t i c o l o r i n gw i t h ( ，q ) e 2 ( g 。) c o l o r s f u r t h e r ，t h em u l i t c o l o r i n gc a nb eo b t a i n e di nt i m eo ( i v l ) c o r o l l a r y2 2 1 6 【7 1 】l e tg 。= ( ue ，w ) b ear e s t r i c t e dg r a p hw i t ht h e w e i g h tlo fe a c hv e r t e xa n dm = 1 ，a n dt h eb a s i cg r a p ho fi ti sc o m p l e t eg r a p h t h e n 元( g 。，) = ) ( = a + 1 c o r o l l a r y2 2 1 7 7 1 l e tg 。= ( ue ，w ) b eas t a rw i t hr o o tn o d eu a n dl e a v e s v = 札， 1 ，1 2 2 ，一一， s u p p o s et h a tw ( v i ) = 1a n dm = 1 t h e n 鼋( g 。) = x ；2 c o r o l l a r y2 4 2 l e tg 。= ( k e ，w ) b e as t a r ，s t a r ( u ) a l g o r i t h mc a nf i n d l 一o r i e n t e do p t i m a ls o l u t i o ni nt i m eo ( i v l ) c o r o l l a r y 2 4 4l e tg m = ( k e ，w ) b e a c a t e r p i l l a rt r e ea n dt h el e n g t ho f i ti sd o u n d e d ，t h e n “o r i e n t e do p t i m a ls o l u t i o no fi tc a nb ef o u n di nt i m e o ( i v l ) t h e o r e m2 4 5l e tg m = ( v e ，w ) b eat r e ea n dt h el e n g t ho fi t i s b o u n d e d ，t h e n8 _ 1 1o p t i m a ls o l u t i o no fi tc a nb ef o u n di nt i m eo ( i v l 2 1 s e c o n d l y , b i np a c k i n gp r o b l e mw i t hr e j e c t i o n ，w h i c ha r i s ef r o mt h eo r g a - n i z a t i o na n dp l a n n i n go fi n t e r n e tc o m m u n i c a t i o ni sd i s c u s s e di nt h es e c o n d p a r t ， t h ep r o b l e mi sf o r m u l a t e da sf o l l o w s ： a s s u m i n gs o m eo n e - d i m e n s i o n a lb i n sw i t ht h el e n g t ho fca n dt h es e tu = 7 2 1 ，札2 ，仳n ) o f t h ei t e m sa r eg i v e n ，t h el e n g t ho f 乱ii sw d 0 ：p i 的两总和达到最小这个问题最早由b a r t a l 4 等人提出并给出此问题 i r 的离线与在线算法的研究h e 和m i l l 将其推广到同类并行处理器上的排序 3 山东大学博士学位论文 问题，对在线算法的设计进行了研究而后，e p s t e i n 5 】和s g a n 6 讨论了该 问题的离线算法 装箱问题是最经典的组合优化问题之一它作为一种最早研究的 v p 难 解问题和复杂性理论的研究平台，为其它n p 困难问题的研究提供了诸多借 鉴。本文正是以装箱问题的研究为基础，将其著名算法应用到带拒绝的装箱问 题上。提出相应的有效近似算法并分析算法的性能，确定算法的性能界限其 主要工作如下： 在研究已经提出的带拒绝的装箱问题的一个2 近似算法的基础上，从另 一个角度，利用线性规划和对偶规划的原始对偶互补松弛条件得到这个问题 的一个下界并在此基础上较简单清晰地描述了与此下界对应的被装箱物 品和被拒绝物品的性质，为一系列近似算法的设计提供了理论依据同时将 已有的2 近似算法进行了修改和改善 对应于装箱问题的著名算法：下次适应算法，首次适应算法和降序首次适 应算法，分别设计了带拒绝的装箱问题的两个近似算法：r n f 算法和r d f f 算法它们分别为2 近似算法和渐进兰一近似算法 评价问题的近似算法性能的标准有时间和空间复杂度，最坏情况性能比 和平均性能比本文针对每个算法分析其时间和空间复杂性，最坏情况性能 比 1 3本文内容组织方式 本文在内容安排上将每个问题的研究工作放在一章里讨论，全文共分四 囊 第一章简要地介绍了本文研究的问题和研究的主要内容 第二章讨论了带频道负荷约束的频道分配问题 第一节首先从频道分配问题的研究背景和发展现状出发，引入了带频道 负荷约束的频道分配问题 第二节给出了此问题的图表示定义了新概念一限制图和k m 限制多 重染色；应用序列算法得到一般图的m 限制多重色数的上界和下界及一些推 论 第三节讨论了此问题的数学规划模型第一部分给出了它的整数规划表 示，第二部分描述了一个特殊的最优解一“定向最优解 4 山东大学博士学位论文 第四节设计了树网络图的一个精确算法第一部分给出了树的结构分解， 将树分解为以树的顶点u 分别为树根和树叶的两棵子树钍一根树和u 一叶树 第二部分设计了求星的u 一定向最优解的精确算法第三部分利用动态规划思 想给出了子树网络图的钍定向最优解的精确算法第四部分利用固定优先选 择的分配思想，得到了求解一般树的最优解的多项式时间算法 第三章研究了带拒绝的装箱问题 第一节首先给出了此问题的研究背景和一些相关定义 第二节在带拒绝装箱问题的整数规划表示的基础上给出了其变量放松对 应的线性规划及其对偶规划，通过它们的原始对偶互补松弛条件得到了原问 题的一个下界和与此下界对应的物品的性质 第三节至第五节分别设计了所讨论问题的三个近似算法 本文的第四章对全文所傲的工作进行了总结，并提出了有待于进一步研 究的问题 5 第二章带频道负荷约束的频道分配问题 目前由于无线电网络中发射台需求量的迅速增长，使得合理地、经济地利 用紧缺资源频遭成为频道分配问题的首要课题频道资源的贫乏表明：在完 全摆脱其他用户带来的潜在干扰的情况下，用户必定要用相同的频道本章考 虑在增加频道负荷约束的限制下，网络所需的最少频道数目的频道分配问题 2 1研究背景 2 1 1 频道分配问题 频道分配是无线电网络设计的重要问题之一频道分配这一术语已经广 泛地用于描述许多不同类型的问题，这些问题通常具有不同的模型需求和目 标函数，它们主要包括； l 对固定无线电光谱的分配、许可和基于所有无线电光谱最大利用的原 则，设计模型【7 】； 2 对给定分配的网络方案建构模型，包括航空无线电移动通讯、陆地移 动通讯、水下移动通讯、广播、陆地固定通讯和卫星通讯等闲络； 3 在已建成的网络中，对用户动态地分配频道以设计在线算法 其中，研究工作者最感兴趣的是陆地无线电移动系统，同时对此已作了大 量的研究工作。 上述的所有闻题都有一个共性，也就是将有限的无线电光谱资源最优地 分配给正在迅速增长的大数量的无线电用户同时，对每个用户雨言，所需增 加的光谱总量实际上就变成了正在增长地密集的信息量 总之，频道分配问题是一个组合优化问题，它涉及的是在满足一定约束的 条件下，将无线电频道分配到发射台集合传统上，频道分配所满足的约束是 使整个分配网络所受到的干扰最小频道分配问题有两个基本方面： 1 所有发射台分配到的频道必须是可行的，并且，频道应该在每个发射 台给定的不同频道集内选取 2 如果分配到两个发射白的频道产生了干扰。那么干扰就导致了传送的 信号性能损失当相同的或者相近的可分离无线电频道同时分配给邻近的地 理区域时，干扰产生这样的发射台送出的接受信号变弱，使所需要的信息和 不需要的信息几乎不能区别开 6 山东大学博士学位论文 人们对频遭分配问题进行了大量的研究工作，基于研究者的研究目的和 应用，广泛地提出了频道分配问题的不同模型和求解这些模型的技巧而这 些模型和求解技巧的提出主要因为频道分配问题属于n p 难解问题8 9 1 由于发射台所需的频道随时间的变化而改变，在发射台实际需求的基础上， 我们将大量文献中处理频道分配问题所提出的方法分为三类；固定频道分配 ( f c a ) ，动态频道分配( d c a ) 和混合频道分配( h c a ) 混合频道分配是把固 定频道分配( f c a ) 和动态频道分配( d c a ) 两种方案合并在一起后得到了网 络一个较好的整体性能f 1 0 1 给出了h c a 方案的一个例子，他们在文中把神 经网络和遗传算法描述为借频道的分配问题。 1 1 】给出了d c a 方案的一个例 子，他们在文中讨论了一个固定优先选择的分配方案。【1 2 】证明了在网络的 通信量较轻和通信量不均匀的情况下，动态频道分配方案好于固定频道分配 方案然而，在通信量较重和通信量均匀的情况下，固定频道分配方案超过了 动态频道分配方案除此之外。固定频道分配给出了动态频道分配方案性能的 一个界为此，人们研究频道分配问题的重心大都放在固定频道分配方案这 一方面 2 1 2 带频道负荷约束的频道分配问题的提出 在一个固定频道分配方案中，网络所期望的通信负荷变成了人们必须分 配到每个发射台上的固定数目的频道数，称之为发射台的需求这些需求规定 了每两个发射台之间所需的频道分离必须满足的最小值传统上，它们可以用 一个约束图表示设图g = ( ve ) ，每条边带有非负标号，网络的发射台用 图的顶点表示，如果分配到两发射台t 。t ，的频道要求超过西频道分离，则在 发射台t 。，t 。对应的两顶点之间连边且在边上标号砂这样产生的图称为约束 图 求解固定频道分配问题的途径可以分成俩大主流，第一，要求分配到顶点 的频道对应的解产生的总惩罚值最小；第二，要求这个解产生的最大总惩罚值 最小根据这两大主流，文献讨论的模型因发射台满足的约束类型和需要优 化的目标不同而不同为此，【1 3 列举了解f c a 问题的四种模型，对每个模 型，分别给出了对应的数学规划表达式 ( 1 ) 最小序频道分配问题( m o f a p ) ； ( 2 ) 最小跨度频道分配问题( m s f a p ) ； ( 3 ) 最小干扰频道分配问题( m i - f a p ) ； 7 山东大学博士学位论文 ( 4 ) 最小阻塞频道分配问题( m b f a p ) ； 对于上述的模型，寻找它们的精确解方法已有了很大的进展。目前，通过 将下界技巧和启发式算法有机地结合在一起，最小序频道分配问题似乎可以 有效地找到最优解f 1 4 1 将整数规划和启发式算法结合在一起得到了对许多 实例有效的强壮算法；1 5 1 应用整数规划的技巧：分枝和割方法求解所要讨 论的实例，结果得到了所有例子的最优解f 1 6 ，1 7 ，1 8 ，1 9 】通过探测约束图的 团或其它子图，并且提取几个团或其它子图共有的信息的方式，改进了已有 的下界。对于最小跨度频道分配问题的下界的研究，文献 2 0 给出了m s f a p 的第一个非平凡的下界以后，只有很少的研究者较成功地找到了好于【2 0 】的 下界。其中， 2 1 】发展了g a m s t 的工作，f 2 2 】利用特征值与特征向量分析了 特殊实例的最小频道跨度，最好的是 2 3 ，2 4 】中的结论，从锥理论出发，分别 利用了f 1 9 ，2 5 、2 6 ，2 7 1 中提到的旅行售货员问题与此问题的关系而得到了一 个下界从精确解的观点看，m i f a p 好像是四个问题中最困难的一个， 1 5 尽管应用整数规划的分枝和割方法得到了m o f a p 的几乎最好的结果，但用 这个方法却不能较好地解m i f a p 中的任意一个例子，f 2 8 ，2 9 ，3 0 1 给出了两 个仅对少数例子有好结果的精确求解方法，可以说这两个方法只对局部的实 例有较好的结论。近些年来， 1 33 1 ，3 2 】利用部分约束适定性和树分解方法 有效地求解了此问题对于h i b f a p ，f 1 1 2 9 ，3 3 ，3 4 1 从此问题与最大独立集 的关系着手，应用整数规划和有效的搜索技巧成功地解决了一些生活中的实 例。 除了上述四种模型外，其它类型的模型在不同的文献中也不断出现其 中最引人瞩目的模型是把前面的四种模型中的有关性质合并在一起，从而考 虑用多目标模型刻画所需研究的问题。例如， 3 5 】和【3 6 】将模拟退火方法应 用到求解有干扰、阻塞和跨度组成的线性函数的最小费用问题；3 7 1 考虑了 由平均干扰和最大干扰的一个凸组合形成的函数的费用，所用的方法也是模 拟退火方法； 3 8 】讨论了最小序和最小跨度合并起来的目标；首先确定了问 题的最小序。在此基础上再确定了最小跨度另外，对最小跨度的频道分配问 题的一个变化形式，f 3 9 ，4 0 ，4 1 1 讨论了圈频道距离的频道分配问题，在此问 题中频道的分配被视为满足圈分离频道约束；对几类特殊图，f 4 1 1 证明了限 制到这些特殊图此问题在o ( f y n 时间内可解； 3 9 ，4 0 把此问题描述为圆染 色并得到关于无限可三角格图、无限方格图和无限线格图较好的理论结果 f 4 2 43 】讨论了选取基站的最优位置的数学模型。 4 4 ，4 5 ，4 6 分别讨论了具有 8 山东大学博士学位论文 大距离和大需求的频道分配问题的模型 目前由于无线电网络中发射台需求量的迅速增长，使得合理地、经济地利 用紧缺资源频道成为频道分配问题