无线自组网中基于松散位置依赖的缓存搜索方法

摘要

本发明公开了一种无线自组网中基于松散位置依赖的缓存搜索方法，松散位置依赖模式下的搜索过程包括以下4个步骤：1)生成请求；2)本地缓存搜索，若无结果则执行步骤3)；3)向邻居用户发送搜索请求，每个邻居用户执行步骤2)的本地搜索，将结果返回产生请求的用户，由该用户选择最合适结果，若无结果则执行步骤4)；4)向服务器提交搜索请求，由服务器返回最优结果。用户在提出搜索请求时可根据具体情况附加上其可以承受的额外开销，通过比对缓存数据的有效区域以及相应的约束值来决定该缓存数据是否可用。该方法既提高了缓存的命中率，同时也降低了通信传输过程中的能量开销。

主权项

一种无线自组网中基于松散位置依赖的缓存搜索方法，其特征在于以空间约束r、内部对象集Pin和周边对象集Pout来描述一个数据对象q0的松散有效区域：对于给定的q0和r，令Polyi表示用Voronoi图划分的qi的有效区域的边集，其中i＝1，...，N，首先把qi按到q0的距离从小到大进行排序，取出距离q0最近的对象qk，作曲线f(M(x，y))：|q0M|‑|qkM|＝r，若该曲线与Polyk的交点少于2个，则取下一个距离q0最近的对象qn重复上述操作，即作曲线f″(M(x，y))：|q0M|‑|qnM|＝r，若该曲线与Polyn有2个交点P1和P2，取一个交点P2，则必存在另一个对象qk′，P2也在Polyk′的一条边上，作新的曲线f′(M(x，y))：|q0M|‑|qk′M|＝r，得到另一交点P3，依次下去得到新的交点P4、P5、…、Pm；由于过点P1、P2、…、Pm用双曲线段所围成的区域是封闭的，即Pm+1＝P1，至此q0的松散有效区域的边集构造完成，同时也找出了所有的周边对象，接下来对照各数据对象的位置就可以确定内部对象集，即位于该松散有效区域内的其他备选数据对象；而基于松散位置依赖的缓存搜索方法包括以下4个步骤：1)生成请求Q(X，(xc，yc)，Δd)，其中，X是所请求的数据对象，(xc，yc)是用户发出请求Q的位置M的坐标，Δd是用户能够承受的额外开销；2)搜索本地缓存，找出松散有效区域覆盖率用户的当前位置的所有数据的集合，作为备选结果集{Ai}，对于每一个Ak∈{Ai}，如果其空间约束值rk≤Δd，则Ak为Q一个合适的搜索结果；否则，找出离用户发出请求Q的位置M最近的备选对象qx，qx∈Pin，令e＝|AkM|‑|qxM|，若e≤Δd，则Ak亦为Q一个合适的结果，返回具有最小e的合适结果，若无结果则执行步骤3)；3)向邻居用户发送搜索请求，每个邻居用户执行步骤2)，将结果返回产生请求的用户，由该用户选择最合适结果，结束；若无结果则执行步骤4)；4)向服务器提交搜索请求，由服务器返回最优结果。