基于虚拟坐标系统的无线网络地理路由算法

Geographic routing algorithm based on virtual coordinate system

针对地理路由算法中的路由空洞问题,通过引入虚拟坐标的方式,提出了一种新颖的无线网络地理路由算法——双重贪婪算法(DGA)。根据网络的拓扑结构信息,DGA为每个节点分配虚拟坐标,在基于真实地理位置的贪婪算法遇到路由空洞时,以基于虚拟坐标系统的贪婪算法作为恢复机制,从而保证路由算法的收敛性。DGA克服了GPSR等传统地理路由算法只能适用于理想的单位圆图(UDG)的缺点,能够适用于更加真实的无线网络模型。仿真实验验证了DGA高效的路由性能及良好的扩展性。

To address the holes problem in wireless sensor networks,a novel geographic routing algorithm,named Double Greedy Algorithm （DGA）,was proposed based on virtual coordinate system.First,each node in the wireless network was allocated a set of virtual coordinates according to the topology of wireless network.Then,when the greedy algorithm based on the real geographic positions failed,the greedy algorithm based on the virtual coordinates helped it to recover from the dead end situation.Hence,the convergence of DGA was guaranteed.DGA was applicable for more accurate network models,such as the network model based on the log-normal shadowing model,which is substantially different to the GPSR algorithm.At last,the performance and scalability of DGA were verified by simulations.