无线自组织网络环境中基于服务距离的服务发现方法

技术领域

本发明属于自组织网络技术领域，具体涉及一种能够适应无线自组织网络环境的基于服务距离的服务发现方法。

背景技术

服务发现是查询网络中服务的位置、并收集相关信息的过程。该技术是服务组合、服务执行的必须前提基础技术，因此，它在服务计算的各环节中占有非常重要的地位。

在固定有线网络中，典型的Web服务发现方法和协议有：Jini，UPnP，Salutation/Salutation-lite，SLP(Service Location Protocol，服务定位协议)。Jini是由SUN公司开发的一种分布式的服务发现体系结构，其目标是将传统网络转换为一种灵活、易管理的工具，使用户可以很方便地发现服务，其核心是JLS(Jini Lookup Service，Jini查找服务)，维护可用服务的动态信息。UPnP扩展了微软关于外部设备即插即用的模型，支持不同厂商网络设备提供的服务发现。UPnP采用SSDP(Simple Service Discovery Protocol，简单服务发现协议)在IP网络上发现服务。Salutation是一种开放标准的、与平台无关的服务发现和会话管理协议，它的目标是解决在广域或移动环境中，大量应用和设备的服务发现和利用的问题。Salutation-lite是为适应小设备而设计的Salutation的简化原型。SLP是一种与语言无关的协议，在IP网络上进行自动服务发现，有三种类型的代理(用户代理，服务代理以及发现代理)。

上述协议都需要有一个服务发现代理中心来协助完成服务发布和发现的功能，这种机制并不适合自组织这类无基础结构的网络。Ninja是Berkeley大学研究的服务发现系统，由用户、服务以及SDS服务器组成，系统具有可伸缩、容错、安全可用等特点，支持局域或广域服务；用户、服务采用全局SDS多播信道与SDS服务器进行通信。蓝牙服务发现协议(Bluetooth Service Discovery Protocol)是P2P网络中的简单服务发现机制，实现无中心目录服务，服务信息存储在每个移动/静态设备上的本地的服务发现服务器上，但该服务器并不指明对服务的访问方法，只是回答是在该设备上是否服务可用。

无线自组织网络中的服务发现是使用无线环境中邻近设备上可用服务的必备环节，也是进一步进行服务组合的必须步骤。目前，在无线自组织网络中的服务发现主要还是采用广播驱动(broadcast-driven)的方法。这种基于广播的服务发现方法虽然简单，但可伸缩性不佳。特别是当网络规模增大时，基于广播的服务发现方法会直接导致网络负载过重，影响正常的网络通信。D.Chakraborty等提出了基于组的服务路由和服务发现协议，采用基于分布式代理方法实现服务组合。以上这些方法都没有考虑自组织网络的拓扑动态变化快、可伸缩性大等关键特性。

发明内容

本发明的目的在于提出一种适合无线自组织网络环境的基于服务距离的服务发现方法。

首先对一些基本概念进行定义：

(1)服务提供者：服务的拥有者和具体实现者，是服务的直接提供方。

(2)服务请求者：服务的需求方和请求方，发起服务发现过程以获得所需服务的位置等信息。

(3)服务广告(Service_ADV_Msg)：是由网络中的节点周期性地主动向其周围邻居节点发送的服务宣告信息，宣告其拥有某个服务或某类服务，以及所知道的其周围节点所拥有的服务信息。

(4)服务信息缓存：节点为保存自身的服务信息或服务广告中服务信息而开辟的存储空间。

(5)服务距离(Service_Distance)：当前节点距离服务广告或服务信息缓存中描述的服务(组)的服务提供者的节点跳数。

在无线自组织网络中，由于受节点移动、能量有限等因素的影响，网络的拓扑会经常发生变化。在这样一个不断变化的网络环境中，一般认为离服务请求者越近的服务越可靠，反之离服务请求者越远的服务由于越容易受环境因素的影响，因此越不可靠，越不值得信任。

本发明提出的服务发现方法不再使用广播发现的方式，而是利用网络节点定期发送的服务广告，并在服务广告中加入服务距离信息的方式辅助服务发现。一方面，服务请求者通过中间节点缓存的服务所属组及服务距离信息可以避免采用广播发现的方式，大大缩小搜索范围，减少服务发现请求包的数量，减轻网络负担。另一方面，本方法充分利用服务距离信息帮助服务请求者发现更可靠、更有效的服务提供者，同时由于选择服务距离最近的节点，因此也降低了服务发现的延迟时间，并提高了后续的服务执行效率。

整个服务发现的过程包括服务本体构造、服务广告、服务信息缓存、服务发现四个阶段。

各步骤具体如下：

1、服务本体构造

首先使用OWL-S语言(Ontology Web Language，Web服务本体描述语言)结合具体的服务应用场景对服务进行语义描述，描述服务的功能、特性、适用面等。然后根据服务的功能、特性对服务进行归类分组，分成语义相近的服务组(Service Group)。若干服务组可以继续归类分组为更高层次的服务组，逐渐形成一个服务分组的层次结构。服务的语义描述和分组情况最终构成了服务本体。例如，在会议现场有黑白和彩色两种复印服务，这两种复印服务都可归类为复印服务组，而复印服务又可被归类到输出服务组。这些服务的语义描述和分组描述都可以使用OWL-S语言描述成服务本体。

