臺灣博碩士論文加值系統

MANET 是很熱門的研究方向，其中又以制定其擇徑演算法，為最重要的目標之一。目前已有許多擇徑演算法陸續被提出，其中，On demand (例：AODV、DSR…)演算法，在探索路徑時皆採用氾濫式廣播(flooding)的方式；也就是說每一個節點在收到探索封包時，均會重播。這樣的行為不僅會消耗過多的電池電量，也會造成廣播風暴問題。
為了解決廣播風暴問題，我們提出FARNO (Farther Node Only)演算法。其主要精神為：各節點在探索路徑時，以象限分成四分區，各象限指定一個在自己傳輸範圍內較遠的節點為轉送節點(forwarding node)，並令其重播RREQ。透過模擬，我們比較FARNO、AODV 與QDIR 的連線成功率、搜尋路徑時的廣播次數與碰撞次數、可用的路徑數量及其hop count。模擬數據顯示， FARNO 在絕大多數的項目中皆有較好的效果。

Routing is an important work for MANET (Mobile Ad-hoc Network).Many routing algorithms have been proposed. For the on demand (e.g.AODV、DSR…) protocols, route request (RREQ) packets are broadcast by each node to all neighbors to detect routes in the route discovery phase. Flooding these packets may create the “broadcast storm” which also results in extra power consumption.

To counter the broadcast storm problem, we propose a new algorithm named FARNO (FARther Node Only). Its principle is that only one farther node in each quadrant is designated to rebroadcast RREQ packets, rather than by flooding. We compare its performance with that of AODV and QDIR by evaluating connection set up ratio, number of RREQ, number of RREQ collisions, number of paths, and hop count of paths. Simulation results reveal that FARNO has better performance based on most of the metrics.

第1 章、 導論 ................................ 1
1.1 前言...................................... 1
1.2 研究動機.................................. 4
1.3 研究目的與方法............................ 5
1.4 論文架構.................................. 5
第2 章、 相關文獻探討 ........................ 7
2.1 MANET 擇徑演算法 ......................... 8
2.1.1 Table driven ........................... 8
2.1.2 On demand .............................. 8
2.1.3 Hybrid ................................ 10
2.1.4 Power-aware routing ................... 10
2.2 廣播時電池電量消耗過多....................12
2.3 廣播風暴問題............................. 13
2.4 解決廣播風暴問題的方法................... 15
第3 章、 FARNO routing algorithm............. 22
3.1 象限分區和指定轉送節點的方法............. 23
3.2 FARNO-RREQ 封包format ....................26
3.3 處理廣播封包的方法....................... 28
3.4 FARNO 工作程序說明 ...................... 31
第4 章、 模擬結果 ............................33
4.1 模擬環境................................. 33
4.2 第一類環境的模擬結果..................... 36
4.2.1 連線成功率............................. 36
4.2.1.1 連線成功的數量分佈................... 38
4.2.2 廣播RREQ 封包發生碰撞的次數 ........... 42
4.2.2.1 各節點發生碰撞的分佈情形..............43
4.2.3 廣播RREQ 封包的數量 ................... 45
4.2.4 RREQ 封包 hop count 的分佈情形 ........ 47
4.2.5 Source node 可用的路徑數量 ............ 50
4.3 第二類環境的模擬結果..................... 52
4.3.1 連線成功率............................. 52
4.3.2 廣播RREQ 封包發生碰撞的次數 ........... 55
4.3.3 廣播RREQ 封包的數量 ................... 57
4.3.4 RREQ 封包 hop count 的分佈情形 ........ 59
4.3.5 Source node 可用的路徑數量 ............ 65
4.4 Source-destination pair 的距離之影響 .... 69
4.4.1 連線成功率............................. 70
4.4.2 廣播RREQ 封包發生碰撞的次數 ........... 73
4.4.3 廣播RREQ 封包的數量 ................... 76
4.4.4 RREQ 封包 hop count 的分佈情形 ........ 80
4.4.5 Source node 可用的路徑數量 ............ 86
第5 章、 結論 ............................... 91
5.1 總結..................................... 91
5.2 未來工作................................. 93
參考文獻......................................94

