在車用行動通訊網路(Vehicular Ad-Hoc Network,VANET)中,由於車輛的移動速度比起傳統行動隨意網路(Mobile Ad-Hoc Network,MANET)的節點移動速度更快,流動性更高,網路拓樸變化更大,並且在車用行動通訊網路中,封包的傳遞範圍受限於道路的分布,容易造成整體網路的區域性,以致經常造成網路斷線,來源車輛要找到一條固定且穩固的路由(route)將封包(packet)傳送至目的車輛是不容易的,路由容易因為車輛變換方向與位置而無法維持,封包因此大量地遺失，目的車輛僅僅收到少量的封包，檔案成功傳遞的可靠度(data delivery ratio)相對地下降,在這樣的瓶頸下,我們利用隨機線性網路編碼理論( Random Linear Network Coding ),來源車輛將編碼後的編碼封包廣播至目的車輛,有效地提高檔案成功傳遞的可靠度及縮短目的車輛成功接收每個檔案的延遲時間(end to end delay)。為了確保資料成功傳遞的可靠度,我們亦增加了Store and Forward的機制,當鄰近地區沒有車輛幫忙轉送封包時，便將封包暫時儲存在佇列(queue)裡,直到遇到其他車輛時,才將封包傳送出去,因此適用於車輛稀少的網路裡。由於車流移動變化影響,封包遺失的情況大大侷限目的車輛收到的完整原始檔案的機會,利用隨機線性網路編碼,目的車輛能夠更有效的將收到僅有的編碼封包解碼回原始資料,提高獲取完整原始檔案的機率,根據我們的實驗模擬結果,在車用網路中配合隨機線性網路編碼理論可有效提高檔案傳遞可靠度及傳輸時間。

Mobility of vehicles in a vehicular ad-hoc network frequently results in network partitioning and route disconnection for packet forwarding. Conventional mechanisms of route discovery and maintenance are usually infeasible in vehicular ad-hoc networks. As a result, successfully transferring a file in a vehicular ad-hoc network is much challengeable than doing that in traditional mobile ad-hoc networks. In this thesis, an opportunistic forwarding mechanism incorporating with random linearly network coding is proposed to carry out file forwarding in a vehicular ad-hoc network. The file is divided into a series of blocks, namely raw blocks. Coded blocks generated by the raw blocks with different linear combination coefficients are forwarded to the receiver. Traditionally, file forwarding has to successfully deliver all the raw blocks to the receiver side and, thus, wastes longer time and delivery ratio may be lower. With network coding, the receiver just collects any coded blocks met on its way and recovers the original file using coded blocks with linear independent coefficients. In particular, the number of the coded blocks used to recover the file is the same as the raw blocks used by the traditional forwarding method. Since the receiver does not need to wait every single raw block, the end to end delay of file forwarding is reduced and the delivery ratio is improved. In addition, a store and forward approach is developed to achieve effective block forwarding in sparse vehicular networks. Simulation results show that our forwarding mechanism effectively improves data delivery ratio and end to end delay in a vehicular ad-hoc network.

