結合網路編碼之網格地域性廣播轉送機制

On Combining Network Coding with Grid-based Geocasting Scheme over MANETS

地域性廣播(Geocast)是一種廣播協定，利用地理位置資訊將訊息轉送到特定地理區域內的所有節點。在轉送過程中，當轉送區域內有大量節點時，會增加傳送封包時碰撞的機率，遺失率也相對提高。本篇論文提出Grid-base-Location-Aided (GLA)與Greedy-Grid-base-Location-Aided (GGLA)方法來改善此問題，GLA方法主要將地域性廣播轉送區域分成數個網格，每個網格只能擁有一個主要節點(Gateway)負責轉送的工作，來減少傳送次數，GGLA方法則是加入貪婪路由機制，來減少更多不必要的傳送，以改善在無線網路環境中轉送區域內密集節點傳輸所造成的訊號碰撞與封包遺失的問題。當地域性廣播區域中的節點接收到資料封包後，會直接將封包廣播出去，在地域性廣播區域中易產生廣播風暴的問題，造成大量的訊號碰撞及封包遺失。當封包遺失時，透過網路編碼將二個以上的封包進行編碼，用少量的編碼封包來復原遺失資料，可以減少地域性廣播區域內封包的傳送次數，降低封包碰撞機率，提升整體網路效能。

Geocasting can deliver information to a group of destinations in a network identified by their specific geographical locations. During packet forwarding, the probability of signal collision and packet loss increase when a large number of nodes are within the forwarding zone. In this paper, we propose Grid-base-Location-Aided (GLA) and Greedy-Grid-base-Location-Aided (GGLA) algorithms to solve the problem. GLA partitions the geocast forwarding zone into several 2D logical grids; a node is elected as a gateway in each grid. This gateway is then responsible for forwarding data packets to the geocast region. By using the gateway approach, GLA can reduce the required number of packets forwarded. GGLA introduces a greedy routing mechanism to GLA to reduce the probability of packet loss with high-density nodes in the forwarding zone. When a node receives a data packet in the geocast region, it floods the data packet in the geocast region, which may cause a broadcast storm problem. When the network coding mechanisms are combined, two or more packets can be encoded and then broadcast, which can decrease the required number of packets for loss recovery. In this paper, GLA and GGLA are further integrated with a network coding mechanism to improve the efficiency of packet transmission in the geocast region.