[96 Johson] D. B. Johson and D. A. Maltz, “Dynamic source routing in ad hoc
wireless networks,” Mobile Computing, T. Imielinski and H. Korth,
eds., Kluwer, pp. 153-181, 1996.

[96 Toh] C. K. Toh , “A novel distributed routing protocol to support ad-hoc
mobile computing,” Proc. IEEE 15th Annual Int’l Phoenix Conf.
Com. and Commun., 1996, pp. 480-486.

[98 Das] S. R. Das, R. Castaneda, Jiangtao Yan, and R. Sengupta,
“Comparative performance evaluation of routing protocols for mobile
ad hoc networks,” Proc. 7th International Conference on Computer
Communications and Networks, pp. 153-161, 1998.


[98 Singh] S. Singh, M. Woo, and C. S. Raghavendra, “Power-aware routing in
mobile ad-hoc networks,” Proceedings of the 4th Annual
ACM/IEEE International Conference on Mobile Computing and
Networking, 1998.

[99 Elizabeth] E. M. Royer and Chai-Keong Toh, “A review of current routing
protocols for ad hoc mobile wireless networks, ”IEEE Personal
Communications, vol. 62, pp. 46-55, 1999.

[99 Perkins] C. E. Perkins and E. M. Royer, “Ad-hoc on-demand distance
vector routing,” Proc. 2nd IEEE Workshop on Mobile Com. Sys.
and Apps., 1999, pp. 90-100.

[99 Joa-Ng] M. Joa-Ng and I. Lu, “A peer-to-peer zone-based two-level link
state routing for mobile ad hoc networks,” IEEE Journal on
Selected Areas in Communications, vol. 17, pp. 1415-1425, 1999.

[00 Heidemann] Y. Xu, J. Heidemann and Deborah Estrin, “Adaptive
energy-conserving routing for multihop ad hoc networks,”
USC-ISI Research Report 527, 2000.

[00 Ramanathan] R. Ramanathan and R. R. Hain, “Topology control of
multihop wireless networks using transmit power
adjustment,” IEEE Proceedings of Infocom, vol. 2, 2000, pp.
26-30.

[01 Perkins] C. E. Perkins, “Ad-hoc Networking,” Addison-Wesley
Professional, 2001.

[01 Heidemann] Y. Xu, J. Heidemann and D. Estrin, “Geography-informed
energy conservation for Ad Hoc routing,” Proceedings of the
7th Annual ACM Mobicom, 2001, pp. 70 - 84.

[01 Toh] C. K. Toh, “Maximum battery life routing to support ubiquitous
mobile computing in wireless ad-hoc networks,” IEEE
Communications Magazine, vol. 39, no. 6, pp. 138-147, 2001.

[03 Clausen] T. Clausen et al, “Optimized link state routing protocol,” Proc.
IETF Internet Draft,2003.

[06 曾] 曾煜棋, 潘孟鉉and 林致宇 “無線區域及個人網路, ”acore,2006.

[07 A. Latiff] L. A. Latiff, A. Ali, N. Fisal, ”Power reduction quadrant-based
directional routing protocol (Q-DIR) in Mobile Ad Hoc
Network,” Proceedings of the 2007 IEEE International
Conference on Telecommunications and Malaysia International
Conference on Communications, 2007, pp. 208 - 213.

[07 Esieh] Ping-En Esieh, ”Routing Method for Ad Hoc Networks –
Considering Temperature and Remaining Power,” 國立宜蘭大學
電子工程學系96 碩士論文。

[07 Wang] H. C. Wang and Y. H. Wang, “Energy-Efficient Routing Algorithms
for Wireless ad-hoc Networks,” Proc. 18th IEEE PIMRC (2007),
2007, pp. 1 - 5.

[08 Majumder] K. Majumder, S. K. Sarkar, “Multi-level location information
based routing for mobile ad hoc networks,” TENCON 2008 -2008,
TENCON 2008. IEEE Region 10 Conference, 2008, pp.1 - 6.

[09 Latiff] L. A. Latiff, N. Fisal, S. S. Ariffin, “Simulation of Position-Based
Routing Protocol in Wireless Mobile Ad Hoc Network,” Modelling
& Simulation, 2009. AMS '09. Third Asia International Conference,
2009, pp. 292 - 297.