2、服务广告

服务广告(Service_ADV_Msg)的目的是为了宣传节点自己能提供的或它知道的服务信息。而具体的服务信息就是服务本体。在本方法中节点定期主动地向周围邻居节点广告其能够提供的服务，以及它所知的可用远程服务组。

为了限定服务广告的传播范围，避免过多增加网路负载，本方法将服务广告的传播距离设为1跳，即广告报文的TTL(Time-To-Live，存活期)为1。

服务广告的具体报文格式定义如下：

<广告报文>::＝<<广告报文头>，<广告报文体>>

<广告报文头>::＝<报文类型，源节点地址>

其中：

(1)报文类型(Packet Type):＝SERVICE_ADVERTISEMENT

(2)源节点地址(Source_Node_Address):＝发出服务广告的节点地址

<广告报文体>::＝<本地服务列表，远程服务组列表，广告存活期>

          ::＝<Local_Service_List，Remote_Service_Group_List，TTL>

其中：

(1)Local_Service_List::＝<Local_Service，……>

  Local_Service::＝Service_Name(Service_Group，Service_Distance)

(2)Remote_Service_Group_List::＝<Remote_Service_Group，……>

Remote_Service_Group::＝(Service_Group，Service_Distance)

(3)TTL:＝1。

根据以上定义可以看出一个服务广告的扩散范围控制在1跳范围内。其中本地服务列表(Local_Service_List)根据当前节点的实际情况构造。而远程服务组列表(Remote_Service_Group_List)需要根据当前节点已缓存的服务信息(即服务信息缓存，具体定义请参加具体步骤3)构造。

服务广告中的远程服务组列表(Remote_Service_Group_List)的构造算法如下：

(1)遍历本地服务列表，取出一项本地服务Local_Service；

(2)查看Remote_Service_Group_List是否具有与此本地服务同组的远程服务组Remote_Service_Group，即：Remote_Service_Group.Service_Group＝＝Local_Service.Service_Group。如果没有，则跳到第(3)步将此本地服务组添加服务广告的远程服务列表中。如果有则跳到第(1)步循环取下一个本地服务。

(3)将此本地服务组添加服务广告的远程服务列表中，需要新增一项远程服务组Remote_Service_Group，并进行以下赋值：

Remote_Service_Group.Service_Group:＝Local_Service.Service_Group；

Remote_Service_Group.Service_Distance:＝1；

(4)循环跳回(1)，直至本地服务列表遍历完毕，则继续第(5)步。

(5)遍历服务信息缓存，取出一个缓存项Cache_Entry。

(6)查看Remote_Service_Group_List是否具有与缓存项同名的远程服务组Remote_Service_Group， 即：Remote_Service_Group.Service_Group＝＝Cache_Entry.Remote_Service_Group。如果没有则跳到第(8)步添加新的远程服务组。如果有，则继续判断是否Cache_Entry.Service_Distance＜Remote_Service_Group.Service_Distance。如果是，则跳到第(7)步对此远程服务组进行更新。如果否，则跳回第(5)步取下一项缓存项。

(7)对服务广告中的远程远程服务组Remote_Service_Group进行更新：

Remote_Service_Group.Service_Distance:＝Cache_Entry.Service_Distance

(8)向服务广告中远程服务组列表添加新的远程服务组Remote_Service_Group，并赋值：

Remote_Service_Group.Service_Group:＝Cache_Entry.Remote_Service_Group

Remote_Service_Group.Service_Distance:＝Cache_Entry.Service_Distance

(9)循环跳回(5)，直至服务信息缓存遍历完毕。

服务广告的广告周期可以由使用者根据不同的应用场景确定，例如网络拓扑变化较慢且其他环境因素不宜变化的场景，就可以选择较长的广告周期，例如1小时甚至更长。而对于网络环境变化迅速的场景，则可以选择较短的广告周期，即提高广告频率。

3、服务信息缓存

节点收到其他节点发来的服务广告后，需要将其他节点拥有的或知道的服务信息保存下来放入到服务信息缓存中，以便未来接受到服务发现请求时匹配查找。

(A)服务信息缓存定义

<服务信息缓存>::＝<<缓存项>，……>

<缓存项>::＝<远程服务组，服务距离，节点地址，生命终止时间>

(<Cache_Entry>::＝<Remote_Service_Group，Service_Distance，Node_Address，Life_Time>)

其中：

(1)节点地址:＝服务广告报文中的源节点地址

(2)远程服务组，服务距离：根据广告报文中的远程服务组列表(Remote_Service_Group_List)和缓存中已有的服务信息构造。

从缓存项的定义可以看出：每个缓存项包含了某节点所拥有的或所知道的服务组以及该服务组距离当前节点的跳数等信息。

(B)服务信息缓存更新策略

