最短路徑算法之無(wú)線路由器應(yīng)用模擬設(shè)計(jì)報(bào)告

1、模擬Sensor network的工作課題背景：隨著時(shí)代的進(jìn)步，科學(xué)技術(shù)也在不斷地發(fā)展更新，微型制造，無(wú)線通訊以及電池技術(shù)的發(fā)展，使得微 小的感測(cè)器(sensor)應(yīng)運(yùn)而生。微型感測(cè)器(sensor)具有感應(yīng)，無(wú)線通訊以及處理信息的能力，它能夠感應(yīng)偵 測(cè)其周圍一定范圍內(nèi)目標(biāo)物的變化，并將收集到的數(shù)據(jù)初步處理后以無(wú)線傳輸?shù)姆绞綄⑿畔⑺偷绞占行?或基站。基于這些優(yōu)點(diǎn)，感測(cè)器迅速地得到了廣泛地應(yīng)用：軍事應(yīng)用人員識(shí)別，戰(zhàn)場(chǎng)偵測(cè)，敵方部 隊(duì)的大規(guī)模調(diào)動(dòng)等環(huán)境應(yīng)用檢測(cè)空氣污染，監(jiān)測(cè)水體狀況，監(jiān)測(cè)工業(yè)污染物排放，監(jiān)測(cè)地殼活動(dòng) 居家應(yīng)用遠(yuǎn)端控制，溫度監(jiān)測(cè)，防盜系統(tǒng)等。該感測(cè)器微小且便宜，可以在所需偵測(cè)的局域

2、里大量放 置，形成一個(gè)巨大的傳感器網(wǎng)絡(luò)對(duì)目標(biāo)環(huán)境進(jìn)行偵測(cè)，但由于該感測(cè)器的工作能量一般來(lái)自于電池，并且 每個(gè)感測(cè)器的通訊范圍有限，所以在一個(gè)傳感器網(wǎng)絡(luò)中，需要利用網(wǎng)絡(luò)路由的方法將數(shù)據(jù)等信息傳送到收 集中心或基站。問(wèn)題描述：Sensor network是一種新型的網(wǎng)絡(luò)，其基本結(jié)構(gòu)如下圖所示：該網(wǎng)絡(luò)由兩部分組成，Sensor node集和 Data Collectoro Sensor node (可簡(jiǎn)稱為Sensor)能夠完成感知環(huán)境數(shù)據(jù)并將其發(fā)往 Data Collector的功能。 Data Collector完成 Sensor采集數(shù)據(jù)的收集，它就是一臺(tái)帶有無(wú)線接收功能的計(jì)算機(jī)。Data Co

3、ll已史浮Interested areaSensor node限 Sensor nvcirvTk 陲示Sensor network可應(yīng)用到很多實(shí)際領(lǐng)域中，如在戰(zhàn)爭(zhēng)中將Sensor散播在防線的前沿，可以收集敵人的一些 情報(bào)(如大規(guī)模的部隊(duì)轉(zhuǎn)移等)。Sensor散播的地方稱為Interested area，Sensor在這個(gè)區(qū)域內(nèi)采集各自所 在位置的數(shù)據(jù)，然后將采集到的數(shù)據(jù)傳送到 Data Collector。各個(gè)Sensor之間通過(guò)無(wú)線廣播通訊，由于 Sensor廣播能力的限制，它只能和位于自身的一定廣播半徑內(nèi)的Sensor進(jìn)行通訊，所以有些Sensor就需 通過(guò)其它Sensor，經(jīng)過(guò)多次路由后

