机会网络中基于社会交通中节点性质的路由选择方法

摘要

机会网络中基于社会交通中节点性质的路由选择方法。针对现有机会网络路由技术通过周期性访问网络中的所有节点，本发明通过对网络中的不同数据产生率的节点进行分集；根据每个集合中节点所处于的不同位置，对拓扑图中的节点进行区域划分；再根据节点的不同数据产生率和其所处于的区域位置，来确定中继节点Ferry的路径访问策略。本发明基于网络中节点的不同性质而对不同节点采取不同的访问策略，能够缩短网络中所有节点总的延迟时间，避免在相同访问方法下对高数据产生率节点带来的高延时以及对低数据产生率节点带来的资源浪费，解决现有路由技术的上述缺陷。

说明书

技术领域

本发明涉及机会网络中的路由技术，尤其涉及一种基于节点性质的访问策略。

背景技术

机会网络（Opportunistic Networks）中是近年来无线网络领域研究的热点，由于该网络的信息延迟大，链路频繁断开以及节点存储容量和能量有限等特点，因此传统的路由协议不适合该网络。由于不服从传统无线网络的端到端之间存在可靠路径这一假设，机会网络采用了完全不同于传统网络的通信模式，它是一种不需要源节点和目的节点之间存在完整路径、利用节点移动形成的通信机会逐跳传输消息，以“存储-携带-转发”的路由模式实现通信的、时延和断裂可容忍的自组织网络。

目前的机会路由转发机制主要分为4类：基于冗余(redundancy-based)的转发机制、基于效用(utility-based)的转发、冗余效用混合(hybrid)机制和基于主动运动(node movement)的转发机制。在基于冗余的转发机制中，通过基于复制(replication)或基于编码(coding)的方式，每个消息产生多个冗余消息在网络中扩散，通过多路径并行传输提高消息传输性能。基于效用的转发机制与传统的网络转发类似，使用单路径、单消息拷贝，它利用网络状态信息来决策下一跳节点，该机制利用一个估计函数给每个节点赋予转发效用值(utility)，该函数使用相遇预测(meeting prediction)、链路状态(link state)和上下文信息(context)等不同的参数来评估节点转发消息的有用性。当两个节点相遇时，消息从效用值低的节点转发到效用值高的节点，直到目标节点。冗余效用混合机制综合了基于冗余和基于效用的转发机制，每个消息产生多个冗余消息，每个冗余消息按照基于效用的转发策略转发到目标节点。在基于节点主动运动的转发机制中，网络中某些节点在部署区域内主动运动来为其他节点提供通信服务，与节点不存在可用的下一跳邻居节点被动等待连接机会的方式相比，提高了网络传输效率。

在机会网络的路由研究中，信息摆渡MF（Message Ferry）路由机制是目前研究和应用较为广泛的一种路由技术，摆渡节点（ferry）作为中继节点在网络中来回移动，来进行在分割的网络中对不连接的节点之间数据的接收，携带与转发，为网络中的节点提供通信服务。摆渡节点路由机制已经被证明是在机会网络中能够有效的提高终端节点之间的通信能力，并且由于能够作为中继传输信息，同时降低了信息的传输时延。（参见文献： Wenrui zhao and Mostafa H. Ammar, “Message Ferrying: Proactive Routing in Highly-partitioned Wireless Ad Hoc Network,” Proceedings of the Ninth IEEE Workshop on Future Trends in Distributed Computing System, Puerto Rico, May 2003）：MF路由方式主要是为了在机会网络中提供一种非随机移动的节点，通过利用这种非随机移动的性质来帮助传输消息。在网络中，摆渡节点沿着已知的路由路径在网络中移动，摆渡节点的移动路径是固定的，不存在随机性，该路径称为路由路径，并且假设网络中的其他正常节点只产生数据，并不参与消息的携带与转发过程。信息摆渡路由的基本方式是：整个网络的消息携带与转发由固定移动的摆渡节点完成：当经过普通节点时，摆渡节点从普通节点上获取要传输的数据；当遇到目的节点时，把数据转发给目的节点。（参见文献：W. zhao, M. Ammar and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks,” ACM MobiHoc, 2004, pp.187–198）：在一个MF路由的网络中，依据节点在通信中的分工，网络中的设备被分成两类：摆渡节点和普通节点。摆渡节点是负责携带消息并转发消息(carry and forward)的设备；普通节点并不处理消息的携带和转发。（参见文献：W. zhao, M. Ammar and E. Zegura, “A Message Ferrying Approach for Data Delivery in Sparse Mobile Ad Hoc Networks,” ACM MobiHoc, 2004, pp.187–198）：MF在网络中规律移动来负责实现普通无线节点间的数据传输。根据MF与普通无线节点间的关系不同，信息摆渡协议的实现方式可以分为两种：NIMF（Node-Initiated MF 节点主导的信息摆渡）与FIMF（Ferry-Initiated MF 摆渡主导的信息摆渡）。对于节点主导的信息摆渡，摆渡节点在网络中按固定轨迹运动，普通节点在获知摆渡节点的运动轨迹后周期性向其靠拢并进行通信；对于主导的信息摆渡，摆渡节点的运动随普通节点的通信需要而发生改变，普通节点使用长距离无线电发送服务请求信号并“召唤”摆渡节点的到来，而后使用短距离无线电与之进行数据通信。摆渡节点的引进与应用作为中继能够有效的提高终端节点之间的通信能力，同时降低了信息的传输时延，但是针对不同性质的所有节点采取同样的周期性访问方法，会带来一定的资源浪费，无所做到对不同性质的节点采取不同的访问方法。

