Research On Cover Problem And Routing Algorithm Based On Canvas Scheme In WSN

Wireless sensor network(WSN) consists of large amounts of cheap resource-restricted sensor nodes, which work together to monitor the area of the whole network. Individual findings by each sensor node will be sent back to the base station to be deeply analyzed. However, if there are some failed nodes in the network, then the performance of the network will become bad. Moreover, it will be worse if there are some nodes captured by adversary to transform malicious data. And it is more difficult to detect the malicious nodes than failed ones.It used to be difficult to design security protocols in WSN. In recent years, plenty of research has been done on this topic. One of them is a security protocol named canvas scheme which relies on multiple, interwoven authentication chains. Later, its improvement, k- generalized canvas scheme, is presented to provide data integrity if at least one safe node exists on each path of length k-1 in the network.In the application of k- generalized canvas scheme, we can make some sensor nodes protected when initializing the network so that there is at least one protected node on each path of length k- 1 in the network. In this paper, we present a polynomial-time approximation scheme for the k- path connected vertex cover, the set of nodes who need to be protected, in WSN. Also, we need to make the set small enough to reduce the cost.However, WSN used to be so dense that the scale of the k- path connected vertex cover is large and the cost of making all these nodes protected is too high. Thus, we present a method to judge the safety of a path, and secure routing algorithms based on k-generalized canvas scheme, to improve the security of data transmission in WSN.