最短路径算法之无线路由器应用模拟设计报告

1、模拟Sensor network的工作课题背景：随着时代的进步，科学技术也在不断地发展更新，微型制造，无线通讯以及电池技术的发展，使得微 小的感测器(sensor)应运而生。微型感测器(sensor)具有感应，无线通讯以及处理信息的能力，它能够感应侦 测其周围一定范围内目标物的变化，并将收集到的数据初步处理后以无线传输的方式将信息送到收集中心 或基站。基于这些优点，感测器迅速地得到了广泛地应用：军事应用人员识别，战场侦测，敌方部 队的大规模调动等环境应用检测空气污染，监测水体状况，监测工业污染物排放，监测地壳活动 居家应用远端控制，温度监测，防盗系统等。该感测器微小且便宜，可以在所需侦测的局域

2、里大量放 置，形成一个巨大的传感器网络对目标环境进行侦测，但由于该感测器的工作能量一般来自于电池，并且 每个感测器的通讯范围有限，所以在一个传感器网络中，需要利用网络路由的方法将数据等信息传送到收 集中心或基站。问题描述：Sensor network是一种新型的网络，其基本结构如下图所示：该网络由两部分组成，Sensor node集和 Data Collectoro Sensor node (可简称为Sensor)能够完成感知环境数据并将其发往 Data Collector的功能。 Data Collector完成 Sensor采集数据的收集，它就是一台带有无线接收功能的计算机。Data Co

3、ll已史浮Interested areaSensor node限 Sensor nvcirvTk 陲示Sensor network可应用到很多实际领域中，如在战争中将Sensor散播在防线的前沿，可以收集敌人的一些 情报(如大规模的部队转移等)。Sensor散播的地方称为Interested area，Sensor在这个区域内采集各自所 在位置的数据，然后将采集到的数据传送到 Data Collector。各个Sensor之间通过无线广播通讯，由于 Sensor广播能力的限制，它只能和位于自身的一定广播半径内的Sensor进行通讯，所以有些Sensor就需 通过其它Sensor，经过多次路由后

4、才能到达Data Collector (如上图)。如何路由由Sensor内动态生成的路 由表来决定。Data Collector的位置就在Intersted Area的边缘，且固定不动。分析与设计：Sensor在传递数据给收集中心或基站的路由过程是按照自身存储的路由信息寻址的，如何给每个sensor 动态地设计路由表是解决本问题的核心。这其实就是单源点最短路径问题：给定带权有向图G=(V,E)和源点，求v到G中其余各点的最短路径。最短路径问题是图的一个典型的应用问题，如：给定某公路网 的n个城市以及这些城市之间相同公路的距离，能否找到城市A到城市B之间的一条距离最近的通路？怎 样找到最经济的方

5、式，从一台计算机向网络上所有其他计算机发送一条消息？Dijkstra算法是解决最短路径问题的一个优秀算法，它是一个按路径长度递增的次序产生最短路径的， 其基本思想：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对vC V-S，假 设从源点v到v的有向边为最短路径。以后每求得一条最短路径v,v(k),就将v(k)加入到集合S中，并 将路径v,v(k)，v(i)与原来的假设相比较，去路径长度较小者为最短路径。重复上述过程，直到集合V 中全部顶点加入到集合S中。程序设计:程序设计目的：应用数据结构相关知识模拟一个新型网络系统，满足以下基本要求。.设置感测器数目数据收集器坐标Co

6、llector，基本要求：在单机上模拟Sensor network的工作。用 VC+ (C也可以)实现模拟系统，N个Sensor和1个 Data 其具体位置随机确定，Interest Area就是屏幕。N可配置，缺省为100。Sensor进行周期性采集，其采集周期可配置。Sensor的广播半径固定，也是可配置的参数。 路由算法自行选择或设计显示随机分布 的感测器信息程序运行流程图：(右侧)本程序为Win32控制台程序，采用菜单驱动，屏幕输出结果设置感测器通信半径 数据收集周期确定 收集器坐标输入数据收集器编 号及数据收集次数 并确定显示各感测器 (包括收集器)之 间的路由信息周期性显示连接中感

7、测器收 集的信息注：二和二:，分别表示手动输入信息并确定和相关信息的屏幕显示。自定义数据类型:struct nodeint start;int end； double len； node* next;；路径起点 路径终点 打路径长度 stnict s 伫口rIkit r;传感器在区域中的行号int c-传感器在区域中的列号int data;_/_/收集的数据intno;传感器编号int Hag;标记clas s LinkNo de /7 链式队列ptlvate：double *Gr4h；n*a的二维数组作为有权图空间int pointnum;/顶 点教目double* Path_cost；/有