在基于城市交通运输的拓扑图中，客流量越大的地区一般距离拓扑图的中心位置越近，客流量越小的地区则分布在拓扑图中较偏远的位置；产生客流量越大的地区，接受到的客流量也越大，因此，需要用一个交通工具来对上述地区之间进行客流的运输。现有机会网络中基于交换的路由技术通过周期性访问网络中的所有节点，对于具有不同数据产生率的节点采取相同的访问方法，无法做到对于一些数据产生率较高的节点的及时访问，从而造成对于大量数据的高延时；而对于一些数据产生率较低的节点采取同等访问方法，因而带来了一些不必要的资源浪费。

发明内容

本发明所要解决的技术问题是：针对现有机会网络中基于交换的路由技术通过周期性访问网络中的所有节点，无法做到对于一些数据产生率较高的节点的及时访问，从而造成大量数据的高延时。我们提出一种基于网络中节点信息产生率和位置，对不同节点采取不同的访问策略，能够缩短网络中所有节点总的延迟时间，避免在相同访问方法下对高数据产生率节点带来的高延时以及对低数据产生率节点带来的资源浪费，解决现有路由技术的缺陷。

本发明解决上述问题的技术方案是：根据网络拓扑图中节点的信息产生率对节点进行集合划分；根据每个集合中节点的坐标位置用2-D树方式划分区域，将网络拓扑中的节点划分入不同的区域及小区域；分别从区域至不同小区域依次选择节点，确定经过所选节点的最短路径；将每次选取的最短路径组合作为中继节点Ferry的最终访问路径。选取合适的节点进行路径访问，实现中继节点Ferry对不同性质的节点采取不同的访问策略。

本发明“机会网络中基于社会交通中节点性质的路由选择方法”具体包括以下步骤：

1. 节点分集：根据网络拓扑图中节点的信息产生率的不同，对节点进行集合划分，使得属于同一个集合中所有节点的信息产生率属于一个范围之内，以便进一步对于不同集合中的节点采取不同的区域划分。

2. 区域划分：处于同一集合中的节点在网络拓扑图中分布的位置会有一定的差异，根据节点所处在的集合中的坐标位置信息对网络拓扑图进行区域的划分，以便进一步对于不同集合中的节点采取不同的路由访问策略。

3. 路径选取：对于属于不同集合中的节点再根据此节点所在的区域，确定中继节点Ferry分别对所有节点所采取的访问方法，以便达到多数据多访问从而减少总体的数据传输延迟时间。

本发明中的Ferry路由访问策略通过网络拓扑图中节点的数据产生率以及节点所处拓扑图中位置来确定路径，增加了高数据产生率节点的更大的访问频率，能够减少大量数据的传输延迟时间；同时，保证低数据率节点上数据的传输并减少不必要的访问，并在路径中加入靠近路径的节点，从而节省网络资源，提高路由效率。为了防止因为对低数据率节点低频率的访问而由于长时间不访问造成的高延迟时间，本发明还通过给出节点数据总延迟积累时间，使得当低数据率节点的总延迟积累时间达到一定值时就必须使得中继节点Ferry进行及时访问，从而避免因低频率访问而造成更大的数据延迟时间；给出判定路径之外的节点是否需要加入此次路径中，以达到更好的数据传输效果。本发明的路由访问策略增加了中继节点Ferry的自适应功能，能够使得Ferry根据不同节点的不同性质而采取不同的访问策略；从而避免通过周期性访问网络中所有节点，而造成对不同性质节点的不平衡访问所产生的资源浪费和额外数据传输延迟时间，从而可以避免低数据率节点的不必要访问，节省网络资源和数据传输延迟时间。