服务信息缓存主要依据节点收到的服务广告来构造和更新，具体做法是如果缓存空间足够，则将服务广告中的服务信息尽可能地记录下来，但记录的不是服务，而是服务组和服务组的距离信息。如果服务广告中描述的服务组的服务距离更短，则更新服务信息缓存。

服务信息缓存的构造和更新算法如下：

(1)从服务广告Service_ADV_Msg的本地服务列表(Local_Service_List)取出一项本地服务Local_Service。

(2)如果缓存已有缓存项Cache_Entry.Remote_Service_Group＝＝Local_Service.Service_Group，且Local_Service.Service_Distance＜Cache_Entry.Service_Distance，且缓存没有多余存储空间，则将该缓存项的服务距离更新为广告中此本地服务的服务距离，同时延长该缓存项的生命终止时间(Life_Time)。

(3)如果缓存不存在与此本地服务具有相同Service_Group的缓存项，或者缓存仍有多余空间，则将该本地服务作为新缓存项(Cache_Entry)加入缓存中，其中的各项赋值如下：

Cache_Entry.Remote_Service_Group:＝Local_Service.Service_Group

Cache_Entry.Service_Distance:＝Local_Service.Service_Distance

Cache_Entry.Node_Address:＝Service_ADV_Msg.Source_Node_Address

Cache_Entry.LifeTime:＝节点当前时间+自定义生命周期

(4)循环至第(1)步，直至本地服务列表为空。

(5)从服务广告Service_ADV_Msg的远程服务组列表(Remote_Service_Group_List)取出一项远程服务组Remote_Service_Group。

(6)如果缓存已有缓存项Cache_Entry.Remote_Service_Group＝＝Remote_Service_Group.Service_Group，且Remote_Service_Group.Service_Distance＜Cache_Entry.Service_Distance，且缓存没有多余存储空间，则将该缓存项的服务距离更新为服务广告中此远程服务组的服务距离，同时延长该缓存项的生命终止时间。

(7)如果缓存不存在与此远程服务组具有相同Service_Group的缓存项，或者缓存仍有多余空间，则将该远程服务组作为新缓存项(Cache_Entry)加入缓存中，其中的各项赋值如下：

Cache_Entry.Remote_Service_Group:＝Remote_Service_Group.Service_Group

Cache_Entry.Service_Distance:＝Remote_Service_Group.Service_Distance

Cache_Entry.Node_Address:＝Service_ADV_Msg.Source_Node_Address

Cache_Entry.LifeTime:＝节点当前时间+自定义生命周期

(8)循环至第(5)步，直至远程服务组列表为空。

(9)扫描各缓存项，如果某缓存项的生命终止时间已到，则清除该缓存项。

4、服务发现

服务请求者在使用某个服务(如彩色复印服务)前需要了解该服务提供者的位置信息，所以需要发起一个服务发现的过程。节点通过发出服务发现请求报文发起服务发现过程。

服务发现请求的报文格式定义如下：

<Service_Discovery Request>::＝<<SDR_Header>，<SDR_Payload>>

<SDR_Header>::＝<Packet_Type，Request_Node_Address，TTL>

<SDR_Payload>::＝<Service_Name，Service_Group>

其中：

●Packet_Type:＝SERVICE_DISCOVERY_REQUEST

●Request_Node_Address：服务请求者的节点地址

●TTL：服务发现请求报文的存活跳数(生命周期)

●Service_Name：请求的服务名称

●Service_Group：请求的服务所属的服务组

节点在接收到服务发现请求后首先在自己提供的服务列表中查找匹配的服务。如果找到，则说明自己有能力提供该服务，则立即回应服务请求者，服务发现过程结束。如果没有找到说明自己没有能力提供该服务，那么就需要根据服务信息缓存将该服务发现请求转发给可能知道该服务且离当前节点最近的节点，继续服务发现过程。如果服务信息缓存中也不存在知道该服务的节点，则只能将该服务发现请求广播给周围的所有节点继续服务发现过程。

节点处理服务发现请求的算法如下：

(5)遍历本地服务列表，如果有本地服务与服务发现请求匹配，则向服务请求者返回服务发现结果。如果没有，则继续第(2)步。

(6)遍历服务信息缓存，查找符合条件Cache_Entry.Remote_Service_Group＝＝SDR.Service_Group的所有缓存项。如果查找结果为空，则转入第(4)步。如果查找结果不为空，则转入第(3)步。

(7)在查找结果中选择Cache_Entry.Service_Distance最小的缓存项Cache_Entry，并向Cache_Entry.Node_Address指向的节点定向转发该服务发现请求包，继续服务发现过程。

(8)向周围邻居节点广播该服务发现请求包，继续服务发现过程。

本方法通过基于服务距离的服务广告方式，不仅避免了广播式服务发现方法存在的可伸缩性差、网络负载重、无法适应无线自组织网络环境的问题，而且，利用服务距离信息使用户能更快地找到更稳定可靠的服务，提高了服务发现的效率。

附图说明

图1：会议应用场景。描述了网络节点构成，以及节点的角色，提供的服务等信息。

图2：服务广告和服务信息缓存。描述以图1为场景的应用中服务广告的发送和服务信息缓存的构造。

图3：服务发现过程。描述了服务发现过程。