关键词: 移动自组网，多点中继，集合覆盖

Abstract: Mutipoint relay selection algorithm is a flooding technique which can be used to propagate message in MA- NET. This algorithm is proved to save node's energy and prolong the MANET's life,and also can reduce the number to be searched and reduce the broadcasting time. This paper began with the relationship between set covering problem and multipoint relay selection algorithm to improve the classic algorithm and then proposed a new one called efficient mutipoint relay selection algorithm (E-MRSA). The simulation results show that the new algorithm can reduce the number of nodes up to 14% Moreover, it also can reduce the power-consumption of network up to 12% and save the propagation time by 9 %. So the E-MRSA algorithm can improve the performance of mobile Ad hoc networks in a certain extent

Key words: Mobile Ad hoc network, Mutipoint relay, Set covering