A Protocol Conformance Testing Method For MANETs

Dynamic network topology and self-organization are the inherent features of Mobile Ad hoc Network(MANET). It is widely used in military, disaster and medical treatment. After a protocol implementation is claimed to follow a specific standard, a protocol conformance testing should be carried out to validate whether the implementation under testing(IUT) is conformance to its specification. So the protocol conformance testing is an important method to ensure the communication quality of the network protocol. The traditional formal model may lead to unfeasible test sequences in conformance testing, due to the topological distinction between testing sequences generation and its execution.To alleviate this problem, firstly, the evolving graph is introduced in this paper. The evolving graph can extend the function of FSM, enhancing its ability to describe the dynamic topology network with predictable movement pattern. A formal model, named Evolving Graph Finite State Machine(EGFSM) is proposed to help alleviate the impact of the dynamic network on conformance testing in MANETs. Secondly, an algorithm for generating test sequences is proposed based on EGFSM. Finally, the result that based on the experiments for AODV and OLSR routing protocol testing demonstrates the effectiveness of the proposed method. The new method can formalize a model to describe the MANET and generate feasible test sequences for the dynamic topology.The research work and innovative contributions of this paper are listed as follows:(1) We use the evolving graph to extend the function of FSM, and put up a protocol testing modeling method for time-varying network topology. The method can help alleviate the impact of the dynamic network on unfeasible test sequences in MANETs, improve the feasibility of the test sequences.(2) We propose a test sequence generation algorithm for conformance testing, which is based on the proposed model Evolving Graph Finite State Machine. This algorithm is based on control flow tests.(3) The OLSR protocol is a kind of MANET protocol. We make the OLSR protocol as a case for conformance testing, and use the proposed method that build model and generate test sequences. The result of the experiment shows the validity of the proposed method.