无线传感器网络(Wireless Sensor Network,WSN)是由大量低成本的受资源约束的传感器节点所构成的网络,这些节点间相互协作,从而实现对网络覆盖区域的监控。各个节点所感知到的信息会被传回基站以供进一步的分析。然而,如果网络中存在故障节点,那么整个网络的性能都会受到影响;如果敌方捕获了网络中的节点或者在网络中部署恶意的节点使其转发伪造的信息,那么这种情况将会造成更为严重的后果。因为相对故障节点来说,这些恶意伪装的节点将会更难被识别出来。对安全协议的设计被认为是WSN研究领域中的一个难点,近些年,学者们围绕这一课题展开了深入的研究。其中,Vogt等人基于多重相交认证链的思想提出了帆布协议以及对它的改进协议——k-广义帆布协议。在k-广义帆布协议中,只要传输路径的任意k个连续节点中至少有一个节点没有被捕获,就能保证该路径上数据传输的安全性。考虑到k-广义帆布协议的应用前提,我们可以在初始化网络时就找出一些传感器节点使之成为受保护节点,以保证网络中每条长度为k-1的传输路径上至少有一个节点受到保护。针对这个问题,本文提出了最小k-路径连通顶点覆盖的近似构造算法。通过该算法,我们可以找出已知网络中的受保护节点的集合,而且可以尽可能地减小集合以节省成本。然而,一方面,WSN通常是一个较为稠密的无线网络,其k-路径连通顶点覆盖往往很大,使得这个集合中的所有节点均受到保护的成本很高;另一方面,WSN是一个动态的网络,事先知道网络的全局信息并在已知网络中找出节点集合从而加以保护的做法是不现实的。在这样的背景下,为了更好地发挥k-广义帆布协议的优势,本文提出了一种判断任意一条路径安全性高低的方法,并提出了基于k-广义帆布协议的路由算法,以提高网络中的数据在传输过程中的安全性。