8、权边int pathc;/有杈边的数目public:MGr枣h( int size);triend void ShortPathlGraph g, int point,sen* data);/Dijkstra算法void BuildGraph( int size);创 建 有权图string Point(int p)；void BuildPath(node* tmp );void Show()；_rpublic:int num;private：sen point； 感丽器LinkXode* next；LinkXcide* JErcnt;LinkXode* rear;public:LinkXad

9、e.；)；void enque(sE：flfi p ； FJ入队sen&delque(); /7 出对class SensorWorKpublic：sen ;inr radius; 通信半径LiiikNode P；口2畔Ep ;/7指示伟感嚣互凝情况用以建立图的有权边ZMGraph mg;private：int r;im匚；收集器的坐标int stime；inr size；inr sennum； /_/传感舞的数目即图出预点个数)public：SensorWorK-f int 睛nnum);-S ens orWo rk-f ) sen* SetSensor-.i _/ x./ / ril tf

10、a 隹类关系图:注:Area为结构体数组，表示感测区域；p为链式队列；sp用于指示感测器之间互联的情况，并以此建立图 的有权边边集；mg为MGraph的一对象，主要实现Dijkstra算法。核心算法：由二维数组创建图的有权边算法：该算法为“以二维数组(区域)中某元素(感测器)为起点，且遵循感测器的通讯半径来最大化遍历数组元 素(感测器)，同时建立与之相对应的图的有权边边集的问题”提供了解决方案。结构体二维数组中非-1的元 素代表感测器编号(感测器的位置在程序运行时动态确定)void S ensorWork: Cost_path(st, int sLinkN cxle &p)1 if(&t=NU

11、LL)判断是不是队列以空！return；else=二this-senaum)ietu.ni;int mr = t.t；int me = t.c;int x = sr;while( sr=-x)i( mr-sr = 0 & mr-sr =-x; i)控制列方向在区域内if( mc-i = & mc-i start = Are amr me .no;path- end = Are amt-y me -i .no；path-len = s qrt(y*y* 1 .O+k*x* 1.0);Hohai UniversityPage 4 of 6path-next = sp;sp = path;Aream

12、rmc .flag += 1; 一if( Areathis-rthis-c.flag = 0)1 cout，1收集器无法找到传感落”&口； retuui; . . _. _return Cost_path(P.delque( this- radius,P)；Dijkstra最短路径算法：V如果收集器周国没有传感器 失灵h g, ini: p,su口* data)int sizesize =g.pointaum;double *dist = new doublesize;string *path = new stringsize;string *pset new stringsize;/data

13、显示连摆着的传感器数据存放源点p传感器编号)到各点的距离，记为无穷运(不连通)存放路径，记录已经选取过的结点for(int 1=。； i +g.Poiit(i elsePa由=”；如果路径不是无穷大，path|i+便存储该路径名psetO = g.Point*p);disttp = 0;int num = 1;while(num size )int k=D;double short_dist 999;foi(int m=0； msize； m+)if( (distfm short_dist) & distm != 1记录已经选取过的结点/当终点集合中的预点数小于K中的顶点数时循环)找出dist

14、中蠢小值，k为最小值下标fishort_dist = distm;k =m;if( disti = 0)该传感器不在有效通信范国，失去连接！elsefoi(int di=0; di size； di+ )for-fint dj =0; djsize； dj+ )if( dat3didj.no=k)输出路径长废，路由路径，感测器数据ffcout配tw(5)distk pathk dat3didj.dataendl;goto lable 1;lablel:psetnum+ = g.Poiat(k);将新产生的路径的终点加入到集合中-同时将该终点做上标记foi(int j=0; j (distk+喜Gr3phkj)/当p-j的距离大于p-Ak + k-j的寤离时作改变1 distj = distk +昏 GraphMi； pathj； =pa由distk = 0;部分源代码：感测器周期性数据收集：void SensorVf orkLzDela?；.-；Sleep( stime); Colle ctDat3();void SensorWork:：CollectData)V冏期挫收集数据for(iat i=0; isize； i+ )rj=。； jsize； j+ )rif( ArealC+程序设计教程作者:钱能清华大学出版社数据结构（C+ +版）作者:王红梅清华大