通过结合使用上述的节点分集、区域划分、路径选取，可以使得中继节点Ferry更加迅速的访问高数据率节点，提高了数据包的接收、转发频率，网络中的数据传输时间也不低于原来的路由方法；同时又可以减少低数据率节点的不必要访问，节省网络资源和数据传输延迟时间。

在不同于传统的一次性访问所有节点方式的情况下，以更加快捷的方式访问数据产生率比较高的节点，做到对数据产生率越高的节点越高频率的访问，降低整体访问对这些节点上数据的传输延迟时间；同时改进对数据产生率比较低的节点的访问策略，保证此类节点上数据的传输并减少不必要的访问，节省网络资源，提高路由效率。

附图说明：

图1路由算法构成示意图；

图2节点分集示意流程图；

图3区域划分流程图；

图4路径选取示意图。

具体实施方式

以下结合附图和具体实例对本发明的实施作具体描述。

如图1所示为机会网络中基于社会交通中节点性质的访问策略路由算法的流程图。包括以下3个主要步骤，节点分集；区域划分；路径选取。

如图2所示为网络中节点分集流程示意图。网络中的各个节点的位置和信息产生率可能都不相同，对于一些信息量小的节点占用更大的数据传输消耗时间，明显是降低系统的整体性能的，我们提出使得ferry针对不同性质的节点采取不同的访问策略。

根据节点的数据产生率对节点进行分集，使得同一集中节点的数据产生率在同一个范围内，其具体操作步骤如下：

网络中每个普通节点的有限缓存为b，节点i的缓存溢出时间为o_i ，节点i的数据信息产生率为r_i，它们之间的关系为                                                ，节点的数据产生率越大，它的数据产生量越大同时缓存溢出时间越小，根据数据产生率大小将节点进行分集，记为集合S_j。假设共分为M个集合，节点中的最大与最小数据产生率分别为r_max和r_min,则集合S_j中的节点满足：

从上式公式可得到不同的节点集合，其中S_j中节点的数据产生率幅度范围是，为S_j+1中节点数据产生率幅度范围的二倍，再由缓存溢出时间与数据产生率的关系，可得S_j中节点的溢出时间范围大小是S_j+1中节点溢出时间范围大小的1/2。

节点的数据产生率满足上述公式关系的节点划分为同一个集合，使得对集合S_j中节点的访问频率是S_j+1中节点访问频率的2倍，其中。

本发明中节点分集方法区分了网络中具有不同性质的节点，以利于中继节点Ferry能够对不同性质的节点采取相应的访问策略。

如图3所示为对节点进行区域划分流程图。由不同数据产生率所划分的集合，再根据集合中节点的坐标位置依次对集合中节点求横坐标或纵坐标平均值，根据平均值将一个区域划分为两个下层子区域，其中第j个节点集合S_j被划分为不超过2^j个子区域A_j，i（），且每个子区域至多被划分为两个下层子区域，具体操作步骤如下：

若对网络拓扑图中所有属于S_j中的节点根据其横坐标平均值划分为不同的区域A_j，i（），判断在第j层子区域A_j，i中是否有属于集合S_j+1中的节点，对区域中属于S_j+1的节点，计算所有节点纵坐标的平均值，根据纵坐标平均值再划分为两个下层子区域，进一步判断所划分的子区域中是否有属于集合S_j+2中的节点，如有继续根据各子区域中节点横坐标平均值或节点纵坐标的平均值重复上述方法进一步划分更小子区域，直至节点集合S_M中的节点被划分完毕。

首先在整个拓扑图区域A₁中选出属于集合S₁的所有节点，并根据所选节点的横坐标求平均值（x_i为集合S₁节点i的横坐标,N为所选节点总数），根据此数值在横坐标作一条平行于y轴的纵线将区域A₁划分为两个下层子区域A₂₁,A₂₂；对于划分好的子区域A_i，j，子区域中若存在属于节点集合S_i+1中的节点，则对子区域A_i，j中所有属于节点集合S_i+1中节点的纵坐标求平均值（y_i为集合S_i+1节点i的纵坐标）,再根据此数值在纵坐标作平行于x轴的横线将子区域A_i，j划分为两个下层子区域A_i+1，2^j_-1,A_i+1,2^j,依次对子区域进行横坐标和纵坐标划分，直至集合S_M中的节点被划分完毕。区域划分中，轮流对节点集合中节点的横坐标和纵坐标求平均值，分别作纵线或横线将集合中节点划分为不同区域。

