最短路徑算法之無線路由器應用模擬設計報告

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

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

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

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

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

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

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

8、權邊int pathc;/有杈邊的數(shù)目public:MGr棗h( int size);triend void ShortPathlGraph g, int point,sen* data);/Dijkstra算法void BuildGraph( int size);創(chuàng) 建 有權圖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； /_/傳感舞的數(shù)目即圖出預點個數(shù))public：SensorWorK-f int 睛nnum);-S ens orWo rk-f ) sen* SetSensor-.i _/ x./ / ril tf

10、a 隹類關系圖:注:Area為結構體數(shù)組，表示感測區(qū)域；p為鏈式隊列；sp用于指示感測器之間互聯(lián)的情況，并以此建立圖 的有權邊邊集；mg為MGraph的一對象，主要實現(xiàn)Dijkstra算法。核心算法：由二維數(shù)組創(chuàng)建圖的有權邊算法：該算法為“以二維數(shù)組(區(qū)域)中某元素(感測器)為起點，且遵循感測器的通訊半徑來最大化遍歷數(shù)組元 素(感測器)，同時建立與之相對應的圖的有權邊邊集的問題”提供了解決方案。結構體二維數(shù)組中非-1的元 素代表感測器編號(感測器的位置在程序運行時動態(tài)確定)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)控制列方向在區(qū)域內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、顯示連擺著的傳感器數(shù)據(jù)存放源點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記錄已經選取過的結點/當終點集合中的預點數(shù)小于K中的頂點數(shù)時循環(huán))找出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)輸出路徑長廢，路由路徑，感測器數(shù)據(jù)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;部分源代碼：感測器周期性數(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ù)結構（C+ +版）作者:王紅梅清華大