4、才能到達(dá)Data Collector (如上圖)。如何路由由Sensor內(nèi)動(dòng)態(tài)生成的路 由表來(lái)決定。Data Collector的位置就在Intersted Area的邊緣，且固定不動(dòng)。分析與設(shè)計(jì)：Sensor在傳遞數(shù)據(jù)給收集中心或基站的路由過(guò)程是按照自身存儲(chǔ)的路由信息尋址的，如何給每個(gè)sensor 動(dòng)態(tài)地設(shè)計(jì)路由表是解決本問(wèn)題的核心。這其實(shí)就是單源點(diǎn)最短路徑問(wèn)題：給定帶權(quán)有向圖G=(V,E)和源點(diǎn)，求v到G中其余各點(diǎn)的最短路徑。最短路徑問(wèn)題是圖的一個(gè)典型的應(yīng)用問(wèn)題，如：給定某公路網(wǎng) 的n個(gè)城市以及這些城市之間相同公路的距離，能否找到城市A到城市B之間的一條距離最近的通路？怎 樣找到最經(jīng)濟(jì)的方

5、式，從一臺(tái)計(jì)算機(jī)向網(wǎng)絡(luò)上所有其他計(jì)算機(jī)發(fā)送一條消息？Dijkstra算法是解決最短路徑問(wèn)題的一個(gè)優(yōu)秀算法，它是一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的， 其基本思想：設(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對(duì)vC V-S，假 設(shè)從源點(diǎn)v到v的有向邊為最短路徑。以后每求得一條最短路徑v,v(k),就將v(k)加入到集合S中，并 將路徑v,v(k)，v(i)與原來(lái)的假設(shè)相比較，去路徑長(zhǎng)度較小者為最短路徑。重復(fù)上述過(guò)程，直到集合V 中全部頂點(diǎn)加入到集合S中。程序設(shè)計(jì):程序設(shè)計(jì)目的：應(yīng)用數(shù)據(jù)結(jié)構(gòu)相關(guān)知識(shí)模擬一個(gè)新型網(wǎng)絡(luò)系統(tǒng)，滿足以下基本要求。.設(shè)置感測(cè)器數(shù)目數(shù)據(jù)收集器坐標(biāo)Co

6、llector，基本要求：在單機(jī)上模擬Sensor network的工作。用 VC+ (C也可以)實(shí)現(xiàn)模擬系統(tǒng)，N個(gè)Sensor和1個(gè) Data 其具體位置隨機(jī)確定，Interest Area就是屏幕。N可配置，缺省為100。Sensor進(jìn)行周期性采集，其采集周期可配置。Sensor的廣播半徑固定，也是可配置的參數(shù)。 路由算法自行選擇或設(shè)計(jì)顯示隨機(jī)分布 的感測(cè)器信息程序運(yùn)行流程圖：(右側(cè))本程序?yàn)閃in32控制臺(tái)程序，采用菜單驅(qū)動(dòng)，屏幕輸出結(jié)果設(shè)置感測(cè)器通信半徑 數(shù)據(jù)收集周期確定 收集器坐標(biāo)輸入數(shù)據(jù)收集器編 號(hào)及數(shù)據(jù)收集次數(shù) 并確定顯示各感測(cè)器 (包括收集器)之 間的路由信息周期性顯示連接中感

7、測(cè)器收 集的信息注：二和二:，分別表示手動(dòng)輸入信息并確定和相關(guān)信息的屏幕顯示。自定義數(shù)據(jù)類型:struct nodeint start;int end； double len； node* next;；路徑起點(diǎn) 路徑終點(diǎn) 打路徑長(zhǎng)度 stnict s 佇口rIkit r;傳感器在區(qū)域中的行號(hào)int c-傳感器在區(qū)域中的列號(hào)int data;_/_/收集的數(shù)據(jù)intno;傳感器編號(hào)int Hag;標(biāo)記clas s LinkNo de /7 鏈?zhǔn)疥?duì)列ptlvate：double *Gr4h；n*a的二維數(shù)組作為有權(quán)圖空間int pointnum;/頂 點(diǎn)教目double* Path_cost；/有

8、權(quán)邊int pathc;/有杈邊的數(shù)目public:MGr棗h( int size);triend void ShortPathlGraph g, int point,sen* data);/Dijkstra算法void BuildGraph( int size);創(chuàng) 建 有權(quán)圖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入隊(duì)sen&delque(); /7 出對(duì)class SensorWorKpublic：sen ;inr radius; 通信半徑LiiikNode P；口2畔Ep ;/7指示偉感囂互凝情況用以建立圖的有權(quán)邊ZMGraph mg;private：int r;im匚；收集器的坐標(biāo)int stime；inr size；inr sennum； /_/傳感舞的數(shù)目即圖出預(yù)點(diǎn)個(gè)數(shù))public：SensorWorK-f int 睛nnum);-S ens orWo rk-f ) sen* SetSensor-.i _/ x./ / ril tf

