复杂网络与无线传感网 自制PPT.ppt

1、复杂网络拓扑结构研究,-无线传感器生命周期估计,1 无线传感器网络拓扑结构（引言） 2 复杂网络 2.1 ER模型（随机图形） 2.2 BA模型（无标度） 2.3 WS模型（小世界）,无线传感网络定义,无线传感器网络（Wireless Sensor Network）是由大量低成本且具有传感、数据处理和无线通信能力的传感器结点通过无线通信技术自组织构成的网络。,该技术融合了传感器技术、信息处理技术和网络通信技术，是信息技术中的一个新的领域。,可实现数据的采集量化、处理融合和传输应用，因此在军事和民用领域均有着非常广阔的应用前景。,目前，该技术已成为美国技术评论杂志评出的十种将改变世界的新兴技术和

2、美国商业周刊评出的未来将掀起新的产业浪潮的四大高新技术之一 。,拓扑结构,根据传感器结点在使用中是否移动，可将无线传感器网络分为： 静态网络：结点被随机地或按一定要求布置在监测区域内，并根据用户的要求进行测量。 动态网络：结点被安置在可移动的物体上，如车辆或被监测的动物，它将随物体的移动而移动。 汇聚(sink)结点：也称网关结点，它是无线传感器网络的中心处理结点，该结点可向区域内的传感器结点发送数据采集命令，并接收和处理传感器结点传送来的数据。,拓扑图,动态网络,动态网络2,研究要求,低能耗：由于传感器结点的体积小，因此电池容量有限，而且由于传感器网络的工作环境往往难以更新电池或因更新代价大

3、而不可操作。 可扩展：由于传感器结点可能非常多，因而要求其应用的各项技术能有效用于大规模网络。 自适应：能够适应环境、网络拓扑等动态变化以及网络的高冗余特性等。 简单：由于传感器结点的能力受限，因而现实可行的技术应简单有效。,硬件组成,相对独立,存储器,ADU,CPU,电源,传感器,网络接口,天线,与应用有关,与应用 相对独立,应用部件,结点平台,WSN与其他无线网络的对比,由于传感器网络应用的特殊要求，传统的无线网络中的很多研究成果不再适用。 蜂窝网络（Cellular Network) 移动自组织网络(MANET,Moblie Ad Hoc Network) 蓝牙短距离无线网络(SRWN,

4、 Short Range Wireless Network),11,无线传感器网络,估计生命周期,结点数重多 自然连接,复杂网络,目标,特点,什么是复杂网络,2005/11/3,13,2005/11/3,14,Categories of Complex Networks,Complex Networks,Social Networks,Technological(Man-made) Networks,Information (Knowledge) Networks,Biological Networks,Friendship Sexual contact Intermarriages Busi

5、ness Relationships Communication Records Collaboration (film actors) (company directors) (coauthor in academics) (co-appearance),Internet Software classes Airline routes Railway routes Roadways Telephone Delivery Electric power grids Electronic circuit,WWW P2P Academic citations Patent citations Wor

6、d classes Preference,Metabolic pathways Protein interactions Genetic regulatory Neural Blood vessels Food web,ER模型,Erds和Rnyi （ER）最早提出随机网络模型并对模型进行了深入研究，他们是用概率统计方法研究随机图统计特性的创始人。 在模型开始阶段给定N个节点，没有边，以概率p用边连接任意一对节点，用这样的方法产生一随机网络。 图论小贴士： 度 连接顶点的边的个数称之为度 在一个有向网络中，有入度和出度之分 中心结点 度的值突出的点，被称为中心结点。 例如在网络中，中心结点可以

7、是Yahoo,或着Google。,Poisson distribution,N=100 P=0.1,什么是无标度网络?,无标度网络是由Barabasi所命名的（BA模型)，该种网络具有2种特性：不断增长和偏好连接。 不断增长： 早期的网络模型没有考虑结点数随着时间而增长。整个图形是静止的。然而，在现实生活中，总有新人加入到社交网中，总有新的网站在internet上出现。于是乎，网络处在一个不断增长的状态。,Hello!,Nice to meet you!,偏好连接,无标度网络的另一个特性，偏好连接，意指新结点连接度高的结点的可能更大。 在如下的一个例子当中，新结点最有可能和红色结点相连。 在现

8、实生活中，新的网站很有可能会和一些热门的网站相连例如Yahoo, Google, BaiDu。,New Node,幂分布现象。,无标度网络貌似服从幂分布。 早期的模型把网络描述成一个钟型曲线，大量的结点拥有相同的度，而几乎没有高度的结点。 在无标度网络模型中，网络是由大量低度的结点以及少量高度的结点所组成的。,# of links (k),# of links (k),# of nodes with k links,# of nodes with k links,Bell Curve,Power Law Distribution,Degree Distribution,几种真实网络的度分布图。

9、 a internet ；b 电影演员合作关系网络；c 高能物理学家合作关系网；d 神经学家合作关系网络。不是泊松分布，而是符合幂函数分布。,如右图所示，整个网络中的结点通过 红色的中心结点连接在一起。 如果黄色的结点失效了，系统依旧保持 完整，其余的结点依旧相互连通。 然而，如果红色的结点失效了，整个系统 分成3块互不相连的部分。,无标度网络的优缺点,小世界理论,生活在这个世界上的每个人只需要很少的中间人（平均6个）就可以和全世界的任何一个人建立起联系。 这就是六度分离理论，也叫小世界理论。这似乎是很普遍的客观规律：社会化的现代人类社会成员之间，都可能通过“六度分离” 而联系起来，绝对没有联

10、系的A与B是不存在的。这是一个更典型、深刻而且普遍的自然现象。该理论最早由美国社会心理学家Stanley Milgram (1967)创立。,在1958年, Pool 和Kochen 提出了一个问题“2个陌生人之间拥有一个共同的朋友的概率是多少” (社会网络的组成关系是怎么样的?) 进一步提出了一个更困难的问题: “如果他们没有共同的朋友，那么2个人之间的间隔是多少（通过几个朋友他们可以相互认识?”） 太复杂,小世界实验,在1967年, Stanley Milgram (与他的学生 Jeffrey Travers) 在 Pool 和 Kochens 的工作的基础上设计了一个试验. (将一封信从

11、A传递给B需要多少次接力?) 1个B在波士顿. 300 个A在内布拉斯加 . 每一个A都会将信发给最接近波士顿的朋友. 他的朋友也会做同样的事.,The Small World Experiment,The Small World Experiment,Path Length,Clustering Coefficient,WS小世界模型的构造方法如下：,(1)从规则图开始，考虑一个含有N个节点的规则网络，它们圈成一个环，其中每个节点都与它左右相邻的各K2个节点相连接，K为偶数；(2)随机化重连，以概率p随机地重新连接网络中的每条边(将边的一个端点保持不变，而另一个端点取为网络中随机选择的一个节点)，其中规定，任意两个不同的节点之间至多只能有一条边，并且每一个节点都不能有边与其自身相连。下面3个图表示了小世界网络的构造以及它与规则网络、随机网络的关系。在WS小世界模型中，p0对应于规则网络，pl则对应于完全随机网络，通过调节p的值就可以控制从规则网络到完全随机图的过渡。因此小世界网络是介于规则网络和随机网络