对节点进行区域划分，得到了属于不同集合中节点所在的区域，对于中继节点下一步Ferry的路径选取提供了选择信息。

依次选择每层区域中下层子区域中不同集合中的节点，由选择的节点组成由中继节点Ferry访问的最短路径。

如图4所示为中继节点Ferry的路径选择流程示意图。根据划分的网络中节点集合，以及区域划分后不同集合中节点所在的区域，可得第i个节点集合S_i被划分为不超过2ⁱ个子区域A_i，j（）。从第一层区域中选择属于第一个节点集合中的节点，选择属于第一层区域中的第二层子区域中的第二个节点集合中的节点，依次类推。分别从每层区域中选择一个子区域A_i，j中属于节点集合S_i的节点，且下层区域为上层区域的子区域，选择的节点即为中继节点Ferry的下次路径中所要访问的节点，并得到历经所选节点的一次小路径，由所有小路径组合在一起形成的路径即为最终的路径。具体操作步骤如下：

首先在整个区域A₁中选取属于节点集S₁中的节点，然后在区域A₁的子集域A₂₁中选取属于节点集S₂中的节点，再在区域A₂₁的子集域A₃₁中选取属于节点集S₃中的节点，如此下去直到第个子区域（其中“”为下取整数，M为总节点集数），若此时前个节点集合中的节点数目小于总节点数目的一半，则节点选取到第+1个子区域，每次选取的节点即为此次路径中所要访问的节点，并根据节点位置得到一条经过这些节点的最短路径，在相连的两点路径附近如存在靠近的其他节点，可将靠近此路径的其他节点加入此路径中，即为此次Ferry的访问小路径；

第二次选取时，首先在整个区域A₁中选取属于节点集S₁中的节点，然后在区域A₁的子集域A₂₂中选取属于节点集S₂中的节点，再在区域A₂₂的子集域A₃₃中选取属于节点集S₃中的节点，如此下去直到第个子区域，若此时前个节点集合中的节点数目小于总节点数目的一半，则节点选取到第+1个子区域，每次选取的节点即为此次路径中所要访问的节点，并根据节点位置得到一条经过这些节点的最短路径，再可将靠近路径的其他节点也加入进来，即为此次Ferry的访问小路径；

依次重复下去，最终得到每次的小路径，其中总数目小于等于2^M-1。最后将每次选取的小路径组合成为一条大的路径，即为中继节点Ferry的最终路径。根据上述区域中节点的选取，对于未加入路径中的节点设置延迟访问，当达到访问延迟时间后对其进行访问。

根据公式（x为时间自变量，t_i为中继节点上次访问节点i的时间，t为即时时间，其中起始时间为0，n为节点数，T为中继节点一次路径访问所有节点的周期时间）计算节点i在t时刻的数据延迟时间，可将对节点i的方问时间延迟，而不必马上对位置偏远的低数据率节点进行访问，以此保证此类节点上数据的传输并减少不必要的访问。同时在选定节点的路径中，考虑在相连的两点路径附近是否存在靠近的其他节点，并将其加入此路径中。具体判定方式为：以两相邻的节点i，j为焦点，以（1+α%）d_ij为定长画一个椭圆，则位于椭圆内的节点加入到此次路径的访问中，其中d_ij为两相邻节点的距离长度，α根据网络中节点密度确定，随着密度的增加而减少。

采用上述方法，中继节点Ferry不再通过周期性访问网络中的所有节点，基于网络中节点的不同性质而对不同节点采取不同的访问策略，能够缩短网络中所有节点总的延迟时间，避免在相同访问方法下对高数据产生率节点带来的高延时以及对低数据产生率节点带来的资源浪费，加快了对一些节点的访问频率，有利于减少数据的传输延迟时间，解决现有路由技术的上述缺陷。

本发明适用于机会网络，特别是网络中节点的数据产生率相差较大，数据产生率越高的节点越靠近网络拓扑图的中心位置，并且此类节点所占比例较高的机会网络。