无线传感器网络的WiME系统路由设计及应用

4.2 BIoom Filter概念

　　Bloom Filter的概念最早是由B.H.Bloom于1970年提山的。已知一个集合S含有n个元素，每个元素可以是人名、网址或者某个编号之类的能被计算机识别的独有的一个或一组符号。我们定义一个含有m个元素的向量表v，v中的每个元素只使用1位表示，即每个元素只能表示为0或1。初始化v的每个元素为0。假设有k个独立的hash函数H1，…，Hk，映射范围为m。对S中的每个元素，将其进行hash变换后在v中对应的位置上置1。

　　如果要知道一个元素a是否在集合S中，可以参照图1对其进行k个hash变换，并查询v中对应的元素是否为1。如果k个对应元素均为1，就断定a在集合S中。

　　举例来说，如果S表示的是一个URL查找表，每个元素平均包含50个ASCII码，则直接存储需要400n位；而采用Bloom Filter存储，需要m位(m和kn同数量级)。由于hash函数的计算需要花费一定的时间，限制k的个数不会很大，使得存储空间大大缩小，所以这是一种用时间换取空间的办法。

4.3 最优情况下Bloom Filter的正向误检概率

　　从上面可以看到，集合元素个数n、hash函数个数k和向量表长度m是Bloom Filter的3个关键参数。BloomFilter中存在着这样一种情况，即虽然一个元素不属于集合S，由于hash函数的随机性，有可能k个hash变换在v中的对应元素均为1，从而该元素被误认为属于集合S。这种情况称为“正向误检(false positive)”。从概率上看，正向误检总是不可避免的。

　　将n个元素插入Bloom Filter表中后，每一位元素仍然为0的概率是(如无声明，下面均认为hash函数是均匀映射的)：

4.4 计数型Bloom Filter

　　在生成Bloom Filter表的过程中，不可避免地会出现映射到v的同一位置的情况，这在存在增删的情况下就会出现问题。如果一个元素从集合中删除，则其对应的Bloom Filter表中的元素都要从1变为0。那么，其他映射到该位置的元素在查询自身是否属于集合时，就不会得到正确结果，这称为“反向误检(false negative)”。计数型Bloom Filter可以解决这个问题，它将向量表中每个位置从1位表示改为多位表示。这样，添加操作中每映射到某一位置1次，该位置就计数加1；删除操作中时，该位置减1。计数位数决定了所能计数的最大值。

4.5 Bloom Filter的其他改进

　　除了计数型Bloom Filter，还有许多在尝试提出改进的Bloom Filter数据结构。参考文献[6]提出的压缩型Bloom Filter探讨了非最优情况下m、n和k之间的相互关系；参考文献[7]提出的域衰减Bloom Filter，针对无线传感器网络中洪泛查询的特点提出了随空间域衰减的方式，其Bloom Filter向量表中置1的位会随着空间域的变化以一定概率清0，则Bloom Filer解码时就变成了统计k个hash函数对应位置上1的个数(个数越大可能性越大)；参考文献[8]提出的拆分型Bloom Filter，针对反复增删最终导致最初设计的Bloom Filter表不可用的情况，提出将总表分割成多个子表来设计。

综合考虑，笔者仍然认为计数型Bloom Filter是简单、易用的，而且具有较好的性能。尽管参考文献[5]建议使用4位计数，但经过对计数位数的理论分析和实验验证，笔者最终采用了2位计数。这已经可以将进行反复增删可能造成的反向误检的概率降低到1.85×10-4。反复增删5396次，才会出现1次反向误检，对1000个节点这样的规模已经是够用的了。不过，对于这一问题的讨论已经超出了本文的范围，这里不再赘述。　

　5 结 论

WiME是一个基于生物行为启发的、使用无线传感器网络实现的智能复眼系统。它尝试着从仿生的角度来有效地降低智能实现的复杂性，提高机器人的移动能力；同时拓宽机器人的应用范围，使廉价移动机器人也可以表现出卓越的移动智能。这是从另一个视角解决集中式人工智能所面临的应用难点的一种新的理论尝试。

WiME中的机器人导航技术采用单步的方向查询方式，完成了一跳情况下的路由查询任务；而且使用了Bloom Filter来压缩存储，空间进行了高度优化。这使在无线传感器网络这样一个计算能力弱、资源严重受限的环境下完成路径和通信路由查询系统这样一个包含大数据最的工作变成了现实。希望本设计的思路，对于其他的机器人导航应用有很好的启发作用。