模擬Flooding或Broadcast |
答題得分者是:Coffee
|
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
環境為一個Sensor Network,共有4000個nodes。
struct Node_Attribute //node information { int Node_ID; // Node id int coordinate_x; // Node x 座標 int coordinate_y; // Node y 座標 int root_ID; // Network 的 root bool isRoot; // 目前的Node是否為root int min_hop_count_to_root; // 最後到達root最小的hop count int local_min_hop_count_to_root; // 目前所記錄到達root最小的hop count struct Node_Attribute *Neighbor; // Node i 的 neighbor int Neighbor_Number; // Node i 的 neighbor 數目 }; 所有的node都是random產生。假設我取最左上角的node為root,即 x、y 座標最小者。 現在我想從root開始傳送訊息(Flooding),直到所有的node都收到自root傳來的訊息,藉此計算每個node到達root所需的距離(hop count)。 原理是,root傳送訊息給他的neighbor,再由neighbor傳送給他的neighbor如此傳送下去。 但是我不知道怎麼寫比較好,一開始的想法是用for loop,但是這樣只能考慮root往下傳的那一層。再繼續下去還要再寫一個for loop。 主要是因為我傳送下去並不是按照node產生的順序,而是他的neighbor,因此從for loop還要額外定義一個 類似 int *root_neighbor_id; root_neighbor_id=new int[Node[Root_ID].Neighbor_Number]; 然後 for(int i=0;i Node[Root_ID].Neighbor[i].min_hop_count_to_root=1; root_neighbor_id[i]=Node[Root_ID].Neighbor[i].Node_ID; Image1->Canvas->Font->Color=clRed; Image1->Canvas->TextOutA(Node[Root_ID].Neighbor[i].coordinate_x,Node[Root_ID].Neighbor[i].coordinate_y,"."); } for(int i=0;i for(int j=0;j Node[root_neighbor_id[i]].Neighbor[j].local_min_hop_count_to_root=Node[root_neighbor_id[i]].min_hop_count_to_root 1; //距離root的距離=前一個距離 1 Image1->Canvas->TextOutA(Node[Root_ID].Neighbor[i].coordinate_x,Node[Root_ID].Neighbor[i].coordinate_y,"."); } } 接下來我就不知道該怎麼做才好了。 請問有什麼比較好的方法嗎?謝謝 |
Coffee
版主 發表:31 回覆:878 積分:561 註冊:2006-11-15 發送簡訊給我 |
Recursive Forest Travel?
單考慮一個Node,先Travel同一個方向,比如向左,利用Recursive function fTravel 先看最左邊,若最左的chile node不是leaf,那麼就把這個Node當成你的RootNode繼續看 //此時這個函式沒有結束,只是再一次呼叫自己 這個函式fTravel已經被呼叫到第n層時,發現最左邊為一個leaf//也就是它沒有child node 就處理這個leaf,然後這個函式會結束,也就是結束第n階的fTravel, 這時會回到n-1 fTravel,這個fTravel已經處理完child node,繼續看第二個node是否是leaf, 是就處理,不是就往下一層,直到有leaf出現並處理,直到n-1階的fTravel結束,會回到n-2階 不過recursive的問題是最大一千個階層,因為你有4000個node,處理這個要小心 改成迴圈不是很好寫
------
不論是否我發的文,在能力範圍皆很樂意為大家回答問題。 為了補我的能力不足之處,以及讓答案可以被重複的使用,希望大家能儘量以公開的方式問問題。 在引述到我的文時自然會儘量替各位想辦法,謝謝大家! |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
氣死人,打了老半天,結果不知道為什麼重整網頁,一切要重來
謝謝你的提醒,我之後有想到是否可以用遞迴的方式。 關於你的演算法我不是很清楚。我猜測是否要將node與neighbor的關係轉換成tree,但是照你的方法我想會有個問題,就是當p1是p2的neighbor,同時間p2也是p1的neighbor,這樣的tree好像會導致cycle,還有就是,因為事先不知道每個node的neighbor數,因此每個node的child數目也要動態產生,這樣的tree structure好像有點複雜,直觀來看,我不知道怎麼表示某一個node的所有child,本來像是binary可以用left & right,但是在這裡我就不知道要怎麼表示才好了。 我又想了一個偷懶的方法,我想了想應該可行: 例如,有10個node的network。如下圖,其中n8為root。(ps.相對的距離先不管,因為是用小畫家畫的,有點難畫) 接著根據neighbor建立成以下的tree structure: 然後從最上層開始往下trace。越上層表示hop count越小,因此只要把尚未加入到hop count table的node逐一加入,如紅色圈出來的部分。 若root n8的hop count=0 則 n7、n0、n6的hop count=1 n1、n2、n4、n9的hop count=2 n3、n5的hop count=3 如此就可以找出所有node的min hop count。 ===================引 用 文 章=================== Recursive Forest Travel? 單考慮一個Node,先Travel同一個方向,比如向左,利用Recursive function fTravel 先看最左邊,若最左的chile node不是leaf,那麼就把這個Node當成你的RootNode繼續看 //此時這個函式沒有結束,只是再一次呼叫自己 這個函式fTravel已經被呼叫到第n層時,發現最左邊為一個leaf//也就是它沒有child node 就處理這個leaf,然後這個函式會結束,也就是結束第n階的fTravel, 這時會回到n-1 fTravel,這個fTravel已經處理完child node,繼續看第二個node是否是leaf, 是就處理,不是就往下一層,直到有leaf出現並處理,直到n-1階的fTravel結束,會回到n-2階 不過recursive的問題是最大一千個階層,因為你有4000個node,處理這個要小心 改成迴圈不是很好寫 |
Coffee
版主 發表:31 回覆:878 積分:561 註冊:2006-11-15 發送簡訊給我 |
跟你的很像,只不過你應該還記得Data Structure裡面對Tree的Travel吧?
所以Travel的順序會變成 8->7->0->4,這時候函式來到第四層,發現4為leaf,所以往上一層到0,因為左子樹已經結束,所以換右子樹,Travel 2 -> 5,5為leaf,處理完換2,又回到0, 這時候0的L, R都結束,回到0的上一層7,這時候7的L也結束了,換R -> 1以此類推 這樣函式就只要知道root跟它所有的child node就可以,不用立刻考慮child node是否是leaf 當然,狀況就跟你說的一樣,Path是不能有交錯的,否則會造成cycle,//不過也是有更偷懶的方法可以避免這個問題..:P 但如果會有這樣的問題,你可能就要考慮是否答案非唯一(會不會影響到你的目的),如果要最短路徑,可能就要想一下尤拉,畢竟現在畫出來的只有10個node..:P
------
不論是否我發的文,在能力範圍皆很樂意為大家回答問題。 為了補我的能力不足之處,以及讓答案可以被重複的使用,希望大家能儘量以公開的方式問問題。 在引述到我的文時自然會儘量替各位想辦法,謝謝大家! |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
|
Coffee
版主 發表:31 回覆:878 積分:561 註冊:2006-11-15 發送簡訊給我 |
看你用什麼當key,在建Tree的時候加入table,並對將要拜訪的node查詢是否在table上,是就跳過,這樣你就可以在Travel的時候delete item,不在table上的就是travel過的,剛好一建一刪來確保你的node剛好全部都travel
除非你一定要求最短距離,不然Travel的方法可以仿照我說的方式就執行就可以
------
不論是否我發的文,在能力範圍皆很樂意為大家回答問題。 為了補我的能力不足之處,以及讓答案可以被重複的使用,希望大家能儘量以公開的方式問問題。 在引述到我的文時自然會儘量替各位想辦法,謝謝大家! |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
你好,其實我要做得有點類似shortest path,因為要找出min hop count,若node接收到兩個以上來自他的neighbor傳來的距離root的距離。
例如:(第一張圖) 收到n0會收到n8跟n7的訊息。其中n8送出的訊息會告訴n0距離root只有一步距離,但是n7告訴n0距離root有兩步距離,因此他就要判斷最短的是哪一個。 因此,(第二張圖中)才會有n0不只出現一次。我有考慮過用table去查詢,但是這樣無法保證收到的是最短的距離。 不好意思,一開始沒說明清楚。 ===================引 用 文 章=================== 看你用什麼當key,在建Tree的時候加入table,並對將要拜訪的node查詢是否在table上,是就跳過,這樣你就可以在Travel的時候delete item,不在table上的就是travel過的,剛好一建一刪來確保你的node剛好全部都travel 除非你一定要求最短距離,不然Travel的方法可以仿照我說的方式就執行就可以 |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
|
Coffee
版主 發表:31 回覆:878 積分:561 註冊:2006-11-15 發送簡訊給我 |
type TNode = class
NodeID : integer; NodeStep : integer; ParentNode : PNode; function getChildNodes : array of PNode;//取得Node的所有child node end; type PNode = ^TNode;//就是一個TNode type的指標型態 funciton RTravel(PNode); var ChildeNodes : array of TNode; ind : integer; begin ChildNodes := PNode^.getChildNodes; PNode^.NodeStep:=PNode^.NodeSep 1;//預設nodestep為0,先加之後再減回來 if Length(ChildNodes)>0 then //判斷是否有child node for ind:=0 to Length(ChildNodes)-1 do //依次拜訪child begin if (ChildNodes[ind].NodeStep=0) or (ChildNodes[ind].NodeStep>=PNode^.NodeStep) then begin //如果child 未被拜訪過,或者是child的上一次演算路徑過長,就把child的parent改成自己 ChildNodes[ind]=PNode; ChildNodes[ind].NodeStep=PNode^.NodeStep; end; RTravel(ChildNodes[ind]); end; PNode^.NodeStep:=PNode^.NodeStep-1; end; 這樣的想法應該OK?不過先決條件應該是Network本身是單向的.. 如果是雙向那麼就要另外加一個Table去列cycle path 這個Travel完之後,每個Node會決定自己的上一個Node是誰(才是最短的) 而NodeStep將會包含min count 如果需要實際路線,就再用另外一個recursive function去找childnode的parent是自己的往下走就可以了 我想你應該是用C 寫,不過我懶得想C 怎麼寫了,就把這個當虛擬碼吧XD
------
不論是否我發的文,在能力範圍皆很樂意為大家回答問題。 為了補我的能力不足之處,以及讓答案可以被重複的使用,希望大家能儘量以公開的方式問問題。 在引述到我的文時自然會儘量替各位想辦法,謝謝大家! |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
我最後用的方法是這樣:
void Flooding(int ParentID) { int parentHC=Node[ParentID].min_hop_count_to_root; int childHC; for(int i=0;i childHC=parentHC 1; if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root <= childHC) { if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root != -1) Node[ParentID].Neighbor[i].stop=true; else { Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root=childHC; Flooding(Node[ParentID].Neighbor[i].Node_ID); } } if(Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root > childHC) { Node[Node[ParentID].Neighbor[i].Node_ID].min_hop_count_to_root=childHC; Flooding(Node[ParentID].Neighbor[i].Node_ID); } } } |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
上圖是我做出來的Shortest Path Tree。紅色的點是root 在建立之前,每個node如果可以互相通訊,我就把距離設定為1。 因此建立出來的Tree每段path的cost都是1 目前有一個問題,由上面的圖形可以大概看出,被藍色的線區分為幾個sub-tree,因為我是用遞迴的方式去travel,因此做出來的tree會有點像是Deep first search的樣子。 但是這樣做出來跟我想像的不太一樣,我希望他是root開始,有點像是同時broadcast,逐漸往外。 我所希望的是應該只有最右邊的藍線而不是出現右邊的那兩條藍線。 因為昨天開始熬夜寫這個,頭腦已經開始不太清楚了。如果我有觀念不對希望可以提醒我一下。 現在我有點懷疑我做出來的會不會不是shortest path tree。 我會這樣懷疑是因為,這是我實作一篇paper的程式,我要找出最右邊那條藍線的周圍node的最近的共同ancestor, 根據paper的說法是,在最右邊藍線周圍的node (在一開始的時候必須就是neighbor),最近的共同ancestor應該很遠(有個threshold), 而其他地方的node (在一開始的時候必須就是neighbor) 相對之下沒這麼遠,藉此找出藍色這個邊界。 但是,由圖中可以看出,右邊的tree像是細長型的,兩個sub-tree很接近,若在這兩個sub-tree各取一個node (在一開始的時候必須就是neighbor) , 則他們的共同ancestor,仍然距離很遠,跟我想像的完全不一樣。 這個問題是我最後才發現的,昨天寫了一整天都以為是我在判斷最近的共同ancestor寫錯了,看來好像是我的shortest path tree建立就有問題了。 麻煩各位幫我看一下,我在猜是不是我想法錯了。謝謝 |
Coffee
版主 發表:31 回覆:878 積分:561 註冊:2006-11-15 發送簡訊給我 |
關於這個,我今天想了一下,我認為我自己的travel方式是DFS,而且從一開始就是DFS
這是為了簡單的確保所有node會被travel且朝容易解決cycle的方向描述的, 但是我想了一下,我的DFS因為會自己決定上一個node是誰才會離root比較近 所以travel完畢應該不會有不是shortest path的問題, 但是有一個可能性,就是原先的shortest path如果只是單單參照DFS的方式, 可能會忽略cycle path的shortest path的可能,這點我沒有很仔細的去驗證,所以先提出假設 我不知道你的會不會,但我想我上面寫的因為沒有考慮cycle path而不走,所以可以試著用那樣的方式去跑跑看 檢查是否經過這個node之前所用的root到這個node所經過的node時就停掉它就好了//因為最短路徑不可能是走了一圈之後再從root出發會比較快
------
不論是否我發的文,在能力範圍皆很樂意為大家回答問題。 為了補我的能力不足之處,以及讓答案可以被重複的使用,希望大家能儘量以公開的方式問問題。 在引述到我的文時自然會儘量替各位想辦法,謝謝大家! |
GGL
資深會員 發表:104 回覆:600 積分:335 註冊:2006-11-05 發送簡訊給我 |
我在求shortest path的做法是:
先從root broadcast,然後他的neighbor紀錄hop count=1, 如此傳下去,如果同一個點收到兩個以上的hop count,就取最小的那個,同時紀錄是由哪個點傳來的。 所以我建立shortest path tree的方式是,把所有點所紀錄造成最小hop count的點都連起來,就形成上述的圖形。我認為這樣好像就是shortest path tree。 我驗證過edge數目,沒有cycle的情形發生,且剛好符合tree的條件。 我是在想,因為點數很多,而且每個點的neighbor我算過大約是10 (藉由調整通訊範圍來調整degree ) ,因此shortest path tree應該不是唯一的。 只是這樣做出來的結果跟我想像的差距太大。星期二就要給老師看了,看來只好暫時用作弊的方法了。我還想好好跨年 |
本站聲明 |
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。 2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。 3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇! |