（电路与系统专业论文）基于复杂网络的移动网话务量研究[电路与系统专业优秀论文].pdf

摘要 近年来，移动网络迅速发展，随之带来了拥塞、网络扩容等问题。其中，话 务量的研究重点之一就是移动终端用户的社会关系网络。在社会关系复杂网络研 究中，对复杂网络进行拓扑建模与拓扑优化，这两个方面无论理论上还是在实际 应用中都具有非常重要的意义。通过对复杂网络拓扑结构的研究，一方面我们可 以更好地了解和解释现实系统所呈现出来的种种网络特性：另一方面，我们可以 将研究复杂网络拓扑结构的成果运用到具体的实际问题中，如移动通信网络的话 务量研究。 论文基于复杂动态网络的相关理论，研究移动网络话务量问题。论文主要内 容分为两部分。第一部分是复杂网络拓扑模型的研究，首先分析复杂网络所表现 出来的一些共同特征，并对这些共性的形成原因进行分析，得出优先连接和动态 生长是复杂网络拓扑的主要共性。然后，对i n t e m e t 网络拓扑模型进行研究和分 析，提出基于消息传递的复杂网络改进拓扑模型，并将其应用于社会网络的建模。 最后，根据改进模型的迭代算法，实现一个拓扑生成软件。 第二部分是移动网络话务量研究。利用上述社会网路拓扑结构，与移动网络 的拓扑结构结合起来，根据运营商实际数据，建立移动通信网络的话务量模型， 得到每个时刻有多少移动终端用户试图拨出电话，有多少移动终端用户接n t 连 接请求，以及每个用户所在的基站位置等等。有了这些信息就可以用来评估移动 网络每个时刻的话务量压力，以及产生拥塞和无效数据的可能性。 论文通过基于消息传递的拓扑模型，建立社会网络的拓扑结构，再利用这个 拓扑结构和话务量的统计数据建立了话务量模型。最终得到某个时刻每个基站的 话务量情况。 关键词：复杂动态网络；拓扑建模；消息传递；移动网络；话务量 a b s t r a c t r e c e n t l y , b e c a u s e o ft h er a p i dd e v e l o p m e n to ft h em o b i l en e t w o r k s ，t h e c o n g e s t i o na n dn e t w o r ke x p a n s i o na p p e a r s t h ek e yp o i n to ft h e s e r v i c ep a y l o a d r e s e a r c hi st h es o c i e t yr e l a t i o n s h i pn e t w o r ko ft h em o b i l et e r m i n a l s i nt h er e s e a r c ho f c o m p l e xn e t w o r k so fs o c i e t yn e t w o r k s ，t h ek e yo fc o m p l e xn e t w o r k sa r et o p o l o g y m o d e l i n ga n dt o p o l o g yo p t i m i z a t i o n ，b o t ho ft h e mh a v ei m p o r t a n ts i g n i f i c a n c e i n t h e o r ya n da p p l i c a t i o n s i nt h er e s e a r c ho nc o m p l e xn e t w o r k s ，w ec a n u n d e r s t a n dt h e c h a r a c t e r i s t i c so ft h em a n yr e a ls y s t e m sa n dn e t w o r k s ，a n dc a na l s oa p p l yt h er e s e a r c h r e s u l t st om a n ys p e c i f i ca r e a s ，f o re x a m p l e ，t ot h es e r v i c ep a y l o a do ft h em o b i l e n e t w o r k s t h i sd i s s e r t a t i o na p p l i e st h e o r yo fc o m p l e xn e t w o r k st o t h es e r v i c ep a y l o a d r e s e a r c hi nm o b i l en e t w o r k s t h e r ea r et w om a i np a r t si nt h i sp a p e r t h ef i r s tp a r ti s t h er e s e a r c ho ft h et o p o l o g yo ft h ec o m p l e xn e t w o r k s t h ec o m m o n c h a r a c t e r i s t i c so f c o m p l e xn e t w o r k sa n di t sr e s u l t i n gr e a s o n sa r ef i r s t l ya n a l y z e d w ef i n d t h a tt h e p r e f e r e n t i a la t t a c h m e n ta n dd y n a m i cg r o w t ha r et h em a i nc o m m o n c h a r a c t e r i s t i c so f c o m p l e xn e t w o r k s t h e n ，w es t u d yt h ei n t e r a c tt o p o l o g ym o d e l ，p r o p o s ea m o d i f i e d i n t e m e tt o p o l o g ym o d e lb a s e do nt h em e s s a g et r a n s m i s s i o n ，a n dt h e na p p l y t h e m o d i f i e dm o d e lt ot h em o d e l i n go ft h es o c i e t yn e t w o r k s f i n a l l y , t h es o f t w a r e i s r e a l i z e df o r t h en e wm o d e l t h es e c o n dp a r ti st h er e s e a r c ho ft h es e r v i c ep a y l o a do ft h em o b i l en e t w o r k s b a s e do nt h ec o m b i n a t i o no ft h et o p o l o g yo ft h es o c i e t yn e t w o r k s a n dm o b i l e n e “r o r k s ，a n du s i n gt h er e a ld a t ao fs e r v i c ea g e n c y ，w eg e tt h ep o s s i b l e s e r v i c e p a y l o a do fm o b i l en e t w o r k s t h e nt h em o d e lo fs e r v i c ep a y l o a d o fm o b i l en e t w o r k si s b u i l tu p 。t h en u m b e ro fd i a l i n go u ta n di na te v e r ym o m e n t a n de v e r yb a s es t a t i o ni s h e l p f u lf o re v a l u a t i n gt h es e r v i c ep a y l o a d a n dc o n g e s t i o na te v e r ym o m e n t t h i sd i s s e r t a t i o na p p l i e st h et o p o l o g ym o d e lb a s e do nm e s s a g e t r a n s m l s s l o n st o t h em o d e l i n go fs o c i e t yn e t w o r k s w i t ht h et o p o l o g ya n dt h er e a ls t a t i s t i c d a t ao f s e n r i c ep a y l o a d ，t h em o d e lo fs e r v i c ep a y l o a di sb u i l tu p f i n a l l yt h es e r v i c ep a y l o a d a ta n ym o m e n to fe v e r yb a s es t a t i o nh a sb e e no b t a i n e d i i k e yw o r d s ：c o m p l e xd y n a m i c a ln e t w o r k ；t o p o l o g ym o d e l i n g ；m e s s a g et r a n s m i s s i o n ； m o b i l en e t w o r k s ；s e r v i c ep a y l o a d i i i 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名： f i 期：岖 期：of l 、1 飞 - 。- - 1 - - - _ 一 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：导师签名： 南京邮电大学硕士研究生学位论文 第一章绪论 1 1 研究背景 第一章绪论 移动通信是通信领域中最具活力、最具发展前途的通信方式，是当今信息社会中最具 个性化特征的通信手段。与传统静态的固定式通信相对应，移动通信最本质的特点是动态 的移动式通信，它在无线通信的基础上，引入了用户的移动性，即在无线通信的一重信道 动态的基础上加入了第二重用户动态性【1 1 。正是这种二重动态性，成为移动通信技术发展 的原动力，移动通信技术的发展也正是围绕着如何适应信道、用p _ - 重动态性来进行的【1 1 。 自2 0 世纪8 0 年代我国引入模拟移动通信网t a c s 以来，经过2 0 多年的发展，至2 0 0 5 年底我国移动用户总数已达3 7 亿，其中g s m 用户3 4 亿、c d m a 2 0 0 0 用户o 3 亿。我国 第一代移动通信t a c s 系统已完成其历史使命而被淘汰；我国第二代移动通信中的g s m 系统是全球规模最大、用户最多的系统，c d m a 系统也跻身世界前列：我国第三代移动通 信系统目前还处于投入运营准备阶段。 我国蜂窝式移动通信网络从其发展历程来看，大约每l o 年更新一代，目前正处于第 二代( 2 g ) 与第三代( 3 g ) 的交接时期。 第一代( 1 g ) 以模拟蜂窝网为主要特征，于2 0 世纪7 0 年代末开始商用，其中最具代表 性的是北美的a m p s 和欧洲的t a c s 两大系统。从1 g 技术上看，它以解决两个动态性中 最基本的用户动态性为核心，并适当考虑第二重信道动态性。1 g 采用f d m a 方式实现对 用户的动态寻址，并以蜂窝式网络结构和频率规划手段实现载频复用，达到扩大覆盖范围 和满足用户增长的需求【l 】。 第二代( 2 g ) 以数字化为主要特征，于2 0 世纪9 0 年代初正式商用，最具代表性的有欧 洲的g s m 、北美的i s 9 5 和日本的p d c 系统。从2 g 技术上看，它以数字化为基础，较全 面考虑了信道与用户的二重动态性及相应的匹配措施，采用t o m a ( g s m ) 和c d m a ( i s 一9 5 ) 方式实现对用户的动态寻址。 第三代( 3 g ) 以多媒体业务为主要特征，于本世纪初投入商业运营，最具代表性的有北 美的c d m a 2 0 0 0 、欧洲与日本的w c d m a 以及我国提出的t d s c d m a 三大系统。3 g 从 技术上看，在2 g 的信道与用户二重动态特性的基础上引入了业务动态性，即用户业务既 可以是单一的语音、数据、图像，也可以是多媒体业务，且用户可随机选择业务种类。所 以3 g 是在2 g 的数字化基础上，以多媒体化为主要目标，全面考虑并完善信道、用户二重 l 塑室墅皇奎! 塑主婴窒圭堂垡堡奎一 第一章绪论 动态性匹配，并适当考虑业务的动态性，尽力采用相应措施予以实现的技术。 随着g s m 移动通信技术在我国的普及，移动用户数得到了快速增长，也给g s m 网络 容量造成了空前的压力，网络的快速扩张同时也带来了投资与效益的压力，特别是在3 g 技术即将进入商用的阶段，对2 g 网络( g s m 网络) 的投入步入了进退两难的地步。在网络 容量压力与投资要求的情况下，g s m 无线网络的话务量规划己经从以往的粗放式经营进入 到精细化分析。 移动网络话务量的研究设计到移动网络和社会关系网络，社会关系网络则属于复杂网 络的一种。要研究移动网络话务量，社会关系复杂网络的研究至关重要。 自然界中存在的大量复杂系统都可以通过形形色色的网络加以描述【3 】【钔。一个典型的 网络是由许多节点与连接两个节点的一些边组成的，其中节点用来代表真实系统中不同的 个体，而边则用来表示个体间的关系，往往是两个节点之间具有某种特定的关系则连一条 边，反之则不连边，有边相连的两个节点被看作是相邻的。例如，神经系统可以看作大量 神经细胞通过神经纤维相互连接形成的网络；计算机网络可以看作是自主工作的计算机通 过通信介质如光缆、双绞线、同轴电缆等相互连接形成的网络。类似的还有电力网络、社 会关系网络、食物链网络等等。 数学家和物理学家在考虑网络的时候，往往只关心节点之间有没有边相连，至于节点 到底在什么位置，边是长还是短，是弯曲还是平直，有没有相交等等都是他们不在意的。 在这里，我们把网络不依赖于节点的具体位置和边的具体形态就能表现出来的性质叫做网 络的拓扑性质，相应的结构叫做网络的拓扑结构。那么，什么样的拓扑结构比较适合用来 描述真实的系统呢? 两百多年来，对这个问题的研究经历了三个阶段。在最初的一百多年里， 科学家们认为真实系统各因素之间的关系可以用一些规则的结构表示，例如二维平面上的 欧拉格子，它看起来像是格子体恤衫上的花纹；又如最近邻环网，它会让你想到一群人手 牵着手围着簧火跳圆圈舞。到了十九世纪五十年代末，数学家们想出了一种新的构造网络 的方法，在这种方法下，两个节点之间连边与否不再是确定的事情，而是根据一个概率决 定。数学家把这样生成的网络叫做随机网络，它在接下来的四十年里一直被认为是描述真 实系统最好的网络。直到最近几年，由于计算机数据处理和计算能力的飞速发展，科学家 们发现大量的真实网络既不是规则网络，也不是随机网络，而是具有与前两者皆不同的统 计特征的网络。这样的一些网络被科学家们叫做复杂网络，对于他们的研究标志着网络研 究第三阶段的到来。 如果用节点代表某个系统的个体，用节点间的连接表示系统中个体的关系，就可以得 到一个网络。系统所表现的网络形式在现实世界中随处可见。例如，i n t e m e t 的拓扑结构， 2 南京邮电火学硕士研究生学位论文第一章绪论 w o r l dw i d ew e b 、社会关系网络、神经网络和食物链网络等等。目前的研究发现大量自然 系统及人工系统背后都隐藏着一个复杂网络拓扑结构。从细菌、细胞和蛋白质系统，到科 学家之间的合作，论文之间的引用关系，大型的i n t e m e t 和w w w 网络等，它们都构成某 种网络系统，也构成某种复杂网络系统。因此，如果发现一种概括它们共同特性的观点和 方法，则能抓取这类网络的关键，形成深入的认识。目前的复杂网络的研究在这点上发现 了它们同时都具有的3 个主要特征小世界、无标度性和高聚集度。 1 9 9 8 年w a t t s 和s t r o g a t z 提出小世界网络模型( s m a l lw b r l d ，s w ) 模型【4 】。他们通过以某 个很小的概率改变规则网络中边的连接方式构造出了一种介于规则网络和随机网络之间 的网络，它同时具有大的簇系数( 用来描述网络聚集成团的情况) 和小的平均距离( 用来描述 节点间距离的平均情况) ，因此它既不能当作规则网络处理，也不能被看作是随机网络。后 来就把大的簇系数和小的平均距离两个统计特征合在一起称为小世界效应，将具有这种效 应的网络称为小世界网络。 图1 1 是小世界网络的结构示意图，左边的网络是规则网络，右边的网络是完全随机 网络，中间的网络是在规则网络上增加随机的因素而形成的小世界网络，它同时具有大的 簇系数和小的平均距离。 图1 1 小世界网络的结构示意图 人们对大量的真实网络，比如电力网络、计算机互联网、食物链网络、演员关系网、 科学家合作网络等等做了大量实证性的研究后，发现它们几乎都是小世界网络，同时，他 们还发现了真实网络的另一重要统计特征，即节点度服从幂律分布( p o w e rl a w ) 。节点度是 指一个节点拥有相邻节点的数目，节点度服从幂律分布就是说具有某个特定度的节点数目 与这个特定的度之间的关系可以用一个幂函数近似地表示。幂函数曲线是一条下降相对缓 慢的曲线，这使得我们不仅能在网络中发现大量度很小的节点，还能找到一些度很大的节 点。图1 1 中的规则网络，随机网络和小世界网络的节点度分布都不是幂律的，它们的分 堕塞坚皇查堂堕主竺塞生堂垫笙苎 兰二苎堑堡 布区间非常狭窄，几乎找不到偏离节点度均值较大的点。对于这样的网络，上述均值就可 以被看作衡量其节点度的一个特征标度在这个意义上，我们把节点度服从幂律分布的网 络叫做无标度( s c a l ef r e e ) 网络，并称这种节点度的幂律分布为无标度特性。 为了符合复杂网络的无标度特性，b a r a b a s i 和a l b e r t 提出了新的复杂网络模型。他们 认为复杂网络的动态生长和优先连接是彤成这些特性的主要原因，因此以这些特点为基础 得到了新的无标度网络结构( b a 模型) 。图12 是无标度网络结构的示意图。该示意图有1 3 0 个节点，节点度服从幂律分布( 幂指数为- 3 ) 。 从b a 模型开始，许多b a 模型的变形以及一些全新的模型又陆续被提出来，这些模 型无一例外都遵循了b a 模型的基本假设，即动态生长和优先连接。遗憾的是，就目前而 言，直到目前为止，学术界还没有给出复杂网络精确严格的定义。从近几年的研究来看， 复杂网络之所以被称为复杂网络，主要有以下几点原因：首先，它是太规模真实复杂系统的 抽象：其次，它的统计特征明显地不同于规则网络和随机网络。但就日前的研究来看，还没 有一种复杂网络模型生成的网络拓扑完全符合真实网络的统计特征。 图1 2 无标度网络结构示意图 南京邮电大学硕士研究生学位论文 第一章绪论 1 2 复杂网络的应用 网络结构研究非常重要，通过研究网络结构可以了解和解释基于这些网络之上的系统 运作方式，进而预测和控制网络系统的行为。一般将这种建立在网络上的系统动态性质称 为网络上的动力学行为，其涉及面非常之广，如系统的渗流、同步、相变、网络搜索和网 络导航等等。上述研究理论性较强，有一类应用性很强的网络行为研究已经日益引起人们 的兴趣，如计算机病毒在计算机网络上的蔓延、传染病在人群中的流行、谣言在社会中的 扩散等等，实际上它们都是一种服从某种规律的网络上的传播行为。传统的网络传播模型 大都是基于规则网络的，复杂网络研究的深入使我们重新审视这一问题。 由所有移动终端用户构成的移动网络是一些以移动基站与移动终端构成的星形网络 为基本单元的复杂网络，虽然移动网络中的移动终端会在基站之间切换，但总的来说移动 网络的随机性并不很强，它还是具有规则的拓扑结构的。由于存在大量低度节点( 移动终 端) 和少数高度节点( 基站) ，移动网络基本属于无标度网络。因此移动网络节点间的业 务量容限显然受到移动网络拓扑的影响。 移动网络以基站为中心，基站问的连接为蜂窝状。每个基站和移动终端的连接为星形 连接，由于整个网络以每个基站的子网为基础，基站数量和移动终端相比数量较少因此整 个网络的特性基本上由星形网络决定，因此属于无标度网络。 移动网络的业务容量可以由移动网络的拓扑结构计算出来。因此可以根据由社会网络 计算出的总的业务量，再决定相应的移动网络拓扑结构。 一般来说单一地区的移动网络的拓扑结构是有限的。计算出整个网络的平均路径长度 就可以评估出基站间所需的带宽。虽然目前由于g s m 体系得移动网络所产生的数据量并 不很大，因此目前对基站间的通信带宽要求不高。但在3 g 、4 g 网络进入实用以后，由于 移动终端的通信业务量大幅增加，对基站间的通信带宽就会有所要求，通过平均路径长度 就可以估算出移动网络所需的基站间通信带宽。采取不同的移动网络拓扑就可以改变整个 无标度网络的平均路径长度，就可以改变不同设备所面临的业务量的压力。如提高每个基 站的移动终端接入数量，就可以降低平均路径长度。但由于无线带宽的限制，每个基站的 移动终端接入数量是有限的。因此移动网络的拓扑结构的改变基本上很难对整个网络产生 大的改善。 可能的移动通信业务量由社会情况决定，社会网络的结构决定了可能有联系的人，考 虑可能使用移动终端的人群，以及他们的联系强度，再考虑拥有固定终端的人，就能够预 估出移动终端网络总体的业务量。社会网络属于无标度网络，因此复杂网络的理论对估算 s 塑室坚鱼查堂堡主塑壅竺堂篁丝文 第一章绪论 业务量是适用的。 社会网络由人们的复杂人际关系构成，它属于无标度网络，人们的关系决定了人们需 要通信联系。通信联系的产生取决于多方面，包括人们的经济状况，通信习惯，生活需求 和业务需求。这些特性的计算和基础数据基本上来自于统计数据。 1 3 研究内容和意义 为了建立移动网络的模型。需要建立社会网络的拓扑结构。就目前的研究来看，还没 有一种复杂网络模型能够生成完全符合真实网络统计特征的网络拓扑。研究者都在积极寻 找复杂网络特性背后真正的形成原因。由于实际网络数据获取等方面的限制，本文使用 i n t e m e t 复杂网络拓扑结构，来研究复杂网络的模型。由于i n t e m e t 网络和社会网络同属无 标度网络，具有相似的特性，所以使用用于i n t e m e t 网络的基于消息传递的拓扑模型。拓 扑结构的选择可能会对模拟结果造成很大的影响，因此如何选择模拟网络的拓扑结构是关 键环节。 本文基于移动复杂网络的统计特征及复杂网络的形成机制，提出种复杂网络模型及 其拓扑生成算法，并在此基础上提出一种移动网络话务量的模型。 第一章首先介绍复杂网络的背景、发展过程，以及目前研究的现状。 第二章是复杂网络定义。首先讨论图论的基本概念，然后给出几种度量复杂网络的重 要参数。最后分析了复杂网络研究中的一些量纲和现有的网络拓扑模型定义及其构造力 式。重点介绍复杂网络( 包括小世界网络、无标度网络及真实的i n t e m e t 网络) 的建模原理及 过程。 第三章首先讨论几种建模的基本理论。然后提出基于消息传递的复杂网络模型。基亍 复杂网络特征的形成机制，提出一种具体的复杂网络拓扑的建立方法。然后，给出实现谚 模型的拓扑生成器的核心算法，最后分析算法的复杂性。 第四章讨论使用前文建立的社会网络拓扑结构，将其应用于移动网络的话务量模望 中。利用社会网络的拓扑结构和移动网络的拓扑结构，以及经验数据模拟出移动网络的荫 务量。 第五章是总结与展望。 6 南京邮电大学硕士研究生学位论文 第二章复杂网络概述 2 1 图的基本概念 2 1 1 图的概念 第二章复杂网络概述 所谓图( g r a p h ) 是指有序三元组e ，q ) ，其中v 非空称为顶点集( v e r t e xs e t ) ，e 称为边 集( e d g es e t ) ，而q 是e 到v 中元素有序对或无序对簇v v 的函数，称为关联函数( i n c i d e n c e f u n c t i o n ) 。v 中元素称为顶点( v e r t e x ) ( 或点( p o i n t ) ) ，e 中元素称为边( e d g e ) ，q 刻画了边与顶 点之间的关联关系。若v v 中元素全是有序对，则e ，9 ) 称为有向图( d i g r a p h ) ，记为d = ( v ( d ) ，e ( d ) ，t p d ) 。若v v 中元素全是无序对，则e ，中) 称为无向图( u n d i r e c t e dg r a p h 或 g r a p h ) ，记为g = ( v ( g ) ，e ( g ) ，q g ) 。设a ee ( d ) ，则存在x , y e v ( d ) 和有序对 x ，y ) v v 使9 d ( a ) = ( x ，y ) 。a 称为从x 到y 的有向边( d i r e c t e de d g ef r o mx t oy ) 。x 称为a 的起点 ( o r i g i n ) ，y 称为a 的终点( t e r m i n u s ) ，起点和终点统称为端点( e n d - v e r t i c e s ) 。设e e ( g ) ，则 存在x ，y v ( g ) 和无序对 x ，y ) e v v 使q d ( e ) = ( x ，y ) 。由于无序对 x ，y ) y ，x 表示同一 个元素，所以通常简记 p g ( e ) = x y 或y x ，e 称为连接x 和y 的边( e d g ec o n n e c t i n gxa n d ” 2 1 2 图的图示 通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示( 直线或曲 线) 。这样画出的平面图形称为图的图示，如图2 1 所示。由于表示顶点的平面点的位置的 任意性，同一个图可以画出形状迥异的很多图示，比如图2 2 是图2 1 的另一个图示： 怕 旬h 图2 1 图的图形表示 7 南京邮电大学硕士研究生学位论文第二章复杂网络概述 图的图示直观易懂，因此以后一般说到一个图，我们总是画出它的一个图示来表示。 2 1 3 图的表示 无论是对图进行数学运算还是用计算机对图进行处理，都需要一种形式化的方法来表 示。不同的系统抽象出来的图具有不同的特征，如有的图边的数量较少，称为稀疏图；有 的图边比较稠密，称为稠密图。为了运算的方便或者是节约存储空间，不同的图可以用不 同的形式表达。下面分别介绍图的两个主要表示方式，即领接矩阵和关联矩阵。 图的邻接矩阵表示如下，其中v l 吃lk 表示节点的序列，表示顶点v i 与v j 之 间边的数量，如果是节点之间不允许重边，则口，的取值为0 或1 。如果a ( g ) 是无向图，则 a ( g ) = 么( g ) r 。邻接矩阵需要的存储空间复杂度为o ( n 2 ) ，n 为节点数量。邻接矩阵适合 表示稠密图，但不适合稀疏图。 l k l q ， l 呸， l l l 口坩 图的关联矩阵表示如下，其中v lv 2 v v 表示节点的序列，e le 2 e v 表示边的序列。 其中m o 表示顶点v j 在边e j 中出现。在节点数量一定条件下，关联矩阵的表示占用的存储 空间还与边的数量有关，其空间复杂度为o ( n m ) ，其中n 为节点数量，m 为边的数量。 关联矩阵适合表示稀疏图，但不适合表示稠密图。 2 2 复杂网络的基本参数 l p ， l ，l l ， l 朋2 y ll l 聊。 ( 2 2 ) 目前的复杂网络研究还处于起步阶段，大量的实证研究方法被用到复杂网络中来。不 同领域的研究者通过统计的方法对复杂网络进行初步研究。为了发现不同系统抽象出来的 复杂网络的共同特征，就必须有统一的复杂网络参数。其次，为了衡量各种复杂网络拓扑 模型的准确性，也需要这样一些参数。目前的研究中，使用较为频繁的几个参数为网络平 8 屹吃l h q 吒l q ，fr-。一吖j 叫m 以 =g 4 2 2 2 口 吃仇l 气 鸭l ，t-。l吖叫m 以 i i gm 南京邮电大学硕士研究生学位论文 第二章复杂网络概述 均距离、网络聚集系数和网络的度分布等。 2 2 1 网络平均距离 传输延迟是影响网络性能、信息传递的重要因素，而距离和直径是度量传输延迟的重 要参数。但网络距离和直径都无法对网络的总体特征进行评价，因此需要引入网络的平均 距离参数来度量。首先，定义节点i ，j 的距离蛔为从节点i 到达另一个节点j 至少要经过 的边的数目。对于无向网络，平均最短距离定义为： ( g ) 2 丽i ，；_ ) ( 2 3 ) 其中，v 表示网络g 的节点数，v 表示网络g 的节点集合。 2 2 2 网络的聚集系数 网络的聚集系数描述了，网络的聚集程度。某个节点i 的聚集度定义为i 的邻居i 司买际 存在的边数和节点i 的邻居间完全连接的边数之比。节点i 的聚集系数为： c ( f ) = 耥 ( 2 - 4 ) 整个网络的聚集系数是每个节点聚集系数的平均值： c g2 吉善c ( f ) ( 2 - 5 ) 2 2 3 网络的度分布 在有向网络中，节点的度包括出度和入度。无向网络中没有出度和入度的区别。节点 的度能够很好地描述节点的重要程度，用d ( k ) 表示网络中度数为k 的节点个数或在网络中 所占的比例。不同的网络模型具有不同的d ( k ) 函数。 2 3 几种复杂网络模型 复杂网络模型的发展经历了一个从简单到复杂的过程，随着人们对复杂网络研究的不 断深入，越来越多的新特性被发现，以前网络模型的许多统计特征不再符合实际观察到的 复杂网络。为了更符合实际网络，越来越多的复杂网络模型正在被提出来，下面简要讨论 9 南京邮电大学硕二e 研究生学位论文第二章复杂网络概述 复杂网络模型发展中的几个关键模型。 2 3 1 规则网络与随机网络 通常，我们把一维链，二维正方晶格等称为规则网络。规则网络是指平移对称性晶格， 任何一个格点的近邻数目都相同。规则网络的簇系数c 值较大，平均最短距离l 也较大。 随机网络是另一个极端，由n 个顶点构成的图中，可以存在c n 2 条边，从中随机连接m 条 边所构成的网络就叫随机网络。另外一种生成随机网络的方法是，给一个概率p ，对于cn 2 中任何一个可能连接，都尝试一扁以概率p 的连接。如果我们选择m = pc n 2 ，则这两种 随机网络模型就可以联系起来。与规则网络相反，随机网络的平均最短距离l 较小，但簇 系数c 较大。对于如此简单的随机网络模型，其几何性质不是同样的简单。 经典随机网络e r 模型由e r d b s 和r 6 n y i 于1 9 5 9 年提出，e r 模型中有n 个节点，仍 以两个节点以概率p 连接。如果p = l 表示n 个节点完全连接，总边数为n ( n - 1 ) 2 ：如果 p = 0 ，则n 个节点相互孤立：p ( 0 ，1 ) 时，网络中的总边数为p n ( n - 1 ) 2 ，平均度 = 2 n n = p ( n - i ) 。当n 很大时，度分布函数p ( k ) 服从p o i s s o n 分布。随机网络的主要特征 是： ( 1 ) 聚集系数较小； ( 2 ) 网络平均距离小； ( 3 ) 节点度服从p o i s s o n 分布。 规则网络与随机网络的经典几何性质包括：度分布，平均聚集程度与平均最短距离。 规则网络所有定点连接度都相同，因此顶点度值相同。其顶点的度分布为6 ( k k o ) ；其平均 集聚程度也只需要知一个点计算：c = c ，；其平均最短距离可以只从某一个顶点开始计算 从它到所有其他顶点之间的距离之和，然后计算其平均值：d = 五l 巧x n ：n 。对于随机网络 g ( n ，p ) 则包含了从空图到完全图的所有可能情况，因此随机网络的几何性质需要对每一 种可能网络做平均，例如，我们计算一种可能网络的最短距离，然后按照各自出现的概率 求平均值。研究结果表明，随机网络顶点的度值符合平均值为n ，的泊松分布，其集聚 程度约等于p ，最短距离d ：i n ( n ) 。 对比规则网络与随机网络可以发现盯1 嘲，平均聚集程度与平均最短距离这两个静态几 何量能够很好地反映规则网络与随机网络的性质及其差异国1 。规则网络的特征是平均聚集 程度高而平均最短距离长，随机网络的特征是平均聚集程度低而平均最短距离小。 南京邮电大学硕士研究生学位论文第二章复杂网络概述 2 3 2 小世界( s m ai i - w o rld ) 网络 许多现实系统抽象得到的网络具有较高的聚集系数，较小的平均网络距离，度分布服 从幂律( p o w e r - l a w ) 分布，而经典的随机网络不能体现这一特征。复杂网络拓扑结构的不确 定性是复杂网络研究的基本问题。二十世纪中叶e r d b s 和r 6 n y i 突破传统图论，用随机图 描绘了复杂网络拓扑结构。近年来研究发现，很多实际的复杂网络既不完全规则也不完全 随机，而是介于完全规则和完全随机这两个极端之间，即具有类似规则网络的较大聚集系 数，又具有类似于随机网络的较小平均路径长度，这就是小世界网络。 六十年代末期，美国科学家m i l g r a m 成功完成了一个著名的试验。m i l g r a m 经过统计 分析发现。每封信件平均要通过6 个人才能把信从尼布鲁斯传到他在波士顿的朋友手中。 忽视实验误差，他得出的结论是：任意两个人之间可以平均通过6 个熟人联系在一起，或 者说，世界上任何两个人之间可以被某些因素相联。人们称这种特征为“六度分离 ，这 个结论用物理学术语来说就是“小世界效应 。用图论与网络学的术语就是两个相距很远 的节点是可以相联的。这个特性在规则网络中是没有的，却是随机网络的一个重要特征。 小世界网络拓扑结构为从规则网络的底层网络出发，在底层网络的任意两个选定的节 点之间添加连接( 即添加两节点连通的捷径) ，使之向随机网络过渡。当捷径增加到了一定 程度时，即产生了小世界网络的形态。对于有n 个节点，每个节点有k 条边的环形规则网 络，以概率p 重连它的边。显然，当p = 0 时，相当于各边均未动，仍是规则网络；当p = l 时，就变成了随机网络。当0 o ，f l o ，c o ) 3 3 2 拓扑生成算法 r + l = a i , + i ( 口 1 ) ( 3 - 3 ) ( 3 - 4 ) 拓扑的演化过程是一个无限循环过程，每一次循环中，每个节点计算自己的优先度和 消息发送范围，再发送消息给其它节点。然后，每个节点接收来自其它节点的消息，并根 据消息中的内容来决定与某个消息源建立连接。为了避免节点的度数过大。模型为每个节 点保存一个“最优先邻居 ，后来的消息源只有在其优先度超过“最优先 邻居达到一定 阀值时才建立连接，新建立连接的邻居变成了最优先邻居。模型主体算法如下： 南京邮电大学硕士研究生学位论文 第三章基于消息传递的复杂网络拓扑建模 囤 唤醒时间 循环结束 节点循环结束 节点循环结束 图3 2 拓朴生成算法 算法初始化时，需要为每个节点分配坐标位置、设置开始活动的时刻以及进行坐标登 记，坐标登记的目的是降低算法的复杂度。如果不引入坐标登记，则每个消息需要发送给 所有节点。并由接收节点判断消息是否超出其正常作用范围。引入坐标登记后，就能够找 到该消息作用范围所覆盖的节点。在模型中预期有大量节点具有较小的度，从而具有较小 的消息发送范围，因此采用坐标登记后能大幅加少消息的发送量。 在算法中发送信息与接受信息是整个算法的核心，发送信息主要负责填充消息内容， 包括消息源i d 以及消息源的优先度，然后调用辐射范围内节点集中每个节点的接受信息。 2 3 南京邮电大学硕士研究生学位论文第三章基于消息传递的复杂网络拓扑建模 接受信息主要负责判断消息来源的优先度，并选择优先度较高的节点建立连接。这两个函 数决定了生成的拓扑结构的统计特性。 3 4 算法分析 现实中的复杂网络是在不断演化发展的，所有时刻都可能有新的节点加入和老的节点 退出。考虑到算法在程序中的可行性，我们首先定义了1 0 0 0 个节点随机分布在二维平面 中，模拟了拓扑演化1 0 0 代的动态过程。 算法中p 的作用是调节节点自身的度和邻居节点的度之和在节点优先度中的权重比， 通常取d = l 。通过改变a 值，可以调整节点发射消息的辐射范围，若a 太小，如a = 2 或 a = 5 ，将导致在很长一段时间内，消息仅在很小的局部区域内传播，导致整个网络拓扑没 有层次结构，与随机网络模型( e r 模型) 相似。但是如果a 值过大，如a = 1 5 ，又会使大量 节点的消息辐射范围覆盖整个平面，导致模型向全局优先连接模型( b a 模型) 靠近。其特征 是全网存在少量集散节点。仿真结果表明，a = 1 0 时，生成的拓扑结构能较为准确的反映 现实复杂网络中的拓扑结构。当a 设为2 的时候，仿真结果的度分布较好地符合幂率分布。 图3 3 、3 4 、3 5 为社会网络中度分布，横坐标为节点度( 连接数) ，纵坐标为拥有相应度( 连 接数) 的节点数目。 k o d e 丁 z m 刁 o z 图3 3 节点数为1 0 0 0 南京邮电大学硕士研究生学位论文第三章基于消息传递的复杂网络拓扑建模 l - d e 了 z o 刁 o z 2 5 0 0 2 0 0 0 岩1 5 0 0 e 3 z m1 0 0 0 刁 o z 5 0 01 02 03 04 05 06 0 n o d ec o n n e c t i o n 图3 5 节点数为4 0 0 0 以度分布为目标的拓扑模型能够很好的反映现实网络中的统计特征。仿真曲线表明， 在不同的规模下拓扑结构的度分布表现出较强的稳定性，可以产生九在2 - 5 之间的拓扑结 构，见图3 6 。 2 5 南京邮电大学硕士研究生学位论文 第三章基于消息传递的复杂网络拓扑建模 l d e 3 z o 勺 o z 3 5 本章小结 图3 6 节点度分布的统计特性 本章描述了基于消息传递的自组织复杂网络拓扑模型。通过调节( i t 的值，模型可以平 滑地从b a 模型过渡到e r 模型，还可以得到许多介于b a 模型和e r 模型之间的中间模型。 本章分析了复杂网络拓扑模型建立的社会网络拓扑，同时在此基础上对模型进行了改进， 更加符合实际情况，下一章将把它和移动网络结合起来建立移动网络话务量的模型，用来 描述移动网络的话务量。 南京邮电大学硕士研究生学位论文第四章复杂网络模型的移动通信应用 第四章复杂网络在移动网络话务量建模中应用 4 1 移动网络的拓扑结构 移动网络是一些以移动基站与移动终端构成的星形网络为基本单元的复杂网络，虽然 移动网络中的移动终端会在基站之间切换，但总的来说移动网络的随机性并不很强，具有 规则的拓扑结构。由于存在大量低度节点( 移动终端) 和少数高度节点( 基站) ，移动网 络基本无标度网络。 如果认为各个蜂窝站之间的连接是可靠的，移动网络的拓扑结构可以简化为各个独立 的星形网络。将所有的移动终端用户随机地分散到所有的基站当中，所有的移动终端用户 间的社会联系网络则是在这个移动网络背后的隐形网络，话务量则由这个隐形网络来决 定，将这两个网络结合起来研究，就能得到描述移动网络的工作情况和话务量情况的移动 网络模型。 4 2 移动网络话务量模型 话务量的产生是由于有社会关系的两个移动终端用户间需要联系而产生的。话