10、a 隹類關(guān)系圖:注:Area為結(jié)構(gòu)體數(shù)組，表示感測(cè)區(qū)域；p為鏈?zhǔn)疥?duì)列；sp用于指示感測(cè)器之間互聯(lián)的情況，并以此建立圖 的有權(quán)邊邊集；mg為MGraph的一對(duì)象，主要實(shí)現(xiàn)Dijkstra算法。核心算法：由二維數(shù)組創(chuàng)建圖的有權(quán)邊算法：該算法為“以二維數(shù)組(區(qū)域)中某元素(感測(cè)器)為起點(diǎn)，且遵循感測(cè)器的通訊半徑來(lái)最大化遍歷數(shù)組元 素(感測(cè)器)，同時(shí)建立與之相對(duì)應(yīng)的圖的有權(quán)邊邊集的問(wèn)題”提供了解決方案。結(jié)構(gòu)體二維數(shù)組中非-1的元 素代表感測(cè)器編號(hào)(感測(cè)器的位置在程序運(yùn)行時(shí)動(dòng)態(tài)確定)void S ensorWork: Cost_path(st, int sLinkN cxle &p)1 if(&t=NU

11、LL)判斷是不是隊(duì)列以空！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)控制列方向在區(qū)域內(nè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收集器無(wú)法找到傳感落”&口； retuui; . . _. _return Cost_path(P.delque( this- radius,P)；Dijkstra最短路徑算法：V如果收集器周國(guó)沒(méi)有傳感器 失靈h g, ini: p,su口* data)int sizesize =g.pointaum;double *dist = new doublesize;string *path = new stringsize;string *pset new stringsize;/data

13、顯示連擺著的傳感器數(shù)據(jù)存放源點(diǎn)p傳感器編號(hào))到各點(diǎn)的距離，記為無(wú)窮運(yùn)(不連通)存放路徑，記錄已經(jīng)選取過(guò)的結(jié)點(diǎn)for(int 1=。； i +g.Poiit(i elsePa由=”；如果路徑不是無(wú)窮大，path|i+便存儲(chǔ)該路徑名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記錄已經(jīng)選取過(guò)的結(jié)點(diǎn)/當(dāng)終點(diǎn)集合中的預(yù)點(diǎn)數(shù)小于K中的頂點(diǎn)數(shù)時(shí)循環(huán))找出dist

14、中蠢小值，k為最小值下標(biāo)fishort_dist = distm;k =m;if( disti = 0)該傳感器不在有效通信范國(guó)，失去連接！elsefoi(int di=0; di size； di+ )for-fint dj =0; djsize； dj+ )if( dat3didj.no=k)輸出路徑長(zhǎng)廢，路由路徑，感測(cè)器數(shù)據(jù)ffcout配tw(5)distk pathk dat3didj.dataendl;goto lable 1;lablel:psetnum+ = g.Poiat(k);將新產(chǎn)生的路徑的終點(diǎn)加入到集合中-同時(shí)將該終點(diǎn)做上標(biāo)記foi(int j=0; j (distk+喜Gr3phkj)/當(dāng)p-j的距離大于p-Ak + k-j的寤離時(shí)作改變1 distj = distk +昏 GraphMi； pathj； =pa由distk = 0;部分源代碼：感測(cè)器周期性數(shù)據(jù)收集：void SensorVf orkLzDela?；.-；Sleep( stime); Colle ctDat3();void SensorWork:：CollectData)V冏期挫收集數(shù)據(jù)for(iat i=0; isize； i+ )rj=。； jsize； j+ )rif( ArealC+程序設(shè)計(jì)教程作者:錢能清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)（C+ +版）作者:王紅梅清華大