[1] J. Jin, B. Li, T. Kong, “Is Random Network Coding Helpful in WiMAX?,” The 27th Conference on Computer Communications (INFOCOM 2008), IEEE, April 2008.
[2] S. Biswas, R. Morris, “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” Proc. of 2005 conference on Applications, technologies, architectures, and protocols for computer communications (SIGCOMM’05), January 2005.
[3] J. Zhao, G. Cao, “VADD: Vehicle-Assisted Data Delivery in Vehicular Ad-hoc Networks,” Proc. of 25th IEEE International Conference on Computer Communications (INFOCOM 2006), April 2006.
[4] V. Naumov, T. R. Gross, “Connectivity-Aware Routing (CAR) in Vehicular Ad Hoc Networks,” Proc. of 26th IEEE International Conference on Computer Communications (INFOCOM2007), May 2007.
[5] I. Leontiadis, C. Mascolo, “GeOpps: Geographical Opportunistic Routing for Vehicular Networks,” World of Wireless, Mobile and Multimedia Networks (WoWMoM’2007), IEEE, June 2007.
[6]　M. Jerbi, S.-M. Senouci, R. Meraihi, Y. Ghamri-Doudane, “An Improved Vehicular Ad Hoc Routing Protocol for City Environments,” International Conference on Communications (ICC '07), IEEE, June 2007.
[7]　T.Taleb, E. Sakhaee, A. Jamalipour, K. Hashimoto, N. Kato, Y. Nemoto, “A Stable Routing Protocol to Support ITS Services in VANET Networks,” IEEE Trans. on Vehicular Technology, Vol. 56, Issue 6, Nov. 2007.
[8] Y. Ding, C. Wang and L. Xiao, “A Static-Node Assisted Adaptive Routing Protocol in Vehicular Networks,” Proc. of 4th ACM international workshop on Vehicular ad hoc networks (VANET2007), September 2007.
[9] Y. Liao, K. Tan, Z. Zhang, L. Gao, “Estimation based Erasure-coding Routing in Delay Tolerant Networks,” International Conference On Communications And Mobile Computing (IWCMC06), July 2006.
[10] A. Skordylis, N. Trigoni, “Delay-bounded Routing in Vehicular Ad-hoc Networks,” In Proc. of 9th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc08), May 2008.
[11] Simulation of Urban Mobility (SUMO), http://sumo.sourceforge.net.
[12]　F.K. Karnadi, Z. Mo, K. Lan, ”Rapid Generation of Realistic Mobility Models for VANET,＂Wireless Communications and Networking Conference (WCNC 2007), IEEE, March 2007.
[13] R. Ahlswede, N. Cai, S.-Y. R. Li, R. W. Yeung, “Network information flow,” IEEE Trans. on Information Theory, Vol. 46, July 2000.
[14] R. W. Yeung, S.-Y. R. Li, N. Cai, “Network Coding Theory”, Foundations and Trends in Communications and Information Theory, vol. 2, no.4-5, pp. 241-381, 2005.
[15] S.-Y. R. Li, R. W. Yeung, N. Cai, “Linear Network Coding,” IEEE Trans. on Information Theory, Vol. 49, February 2003.
[16] T. Ho, R. Koetter, M. Medard, D. Karger, M. Effros, “The Benefits of Coding Over Routing in a Randomized Setting,” Proc. of International Symposium on Information Theory (ISIT), 2003.
[17] A. Xeros, M. Andreou, A. Pitsilides, M. Lestas, “Information Propagation Probability on Intersections in VANETS,” Proc. 3th International Workshop on Vehicle-to-Vehicle Communications 2007 (V2VCOM 2007), June 2007.
[18] Ron Roth, “Introduction to Coding Theory,” Cambridge University Press, first edition, March 2006.
[19] Q. Yang, A. Lim, P. Agrawal, “Connectivity Aware Routing in Vehicular Networks,” in Proc. of IEEE International Conference on Wireless Communications and Networking (WCNC 2008), March 2008.
[20] A. Mahajan, N. Potnis, K. Gopalan, A. I. Wang, ”Evaluation of Mobility Models for Vehicular Ad-Hoc Network Simulations,” Proc. of the 2nd IEEE International Workshop on Next Generation Wireless Networks, December 2006.
[21] M. Saito, J. Tsukamoto, T. Umedu, T. Higashino, “Evaluation of Inter-Vehicle Ad-hoc Communication Protocol,” Proc. of the 19th International Conference on Advanced Information Networking and Applications - Volume 1 (AINA 2005), March 2005.
[22] T. Nadeem, P. Shankar, L. Iftode, “A Comparative Study of Data Dissemination Models for VANETs,” Proc. of the 3rd Annual International Conference on Mobile and Ubiquitous Systems (MOBIQUITOUS), July 2006.
[23] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, “XORs in The Air: Practical Wireless Network Coding,” IEEE Transactions on Networking, Vol. 16 ,No. 3, June 2008.
[24] P. Chou, Y. Wu, K. Jain, “Practical Network Coding,” Proc. of Allerton Conference on Communication, Control and Computing, October 2003.
[25] H. Shojania, B. Li, “Parallelized Progressive Network Coding With Hardware Acceleration,” Proc. of 5th IEEE International Workshop on Quality of Service (IWQoS), June 2007.
[26] N. Wisitpongphan, F. Bai. P. Mudalige, O. K. Tonguz, “On the routing problem in disconnected vehicular ad-hoc networks,” Proc. of IEEE International Conference on Computer Communications (INFOCOM 2007), May 2007.
[27] N. Wisitpongphan, F. Bai. P. Mudalige, V. Sadekar, O. Tonguz, “Routing in Sparse Vehicular Ad Hoc Wireless Networks,” IEEE Journal on Selected Areas in Communications, Vol. 25, Issue 8, October 2007.
[28] G. Korkmaz, E. Ekici, F. Ozguner, U. Ozguner, “Urban multihop broadcast protocol for inter-vehicle communication systems,” Proc. of the 1st ACM international workshop on Vehicular ad hoc networks, October 2004.
[29] J. Blum, A. Eskandarian, L. Hoffman, “Challenges of Intervehicle Ad Hoc Networks,” IEEE Transactions on Intelligent Transportation Systems, vol. 5, December 2004.
[30] A. K. Saha, D. B. Johnson, “Modeling mobility for vehicular ad hoc networks,” Proc. of the 1st ACM international workshop on Vehicular ad hoc networks, October 2004.
[31] Network Simulator 2, http://www.isi.edu/nsnam/ns/index.html.