簡介本資源面向無線傳感器網(wǎng)絡(luò)WSN方向的本科生、研究生及科研初學(xué)者聚焦路徑規(guī)劃與路由算法仿真以Dijkstra最短路徑算法為核心結(jié)合隨機路點RWP移動模型模擬動態(tài)拓?fù)湎碌墓?jié)點通信場景解決能量感知路由與網(wǎng)絡(luò)生命周期優(yōu)化問題。壓縮包共33個文件含20個MATLAB數(shù)據(jù)文件.mat用于存儲各算法在不同指標(biāo)如剩余能量AvgEc、存活節(jié)點數(shù)Alivenodes、吞吐量Throughput下的仿真結(jié)果7張JPG圖像為關(guān)鍵運行效果圖直觀呈現(xiàn)路由路徑、能量衰減趨勢與網(wǎng)絡(luò)連通性變化5個核心M腳本如DjisktraRoute.m、Energyfun.m、mainTest.m構(gòu)成完整仿真流程另含說明文檔txt提供參數(shù)配置與運行指引。資源體積僅169KB結(jié)構(gòu)緊湊、開箱即用。已有137人下載學(xué)習(xí)可直接復(fù)現(xiàn)Dijkstra路由與Modified LEACH、CORPACO等主流協(xié)議的性能對比實驗快速掌握WSN仿真建模與算法評估方法。路徑規(guī)劃實戰(zhàn)Matlab實現(xiàn)Dijkstra算法的無線傳感器網(wǎng)絡(luò)路由模擬做無線傳感器網(wǎng)絡(luò)WSN仿真的同學(xué)對節(jié)點移動這個場景應(yīng)該都不陌生。傳感器節(jié)點一旦動起來網(wǎng)絡(luò)拓?fù)渚透兟酚蓻Q策就得重新做。這個項目做的就是一件事在節(jié)點隨機移動的傳感器網(wǎng)絡(luò)里用Dijkstra算法動態(tài)計算最優(yōu)路徑并且用隨機路點運動模型來模擬節(jié)點的真實移動行為整套東西用Matlab跑通。適合正在做WSN仿真、路由算法驗證或者畢業(yè)設(shè)計需要出圖出數(shù)據(jù)的讀者參考。這套代碼的核心價值在于它把移動模型和路由算法兩個獨立模塊組裝在了一起節(jié)點每移動一步拓?fù)渚退⑿乱淮温酚梢哺履隳芎苤庇^地看到不同時刻網(wǎng)絡(luò)路徑的變化。比靜態(tài)拓?fù)浞抡嬉咏鎸崍鼍暗枚喽襇atlab的可視化能力讓結(jié)果展示非常直觀跑完一遍基本就能把Dijkstra在WSN里的應(yīng)用邏輯理清楚。下面我把這個項目的設(shè)計思路、核心實現(xiàn)、完整流程和踩坑經(jīng)驗一次講透。1. 項目拆解我們要用Matlab解決什么問題1.1 無線傳感器網(wǎng)絡(luò)路由從一堆節(jié)點到一條最優(yōu)路徑無線傳感器網(wǎng)絡(luò)由大量能量受限、計算能力有限的微型節(jié)點組成節(jié)點通過無線通信協(xié)作完成數(shù)據(jù)采集和傳輸。路由問題說白了就是源節(jié)點要把數(shù)據(jù)送到匯聚節(jié)點sink中間可能隔著很多跳怎么走最劃算在動態(tài)網(wǎng)絡(luò)里這個問題又多了一層麻煩。節(jié)點一旦移動本來連得上的鄰居可能就斷了本來最短的路徑可能繞了遠(yuǎn)路。所以路由算法必須跟著拓?fù)鋵崟r變化。這個項目用Dijkstra算法來解決最短路徑問題用隨機路點運動模型來制造拓?fù)鋭討B(tài)變化兩者結(jié)合就能模擬出一個移動中持續(xù)路由的完整過程。這個場景對應(yīng)很多真實需求野外環(huán)境監(jiān)測中移動動物身上的傳感器、自動駕駛車隊之間的通信、無人機編隊的路由維護本質(zhì)都是節(jié)點在動、鏈路在變、路由要跟上。1.2 為什么選Dijkstra它憑什么當(dāng)路由算法的主角Dijkstra算法是經(jīng)典的單源最短路徑算法貪心策略每次選距離起點最近的未訪問節(jié)點然后做松弛操作。它的適用范圍是權(quán)重非負(fù)的圖而WSN里的邊權(quán)通常是距離或能耗天然非負(fù)所以完全匹配。在WSN路由中選Dijkstra還有一個現(xiàn)實原因大量實際路由協(xié)議本身就是基于Dijkstra思想設(shè)計的。比如OSPF路由協(xié)議每個路由器維護全網(wǎng)的鏈路狀態(tài)數(shù)據(jù)庫再用Dijkstra計算到所有目的地的最短路徑樹。你把這個機制縮小到傳感器網(wǎng)絡(luò)里邏輯一模一樣。所以先掌握Dijkstra的實現(xiàn)后面理解真實路由協(xié)議會非常順暢。更有意思的是Dijkstra的代價函數(shù)可以靈活替換。默認(rèn)用距離做權(quán)重改成績效函數(shù)就能實現(xiàn)最小跳數(shù)路由、最低能耗路由、最大化最小剩余能量路由等變體。這個項目的擴展性就在這里——換一個權(quán)重定義算法框架完全不用動路由策略就變了。1.3 隨機路點運動模型讓網(wǎng)絡(luò)活起來隨機路點運動模型Random Waypoint Model是移動自組網(wǎng)仿真中最常用的移動模型之一。每個節(jié)點隨機選一個目標(biāo)位置、隨機選一個移動速度勻速朝目標(biāo)移動到達(dá)后暫停一段時間再重復(fù)這個過程。為什么要用這個模型因為它在統(tǒng)計學(xué)上已經(jīng)被研究得很透徹并且實現(xiàn)簡單、參數(shù)直觀適合作為WSN動態(tài)路由仿真的默認(rèn)選擇。你可以控制移動速度的范圍來模擬步行傳感器、車載傳感器等不同場景也可以通過暫停時間參數(shù)模擬采集數(shù)據(jù)時停一下的行為。但這里有個很隱蔽的坑我后面專門講——隨機路點模型有個速度衰減現(xiàn)象會導(dǎo)致節(jié)點平均速度隨時間推移持續(xù)下降。如果不處理你的仿真可能跑著跑著所有節(jié)點都像蝸牛一樣慢慢爬了。1.4 整體仿真流程怎么設(shè)計這個項目的整體流程可以分成六步在指定區(qū)域內(nèi)隨機撒N個節(jié)點初始化位置和速度每個時間步內(nèi)按隨機路點模型更新所有節(jié)點的位置根據(jù)節(jié)點間距和通信半徑重建網(wǎng)絡(luò)拓?fù)渖舌徑泳仃囋诟潞蟮耐負(fù)渖线\行Dijkstra算法計算源節(jié)點到匯聚節(jié)點的最短路徑記錄當(dāng)前路徑的跳數(shù)、總距離、路由計算耗時等指標(biāo)移動下一個時間步重復(fù)2-5步直到仿真結(jié)束最后把所有指標(biāo)畫出來。這個流程的精髓是每個時間步都完全刷新不是只在開頭算一次路徑然后整場不變。這樣你能看到節(jié)點移動如何影響路由決策以及算法如何快速響應(yīng)拓?fù)渥兓?。日志曲線一畫出來整個過程一目了然。2. 核心算法與模型實戰(zhàn)Dijkstra與隨機路點的Matlab實現(xiàn)2.1 Dijkstra算法原理從城市導(dǎo)航到網(wǎng)絡(luò)路由Dijkstra的原理可以用一句話概括逐步擴展已知最短路徑的節(jié)點集合。想象你在城市地圖上從家出發(fā)找去火車站的最短路線你先看家附近的路口找到最近的再從這個路口繼續(xù)向外擴展每次都能確定一個新的最近節(jié)點的最短路徑。這個過程持續(xù)下去直到目標(biāo)節(jié)點被確定。在WSN路由里城市地圖變成了網(wǎng)絡(luò)拓?fù)鋱D路口變成了傳感器節(jié)點路口的距離變成了節(jié)點間通信鏈路的權(quán)重。每個節(jié)點只能和通信半徑內(nèi)的鄰居直連其他節(jié)點要通過鄰居的鄰居間接到達(dá)。目標(biāo)就是找到源節(jié)點到匯聚節(jié)點總權(quán)值最小的那條鏈路序列。Dijkstra保證能找到全局最短路徑的前提是圖中所有邊的權(quán)值非負(fù)。傳感器網(wǎng)絡(luò)的鏈路權(quán)重如果定義為距離、能耗、時延之類的物理量天然滿足這個條件。這也是它比A更簡單A需要啟發(fā)式函數(shù)、比Bellman-Ford更適合Bellman-Ford處理負(fù)權(quán)但有額外開銷的原因。2.2 Matlab源碼逐段拆解一個能直接用的Dijkstra函數(shù)我擼了一個標(biāo)準(zhǔn)的Dijkstra函數(shù)輸入鄰接矩陣、源節(jié)點和目標(biāo)節(jié)點輸出最短距離和路徑節(jié)點序列。直接復(fù)制就能用function [dist, path] dijkstra_route(adj, src, dst) % adj: 鄰接矩陣adj(i,j)表示節(jié)點i到j(luò)的通信代價inf表示不可達(dá) % src: 源節(jié)點編號 % dst: 目標(biāo)節(jié)點編號 % dist: 源到目標(biāo)的最短距離 % path: 從源到目標(biāo)的節(jié)點序列不可達(dá)時返回空數(shù)組 n size(adj, 1); visited false(n, 1); % 是否已確定最短路徑 dist inf(n, 1); % 當(dāng)前已知最短距離 prev zeros(n, 1); % 前驅(qū)節(jié)點用于回溯路徑 dist(src) 0; for i 1:n % 在未訪問節(jié)點中找到距離最小的節(jié)點u min_dist inf; u -1; for j 1:n if ~visited(j) dist(j) min_dist min_dist dist(j); u j; end end if u -1 || u dst break; % 沒有可擴展節(jié)點或已經(jīng)到達(dá)目標(biāo) end visited(u) true; % 松弛操作嘗試從u出發(fā)更新鄰居v的最短距離 for v 1:n if ~visited(v) isfinite(adj(u, v)) if dist(u) adj(u, v) dist(v) dist(v) dist(u) adj(u, v); prev(v) u; end end end end % 回溯路徑 path []; if isinf(dist(dst)) return; % 目標(biāo)不可達(dá) end node dst; while node ~ src path [node, path]; node prev(node); if node 0 path []; return; end end path [src, path]; end幾個容易出錯的地方你重點看第一初始化prev為全零回溯時如果遇到prev(node)0說明路徑斷裂要返回空路徑。第二循環(huán)條件是1:n但實際最多n次就能結(jié)束因為每次確定一個節(jié)點提前到達(dá)目標(biāo)可以break省時間。第三鄰接矩陣對角線上的值應(yīng)該是inf因為節(jié)點不用自己連自己訪問到ij時dist(u)adj(u,v)會算出錯誤結(jié)果。這個版本是樸素實現(xiàn)復(fù)雜度O(n^2)。對于幾百個節(jié)點的WSN仿真完全夠用但如果網(wǎng)絡(luò)規(guī)模上千建議用優(yōu)先隊列優(yōu)化Matlab里可以用min-heap結(jié)構(gòu)或者直接調(diào)用java.util.PriorityQueue接口。2.3 隨機路點運動模型建模節(jié)點怎么動才真實隨機路點模型的核心邏輯是每個節(jié)點維護當(dāng)前坐標(biāo)、目標(biāo)坐標(biāo)、速度和暫停剩余時間四項狀態(tài)。我寫的這個函數(shù)每個時間步調(diào)用一次完成節(jié)點的位置更新function [pos, target, speed, pause_time] random_waypoint_move(pos, target, speed, pause_time, dt, area_size, min_speed, max_speed, max_pause) % area_size: [寬, 高]節(jié)點在矩形區(qū)域內(nèi)運動 % dt: 仿真時間步長 if pause_time 0 pause_time pause_time - dt; % 繼續(xù)暫停 if pause_time 0 % 暫停結(jié)束選新目標(biāo)和新速度 target rand(1, 2) .* area_size; speed min_speed rand * (max_speed - min_speed); end return; % 暫停期間位置不變 end direction target - pos; dist_to_target norm(direction); if dist_to_target 0.01 % 到達(dá)目標(biāo)進入暫停狀態(tài) target rand(1, 2) .* area_size; speed min_speed rand * (max_speed - min_speed); pause_time rand * max_pause; else step_len min(dist_to_target, speed * dt); pos pos direction / dist_to_target * step_len; end end這個函數(shù)有個細(xì)節(jié)計算步長時用min(dist_to_target, speed*dt)保證不會沖過目標(biāo)點。如果你讓節(jié)點直接移動speed*dt它可能會在目標(biāo)點附近來回抖動看起來非常假。初始化時每個節(jié)點在仿真區(qū)域內(nèi)隨機選一個位置隨機選一個初始目標(biāo)速度取min_speed到max_speed之間的均勻分布暫停時間初始為0。代碼可以這么寫node_num 50; area_size [100, 100]; min_speed 1; max_speed 5; max_pause 3; pos rand(node_num, 2) .* area_size; target rand(node_num, 2) .* area_size; speed min_speed rand(node_num, 1) * (max_speed - min_speed); pause_time zeros(node_num, 1);隨機路點模型的真實感主要取決于兩個參數(shù)速度范圍和暫停時間。速度太大會讓拓?fù)渥兓珓×衣窂絼偹阃昃褪和r間太短會讓節(jié)點像個沒頭蒼蠅一直亂竄。建議先跑一次預(yù)仿真觀察節(jié)點平均移動距離和拓?fù)渥兓l率再調(diào)整參數(shù)。2.4 通信鏈路構(gòu)建誰和誰才能搭上話有了節(jié)點坐標(biāo)接下來要構(gòu)建鄰接矩陣。傳感器節(jié)點的通信能力是有限的——只有落在通信半徑內(nèi)的節(jié)點才能直接通信。這個邏輯在Matlab里實現(xiàn)很直接function adj build_adjacency(pos, comm_range) node_num size(pos, 1); adj inf(node_num, node_num); for i 1:node_num for j i1:node_num d norm(pos(i, :) - pos(j, :)); if d comm_range adj(i, j) d; % 用歐氏距離作為鏈路代價 adj(j, i) d; end end end end注意這里矩陣對角線保持inf因為節(jié)點不需要自己通信。如果追求效率可以換成向量化寫法用pdist2一次性算出所有節(jié)點對的距離矩陣dist_matrix pdist2(pos, pos); adj inf(node_num, node_num); adj(dist_matrix comm_range) dist_matrix(dist_matrix comm_range);不過向量化版本會額外創(chuàng)建一個node_num x node_num的完整距離矩陣節(jié)點數(shù)很大的時候內(nèi)存占用翻倍。對于一千個節(jié)點以內(nèi)pdist2的寫法沒有問題如果節(jié)點再多建議用循環(huán)加dsearchn或者網(wǎng)格分塊來加速。鏈路代價用什么是個大學(xué)問。這個項目直接用歐氏距離代表通信能耗和距離成正比的簡化模型。你也可以改成跳數(shù)每條邊權(quán)值都設(shè)為1或者結(jié)合節(jié)點剩余能量做加權(quán)。Dijkstra算法本身不關(guān)心權(quán)值怎么來的反正只要是正的有限數(shù)就行。3. 完整仿真系統(tǒng)搭建從初始化到出結(jié)果3.1 參數(shù)配置這些數(shù)字背后都有講究我把仿真參數(shù)分成了三組網(wǎng)絡(luò)參數(shù)、移動參數(shù)、仿真控制參數(shù)。下面這張表是我調(diào)試后覺得比較合理的一組默認(rèn)值參數(shù)類型參數(shù)名稱默認(rèn)值說明網(wǎng)絡(luò)參數(shù)節(jié)點數(shù)50太少拓?fù)涮∈杼嘤嬎懵W(wǎng)絡(luò)參數(shù)通信半徑25約為仿真區(qū)域邊長的1/4網(wǎng)絡(luò)參數(shù)仿真區(qū)域100 x 100單位可以理解為米移動參數(shù)最小速度1保證節(jié)點不會完全靜止移動參數(shù)最大速度5常規(guī)步行/慢速車載速度移動參數(shù)最大暫停時間3單位秒模擬采集數(shù)據(jù)停頓仿真控制時間步長0.1越小運動越精確但計算量越大仿真控制總仿真時間100足夠看到多輪拓?fù)渥兓酚稍O(shè)置源節(jié)點編號1隨機選一個離sink遠(yuǎn)的節(jié)點路由設(shè)置匯聚節(jié)點編號node_num固定放在角落或中心通信半徑這個參數(shù)最敏感。半徑太大幾乎全網(wǎng)絡(luò)都直接互聯(lián)路由退化成單跳半徑太小網(wǎng)絡(luò)可能根本不連通路由經(jīng)常失敗。一個經(jīng)驗法則是讓平均鄰居數(shù)在5到10之間。對于100x100的區(qū)域撒50個節(jié)點、通信半徑25平均鄰居數(shù)大約在π×25^2×50/10000 ≈ 9.8個是比較健康的狀態(tài)。3.2 主循環(huán)結(jié)構(gòu)讓時間一步一步往前走主循環(huán)是整個仿真的心臟。每一輪做四件事移動節(jié)點、重建拓?fù)洹⒂嬎懵窂?、記錄?shù)據(jù)。偽代碼結(jié)構(gòu)如下% 初始化參數(shù) node_num 50; sink_id node_num; source_id 1; comm_range 25; total_time 200; dt 0.1; step_num round(total_time / dt); % 記錄變量 path_length_history zeros(step_num, 1); path_dist_history zeros(step_num, 1); route_fail_count 0; % 隨機路點模型狀態(tài) [area_size, min_speed, max_speed, max_pause] deal([100 100], 1, 5, 3); % 初始化節(jié)點狀態(tài)... for step 1:step_num % 1. 更新節(jié)點位置 for i 1:node_num [pos(i,:), target(i,:), speed(i), pause_time(i)] random_waypoint_move(... pos(i,:), target(i,:), speed(i), pause_time(i), dt, area_size, ... min_speed, max_speed, max_pause); end % 2. 重建鄰接矩陣 adj build_adjacency(pos, comm_range); % 3. 運行Dijkstra [dist, path] dijkstra_route(adj, source_id, sink_id); % 4. 記錄指標(biāo) if isempty(path) route_fail_count route_fail_count 1; path_length_history(step) NaN; path_dist_history(step) NaN; else path_length_history(step) length(path) - 1; % 跳數(shù) path_dist_history(step) dist; end end % 統(tǒng)計路由成功率 route_success_rate 1 - route_fail_count / step_num;有個思路要說一下我把Dijkstra失敗返回空數(shù)組當(dāng)成網(wǎng)絡(luò)不連通來處理而不是報錯。這在實際仿真中非常常見因為節(jié)點移動可能把網(wǎng)絡(luò)扯斷。單獨統(tǒng)計失敗次數(shù)最后算一個路由成功率比直接讓程序崩潰要合理得多。主循環(huán)還有個優(yōu)化空間拓?fù)渲亟ê虳ijkstra計算可以只在網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時才執(zhí)行而不是每步都跑。判斷方法很簡單比較前后兩個時間步的鄰接矩陣是否完全一致如果節(jié)點在暫停狀態(tài)、沒人移動拓?fù)渚蜎]變路由結(jié)果也不用重算。我實測過在暫停時間較長、節(jié)點數(shù)較多的情況下這種優(yōu)化能把計算時間省掉50%以上。3.3 結(jié)果可視化靜態(tài)節(jié)點和動態(tài)節(jié)點的路徑對比Matlab做仿真的最大優(yōu)勢就是可視化方便。我建議至少畫三張圖第一張是網(wǎng)絡(luò)拓?fù)浼赢?dāng)前路徑圖。用scatter畫節(jié)點位置用line畫出Dijkstra算出來的路徑把源節(jié)點和sink節(jié)點用不同顏色標(biāo)出來。再加一個標(biāo)題顯示當(dāng)前時間和跳數(shù)就能直觀看到路徑是怎么隨節(jié)點移動變化的figure(1); scatter(pos(:,1), pos(:,2), 30, filled, MarkerFaceColor, [0.3 0.6 0.9]); hold on; % 畫通信鏈路可選的節(jié)點多的話太亂 for i 1:node_num for j i1:node_num if isfinite(adj(i,j)) plot([pos(i,1) pos(j,1)], [pos(i,2) pos(j,2)], ... Color, [0.8 0.8 0.8], LineWidth, 0.3); end end end % 畫路徑 if ~isempty(path) plot(pos(path,1), pos(path,2), r-, LineWidth, 2); end plot(pos(source_id,1), pos(source_id,2), gs, MarkerSize, 10, MarkerFaceColor, g); plot(pos(sink_id,1), pos(sink_id,2), rp, MarkerSize, 12, MarkerFaceColor, r); hold off;第二張是路徑跳數(shù)和路徑總距離隨時間變化的曲線。你會看到路徑跳數(shù)在拓?fù)渥兓瘯r跳躍式改變非常有動態(tài)感。第三張是路由成功率或者平均路徑長度的統(tǒng)計直方圖用于總結(jié)整體性能。如果你希望做出更漂亮的動圖可以在主循環(huán)里用drawnow加pause(0.02)生成動畫效果。注意每隔一定幀數(shù)才刷新一次圖比如每20步畫一幀否則Matlab圖形刷新會成為最大的性能瓶頸。3.4 性能評估看什么路徑長度、能耗、成功率搭建完仿真系統(tǒng)后不能只跑個動畫就覺得完事了。要評估Dijkstra路由在這個移動網(wǎng)絡(luò)里表現(xiàn)如何我建議至少統(tǒng)計四個指標(biāo)路徑跳數(shù)反映路由的精簡程度。跳數(shù)越少每跳的轉(zhuǎn)發(fā)開銷越小但跳數(shù)少的代價是單跳距離可能較長通信能耗不一定最低。路徑總距離累計鏈路權(quán)值更接近真實能耗的量化指標(biāo)。路由成功率衡量網(wǎng)絡(luò)連通性和路由協(xié)議的健壯性節(jié)點移動導(dǎo)致網(wǎng)絡(luò)分裂時成功率會明顯下降。路由計算耗時衡量算法的實時性節(jié)點越多、拓?fù)湓矫芗臅r越長。所有這些指標(biāo)我都記錄在歷史數(shù)組里跑完后統(tǒng)一計算平均值、方差、最大最小值。你還可以設(shè)計一組對比實驗改變節(jié)點密度或移動速度觀察這些指標(biāo)怎么變。比如把最大速度從1改到20路徑跳數(shù)波動幅度會顯著增加路由成功率可能下降——這組數(shù)據(jù)能直接寫進論文或者項目報告里。4. 調(diào)試過程與避坑指南我踩過的那些坑4.1 Dijkstra實現(xiàn)里的三大經(jīng)典坑第一坑是初始化優(yōu)先級選錯節(jié)點。樸素Dijkstra在找距離最小的未訪問節(jié)點時如果初始所有dist都是inf第一個選出來的節(jié)點是源節(jié)點dist0這是對的。但如果代碼里把源節(jié)點的dist也初始化成inf整個算法就全亂了。檢查方法很簡單在循環(huán)開頭加一個斷言確保dist(src)0。第二坑是對角線權(quán)值沒設(shè)成inf。如果adj(i,i)0松弛階段會用dist(i)0更新自己雖然不會改變結(jié)果但多了一次無意義的遍歷。如果adj(i,i)被誤設(shè)成一個非零數(shù)比如不小心把adj(i,i)也按距離算進去了那就可能出現(xiàn)節(jié)點通過自己繞一圈反而更短的荒謬路徑。我的習(xí)慣是鄰接矩陣初始化為inf后只在i~j且距離小于通信半徑時填值。第三坑是回溯路徑時的邊界條件。如果目標(biāo)節(jié)點不可達(dá)prev(dst)一直是0回溯循環(huán)會陷入死循環(huán)或者返回錯誤路徑。在回溯前必須檢查isinf(dist(dst))如果不可達(dá)直接返回空數(shù)組。另外回溯時遇到prev(node)0也要立刻退出防止節(jié)點編號0被當(dāng)成合法節(jié)點。4.2 隨機路點模型的速度衰減問題這是我做這個項目時最頭疼的問題。隨機路點模型有個著名缺陷節(jié)點選擇的目標(biāo)位置如果是均勻分布那么節(jié)點在長時間運行后平均速度會持續(xù)衰減甚至?xí)吔诹?。原因是?jié)點在從區(qū)域一角移動到另一角時會有更大概率經(jīng)過區(qū)域中心附近區(qū)域?qū)е鹿?jié)點位置分布不均勻中心密度更高。更極端的是如果暫停時間和速度設(shè)置不當(dāng)節(jié)點可能在某個角落區(qū)域內(nèi)反復(fù)選擇很近的目標(biāo)點移動距離極短。表現(xiàn)出的現(xiàn)象是仿真跑到后期所有節(jié)點幾乎看不出在動路徑長時間不變化你以為是程序哪里卡死了。排查方法很簡單——統(tǒng)計每個節(jié)點的實際位移量并畫出來你會發(fā)現(xiàn)位移量在持續(xù)下降。解決方案有三個一是給速度設(shè)置一個下限比如最小速度不能小于最大速度的20%避免節(jié)點選擇極低速度。 二是選目標(biāo)點時排除太近的點要求新目標(biāo)點距離當(dāng)前位置至少是區(qū)域?qū)蔷€長度的10%確保移動有實際意義。 三是周期性重新撒點或者重新初始化節(jié)點的移動參數(shù)強行打破模型的自相關(guān)。我實測下來效果最好的是速度下限最近目標(biāo)距離限制組合簡單高效而且不會破壞模型的隨機性。4.3 Matlab仿真的性能瓶頸與優(yōu)化這套系統(tǒng)的性能瓶頸主要集中在三處鄰居發(fā)現(xiàn)的雙重循環(huán)、Dijkstra的O(n^2)選擇、圖形刷新。鄰居發(fā)現(xiàn)三重循環(huán)如果要優(yōu)化優(yōu)先用pdist2一次性算出距離矩陣。Dijkstra部分在節(jié)點數(shù)大于200時建議換成優(yōu)先隊列實現(xiàn)或者利用Matlab的graph對象和內(nèi)置的shortestpath函數(shù)做快速驗證。注意內(nèi)置shortestpath默認(rèn)用Dijkstra或Bellman-Ford可以直接對比你的手寫實現(xiàn)是否正確。圖形刷新這個問題最隱蔽。很多人喜歡在循環(huán)里用plot反復(fù)畫圖結(jié)果仿真時間90%都花在圖形渲染上。解決辦法是圖形更新頻率降低比如每50步畫一次或者先關(guān)閉圖形等仿真結(jié)束再用歷史數(shù)據(jù)一次性畫圖。還有一個優(yōu)化細(xì)節(jié)每次調(diào)用random_waypoint_move函數(shù)都會產(chǎn)生函數(shù)調(diào)用開銷節(jié)點多的時候這部分開銷也不小。可以把移動模型函數(shù)改成批量更新版本的代碼輸入所有節(jié)點的狀態(tài)矩陣輸出所有節(jié)點的新狀態(tài)利用Matlab的矩陣運算一次處理所有節(jié)點。這個優(yōu)化在節(jié)點數(shù)500以上時效果非常明顯。4.4 排查工具與方法讓問題現(xiàn)出原形碰到仿真結(jié)果不對的情況我的排查套路是小規(guī)模插樁調(diào)試。先把節(jié)點數(shù)改成10個通信半徑調(diào)大到足夠全連通跑幾秒仿真。然后每步把鄰接矩陣、dist數(shù)組、prev數(shù)組打印出來手工檢查幾個容易出錯的場景。具體來說我常用三個檢查手段第一檢查鄰接矩陣對稱性。正常情況下adj(i,j)adj(j,i)如果不等說明建圖階段有bug。第二檢查Dijkstra輸出的dist是否等于目標(biāo)節(jié)點的最短路徑和如果不等拿一條已知的路徑手工加起來比對。第三檢查路徑節(jié)點是否都相互連通路徑中相鄰節(jié)點之間的鏈路權(quán)值必須有限否則回溯邏輯有問題。如果懷疑是隨機路點模型的問題就單獨把移動模型拿出來跑只畫節(jié)點軌跡不跑路由?？窜壽E是否符合預(yù)期——節(jié)點應(yīng)該在你的區(qū)域內(nèi)分布不會飛出邊界暫停和移動交替出現(xiàn)。如果發(fā)現(xiàn)所有節(jié)點都停在某些位置不動那基本就是速度衰減或者目標(biāo)點在區(qū)域外的bug。我用這個分層排查的思路基本能把問題定位到具體函數(shù)。先隔離移動模型再隔離建圖最后才是路由算法一層一層剝開問題跑不掉。5. 擴展方向這個仿真系統(tǒng)還能怎么升級項目跑通后我強烈建議你做幾個方向的擴展性價比都很高。第一個是代價函數(shù)改造。把build_adjacency里的權(quán)值從距離改成距離×單位能耗或者考慮節(jié)點剩余能量就能把Dijkstra從最短路徑路由改造成最小能耗路由或能量均衡路由對比不同策略下的網(wǎng)絡(luò)壽命。第二個是引入更復(fù)雜的移動模型。比如Gauss-Markov模型或者Reference Point Group模型只需要替換random_waypoint_move函數(shù)即可仿真框架完全不用改。第三個是加入數(shù)據(jù)包級別的仿真。目前是每個時間步算一次路徑但沒有真正模擬數(shù)據(jù)包的逐跳轉(zhuǎn)發(fā)、排隊、丟包加進去就能統(tǒng)計端到端時延和丟包率。我個人的經(jīng)驗是這套代碼最大的價值不是實現(xiàn)了一個Dijkstra而是把移動模型、建圖、路由三個環(huán)節(jié)解耦了想改哪個模塊就改哪個模塊非常適合拿來做課程設(shè)計和論文仿真的實驗平臺。如果時間充裕還可以把結(jié)果導(dǎo)出來和真實路由協(xié)議比如AODV的仿真結(jié)果做對比分析集中式最短路徑和分布式路由的性能差異。最后說一個細(xì)節(jié)標(biāo)題里打的Djisktra其實是Dijkstra的手滑拼寫搜索或者寫文檔的時候用正確的拼寫不然容易找不到資料。這個坑雖然小但我還真見過有人因為拼寫錯誤在海量英文文獻里搜不到想要的內(nèi)容白白浪費時間。本文還有配套的精品資源點擊獲取