仮想グリッドネットワークとは,無線ネットワークを一定領域(セル)に仮想的に分割し，各セル中のノードのうち1台をルータにすることでマルチホップ通信を実現する格子状ネットワークである．送受信ノード間の通信は，送受信ノードが移動しても経路を延長することで保持される一方，最適(最短)経路に対して冗長となる場合がある．そこで本研究では，仮想グリッドネットワーク上で送受信ノード間の最短経路が構築されている状況から受信ノードが隣接セルに移動した場合に再び最適化するためのメッセージ通信による非同期分散アルゴリズムを提案する.