一种新的无线自组网双频分级路由方法

专利名称：一种新的无线自组网双频分级路由方法
技术领域：
本发明属于无线自组网通信领域，是一种能够支持大规模网络中 节点间快速、可靠地建立路由和传输数据，并能够降低无线传输中的 干扰，进一步提高网络容量的新的无线自组网双频分级路由方法，尤 其适用于具有异质通信单元且各通信单元协同、空间立体化联合作战 的战场通信环境。
背景技术：
无线自组网一般有两种结构平面结构和分级结构。平面结构的 网络比较简单，网络中所有节点的功能和地位平等，原则上不存在瓶 颈节点，网络比较健壮。但平面结构最大的缺点是网络规模受限，可 扩充性差。因此，为了降低节点成本，提供灵活、可靠的通信，并提 高无线自组网的可扩展性，大型网络中通常采用分级结构。 一种最常 用的分级结构是分簇网络结构，将网络划分为若干个簇，每个簇由一 个簇首和多个普通节点组成。簇首之间的通信需要借助于网关或分布 式网关节点完成，簇首和网关形成了高一级的网络。在高一级网络中， 又可以再分簇，形成更高一级的网络，直至最高级。在分簇结构中， 簇首和簇成员的身份可动态变化，节点仍然自动组网。簇首节点负责 簇间数据的转发、协调和管理。簇首可以预先指定，也可以由节点使 用算法选举产生。分级结构的网络根据硬件的配置不同，可以分为单频分级和多频 分级两种。单频率分级网络中只有一个通信频率，所有节点使用同一 频率通信，为了实现簇首之间的通信，要有网关节点的支持，簇首和 网关形成了高一级的网络。这种分级结构提高了网络的可扩充性，但 由于只有一个通信频率，所有节点仍处于同一冲突域中，对于大规模 网络仍存在着严重的无线传输干扰。另外，簇首之间不能直接通信， 相邻簇间的通信需要经过网关节点来跳转，增加了分组传输中的时不同级采用不同的通信频率。低级节点的通 信范围小，而高级节点要覆盖较大的通信范围。高级节点同时处于多 个级中，有多个频率，用不同的频率实现不同级的通信。低级节点由 簇首和它的普通成员组成，而高级节点通常只有簇首，簇首之间可以 采用较大的传输功率直接进行通信。这样，节点间的寻路方式为普 通节点到簇首，簇首再到普通节点或可达的其它簇首，直到找到目的 节点。但由于无线自组网中节点的移动性及能量的有限性，使得高级 网络中的节点即使采用最大传输功率也不是总能保证高级网络的连 通性。这样，采用前面所述的寻路方式就有可能找不到到达目的节点 的路由。发明内容本发明的目的在于提供一种能够支持大规模自组网中节点间快 速、可靠地建立路由和传输数据，并能够降低无线传输中的干扰，进 一步提高网络容量的新的无线自组网双频分级路由方法。本发明的技术方案是充分结合传统的单频分级与多频分级两种 路由方式各自的优缺点，提出一种新的无线自组网双频分级路由方 法，其特征是包括下列步骤建立网络结构、分级结构维护、寻找传 输路由、传输路由维护、路由差错控制和重新建立路由，其中，建立 网络结构步骤又包括建立低级网络结构和建立高级网络结构两个步 骤，寻找传输路由步骤包括单频分级路由和双频分级路由两种方式。所述的建立网络结构具体内容包括根据网络拓扑结构，采用簇 首选举方案将网络划分为若干个簇，形成簇首、普通节点和网关。其 中，簇首和它的普通成员及网关组成低一级网络，而各簇首之间组成 高一级网络。各低级网络节点通过在频段l上以最佳发射功率交互 HELLO报文，建立起低级网络结构，簇首维护簇的普通成员表及网 关表，普通节点记录本簇的簇首，网关则维护所有可达的簇首表；各 高级网络节点在频段2上以最大发射功率交互HELLO报文，建立起 高级网络结构，各簇首维护一张可达的其它簇首表。所述的分级结构维护具体内容包括各低级节点和高级节点通过 在各自的频段上周期性地交互HELLO报文来维护相应的网络结构，5当节点发现它所维护表格中的成员超过生存期时，则将其从成员表中 删除，各节点的状态也可能随之发生变化对于低级节点，当簇首发 现它的簇成员个数为0时，将自己的状态改为未分配；当簇的普通成 员发现自己的簇首已不存在时，将自己的状态改为未分配；当网关发 现它可达的簇首个数为1时，将自己的状态改为普通成员。所述的寻找传输路由具体内容包括传输路由以无线自组网典型 的路由协议AODV为基础，对所有未分配的节点仍采用AODV洪泛 的方式广播路由请求消息，而对于所有已加入簇结构的节点，采用的路由方式包括单频分级路由和双频分级路由两种在协议中设置一个快速路由发送次数的上限值，当发往同一个目的地的路由请求次数小于此上限值时，采用双频分级的路由方式普通节点到簇首，簇首再 到普通节点或可达的其它簇首，直到找到目的节点；而当此路由请求次数已超过上限值时，说明高级网络可能不连通，则采用单频分级的路由方式普通节点到簇首，簇首到网关，网关再到可达的其它簇首， 直到找到目的节点。各低级节点在频段1上以最佳发射功率进行通 信，而各高级节点在频段2上以最大发射功率进行通信。另外，在发 送路由请求报文RREQ过程中建立或更新反向路由以及返回路由回 复报文RREP过程中建立或更新正向路由时记录本条路由所使用的 信道，以保证数据包的正确传输。所述的传输路由维护具体内容包括对于洪泛路由及单频分级路由，各节点通过在频段1上周期性地交互HELLO报文来确认邻居的 存在，如节点在规定的时间间隔内连续多次没有收到其某一邻居节点 发来的HELLO报文，则认为该邻居节点已移动或故障，并将它到该 邻居节点的链路标为断开；而对于双频分级路由，各簇首通过在频段 2上周期性地交互HELLO报文来确认其可达的其它簇首的存在，如 节点在规定的时间间隔内连续多次没有收到其某一可达簇首发来的 HELLO报文，就认为该簇首已移动或故障，并将到它的链路标为断 开。所述的路由差错控制具体内容包括如果节点在使用某个链路时 发现该链路断开，则从路由表中删除包含该断开链路的路由，并发送 "路由出错"报文RERR通知受链路断开影响的节点，通知相关节点 将对应路由从各自的路由表中删除，沿途转发RERR的节点也删除自 己路由表中的对应路由，并停止在这条断开路由所述的重新建立路由具体内容包括某一节点如果需要发送数据 包，而当传输路由中断，发现到目的节点的路由己经不存在时，则该 节点将要传输的数据包进行缓存，为目的节点继续寻找并建立一条新 的路由，路由建立成功后，再将缓存里的数据包发送出去。本发明的效果是采用这种双频分级的路由方法，当高级网络连 通时，簇首节点之间可以直接进行通信，加快了路由査找的速度，并 且由于高级节点之间的通信与低级节点之间的通信不在同一个频段 上，降低了无线传输中的干扰，提高了网络的容量。而当高级网络不 连通时，仍采用单频分级的路由方式，保证了数据传输的可靠性。本路由方法已基于AODV路由协议在NS2网络仿真平台上进行了模拟。模拟结果表明，相对于传统的单频分级和双频分级的路由方 式，本双频分级的路由方法在分组数据的投递率、分组数据的丢包率、 分组数据端到端的平均延迟等方面都表现出了更好的性能。 下面结合附图和实施例对本发明做进一步的说明。


图l是本发明的程序步骤框图； 图2是发送HELLO分组流程图； 图3是接收HELLO分组流程图； 图4是发送RREQ分组流程图； 图5是接收RREQ分组流程图。
具体实施方式
本发明所需要的硬件支持是节点需配备两块具有不同通信频段 且发射功率可调的无线收发设备。如图1所示，本方法由建立网络结 构、分级结构维护、寻找传输路由、传输路由维护、路由差错控制和 重新建立路由六个步骤组成。其中，建立网络结构步骤又包括建立低 级网络结构和建立高级网络结构两个步骤，寻找传输路由步骤则包含 单频分级路由和双频分级路由两种方式。1)建立网络结构步骤根据网络拓扑结构，采用簇首选举方案将网络划分为若干个簇，形成簇首、普通节点和网关。其中，簇首和它的普通成员及网关组成 低一级网络，而各簇首之间组成高一级网络。各低级网络节点通过在频段1上以最佳发射功率交互HELLO报文，建立起低级网络结构， 簇首维护簇的普通成员表及网关表，普通节点记录本簇的簇首，网关 则维护所有可达的簇首表；各高级网络节点在频段2上以最大发射功 率交互HELLO报文，建立起高级网络结构，各簇首维护一张可达的 其它簇首表。需要注意的是，由于各低级节点是在频段l上以各自的 最佳发射功率交互HELLO报文的，因此可能出现单向信道的问题， 另外，无线信道中复杂的传播环境也可能导致单向信道的出现。通过 交互HELLO报文建立的簇结构须保证成员间的邻居关系是双向的。 发送和接收HELLO分组流程分别如图2和图3所示。图2中，发送HELLO分组流程包括下列步骤首先判断本节点 是否为簇首节点，如果是簇首，则在信道l上以最佳发射功率发送 HELLO分组，并在信道2上以最大发射功率发送HELLO分组；如 果本节点不是簇首节点，则仅在信道1上以最佳发射功率发送HELLO 分组。图3中，接收HELLO分组流程包括下列步骤首先判断本节点 是否是从信道l上接收到HELLO分组，如果是，则判断本节点与发 送节点之间的距离是否小于本节点的辐射半径，如果不小于，则本节 点和发送节点间的邻居关系是单向的，将分组释放，函数返回；如果 两节点间的距离小于本节点的辐射半径，则本节点和发送节点的邻居 关系是双向的，然后查看发送节点是否已存在于本节点的邻居列表 中，如果已存在，则更新此邻居节点的有效期，并建立或更新簇结构。 如果本节点的邻居列表中没有储存发送节点，则将此发送节点添加到 本节点的邻居列表中，并建立或更新簇结构，其具体内容包括普通 节点添加或更新簇首；簇首添加或更新普通成员或网关；网关添加或 更新可达簇首；普通节点若收到多个簇首的HELLO分组，则变为网 关。如果本节点不是在信道1上接收到HELLO分组，即是在信道2 上接收到的，则判断本节点是否为簇首节点，如果是簇首，则添加或 更新可达的其它簇首节点，如果本节点不是簇首，则将分组释放并返 回；各低级节点和高级节点通过在各自的频段上周期性地交互HELLO报文来维护相应的网络结构。当节点发现它所维护表格中的成员超过生存期时(节点在规定的时间间隔内连续多次没有收到其某一成员节点发来的HELLO报文，)，则将其从成员表中删除，各节点 的状态也可能随之发生变化对于低级节点，当簇首发现它的簇成员 个数为0时，将自己的状态改为未分配；当簇的普通成员发现自己的 簇首己不存在时，将自己的状态改为未分配；当网关发现它可达的簇首个数为1时，将自己的状态改为普通成员。采用簇首选举方案可以 进行簇结构的重建以及各簇成员的重新添加。3)寻找传输路由步骤传输路由以无线自组网典型的路由协议AODV为基础，对所有 未分配的节点仍采用AODV洪泛的方式广播路由请求消息，而对于 所有已加入簇结构的节点，采用的路由方式包括单频分级路由和双频 分级路由两种在协议中设置一个快速路由发送次数的上限值，当发 往同一个目的地的路由请求次数小于此上限值时，采用双频分级的路 由方式普通节点到簇首，簇首再到普通节点或可达的其它簇首，直 到找到目的节点；而当此路由请求次数已超过上限值时，说明高级网 络可能不连通，则采用单频分级的路由方式普通节点到簇首，簇首到网关，网关再到可达的其它簇首，直到找到目的节点。各低级节点在频段1上以最佳发射功率进行通信，而各高级节点在频段2上以最 大发射功率进行通信。另外，在发送路由请求报文RREQ过程中建 立或更新反向路由以及返回路由回复报文RREP过程中建立或更新 正向路由时记录本条路由所使用的信道，以保证发送数据时采用正确 的信道。发送和接收路由请求RREQ分组流程分别如图4和图5所不o图4中，发送RREQ分组流程包括下列步骤从路由表中查找 到目的节点的路由，判断路由是否有效，如果路由有效则函数返回， 如果路由无效，则判断上次发送的RREQ是否超时，如果没有超时， 则函数返回，如果超时，则判断路由请求次数是否己超过上限；如果 路由请求次数超过上限，则将路由请求次数清零，释放缓存的分组， 函数返回；如果路由请求次数没有超过上P艮，则将路由请求次数加1， 并重新设定TTL值及RREQ的超时时间；然后判断本节点是否未分 配，如果是未分配，则在信道1上广播RREQ分组，如果本节点已分配，则根据本节点在簇结构中的身份进行不同的操作如果本节点是普通成员，则判断邻居列表中是否存在目的节点，如果存在目的节点，则在信道1上向目的节点单播RREQ分组并返 回，如果不存在目的节点，则在信道1上向簇首节点单播RREQ分 组并返回。如果本节点不是普通成员，则继续判断本节点是否是簇首节点； 如果是簇首，则查找本节点所维护的普通成员表或网关表中是否存在 目的节点，如果存在目的节点，则在信道1上向目的节点单播RREQ 分组并返回；如果不存在目的节点，则继续判断快速路由请求次数是 否已超过上限，如果超过上限，则在信道1上向所有网关发送RREQ 分组，如果没有超过上限，则在信道2上向所有可达的其它簇首发送 RREQ分组；如果本节点不是簇首，则继续判断本节点是否为网关， 如果是网关则查看所维护的可达簇首表中是否存在目的节点，如果存 在目的节点，则在信道1上向目的节点单播RREQ分组并返回，如 果不存在目的节点，则在信道1上向所有可达簇首发送RREQ分组 并返回。如果本点也不是网关，则函数返回。图5中，节点接收到RREQ分组后，首先判断其是否为环路包， 如果是环路包，则释放分组并返回，如果不是环路包，则继续判断是 否为重复包，如果是重复包，则释放分组并返回，否则将此分组添加 到RREQ的广播ID表中，并添加或更新一条到源节点的反向路由， 并记录本路由的所使用的信道。然后再从路由表中査找到目的节点的 路由，如果本节点就是目的节点，则直接向源节点返回路由回复分组 RREP，如果本节点不是目的节点，则继续判断本节点是否有到目的 节点的新鲜路由，如果有新鲜路由，则直接向源节点返回路由回复分 组RREP，否则继续判断RREQ标识是否为快速路由査找标识；如果 RREQ标识不是快速路由查找标识，则在信道1上广播转发RREQ分 组，否则判断本节点的身份，然后进行不同的操作如果本节点是普通成员，则査看目的节点是否存在于本节点的邻 居列表中，如果存在，则在信道1上向目的节点转发RREQ分组并 返回，否则在信道1上向簇首转发RREQ分组并返回。如果本节点不是普通成员，则判断本节点是否簇首，如果是簇首， 则判断其普通成员表或网关表中是否存在目的节点，如果存在目的节 点，则在信道1上向目的节点转发RREQ分组并返回，如果不存在目的节点，则判断快速路由请求次数是否已超过上限，如果已超过上限，则在信道1上向所有网关转发RREQ分组，如果没有超过上限， 则在信道2上向所有可达的其它簇首转发RREQ分组。如果本节点 不是簇首，则判断本节点是否网关，如果是网关，则判断其维护的可 达簇首表中是否存在目的节点，如果存在目的节点，则在信道l上向 目的节点转发RREQ分组并返回，如果不存在，则在信道1上向所 有可达的其它簇首转发RREQ分组并返回。如果本节点也不是网关， 则函数返回。4) 传输路由维护步骤对于洪泛路由及单频分级路由，各节点通过在频段1上周期性地 交互HELLO报文来确认其邻居的存在，如节点在规定的时间间隔内 连续多次没有收到其某一邻居节点发来的HELLO报文，它就认为该 邻居节点已移动或故障，并将它到该邻居节点的链路标为断开。而对 于双频分级路由，各簇首通过在频段2上周期性地交互HELLO报文 来确认其可达簇首的存在，如节点在规定的时间间隔内连续多次没有收到其某一可达簇首发来的HELLO报文，它就认为该簇首已移动或 故障，并将到它的链路标为断开。5) 路由差错控制步骤如果节点在使用某个链路时发现该链路断开，它将从路由表中删 除包含该断开链路的路由，并发送"路由出错"报文RERR通知那些 受链路断开影响的节点，让它们将对应路由从各自的路由表中删除， 沿途转发RERR的节点也删除自己路由表中的对应路由，并停止在这 条断开路由上继续发送数据。6) 重新建立路由步骤当传输路由中断时，节点如果想要发送数据包，发现到目的节点 的路由已经不存在了，则该节点会将要传输的数据包缓存起来，然后 为目的节点继续寻找并建立一条路由。路由建立成功后，把缓存里的 数据包继续发送出去。
权利要求
1. 一种新的无线自组网双频分级路由方法，其特征是包括下列步骤建立网络结构、分级结构维护、寻找传输路由、传输路由维护、路由差错控制和重新建立路由，其中，建立网络结构步骤又包括建立低级网络结构和建立高级网络结构两个步骤，寻找传输路由步骤包括单频分级路由和双频分级路由两种方式。
2、 根据权利要求1所述的新的无线自组网双频分级路由方法， 其特征是所述的建立网络结构具体内容包括根据网络拓扑结构，采 用簇首选举方案将网络划分为若干个簇，形成簇首、普通节点和网关。 其中，簇首和它的普通成员及网关组成低一级网络，而各簇首之间组 成高一级网络。各低级网络节点通过在频段1上以最佳发射功率交互HELLO报文，建立起低级网络结构，簇首维护簇的普通成员表及网 关表，普通节点记录本簇的簇首，网关则维护所有可达的簇首表；各 高级网络节点在频段2上以最大发射功率交互HELLO报文，建立起 高级网络结构，各簇首维护一张可达的其它簇首表。
3、 根据权利要求1所述的新的无线自组网双频分级路由方法， 其特征是所述的分级结构维护具体内容包括各低级节点和高级节点 通过在各自的频段上周期性地交互HELLO报文来维护相应的网络结 构，当节点发现它所维护表格中的成员超过生存期时，则将其从成员 表中删除，各节点的状态也可能随之发生变化对于低级节点，当簇 首发现它的簇成员个数为O时，将自己的状态改为未分配；当簇的普 通成员发现自己的簇首已不存在时，将自己的状态改为未分配；当网 关发现它可达的簇首个数为1时，将自己的状态改为普通成员。
4、 根据权利要求1所述的新的无线自组网双频分级路由方法，其特征是所述的寻找传输路由具体内容包括传输路由以无线自组网典型的路由协议AODV为基础，对所有未分配的节点仍采用AODV 洪泛的方式广播路由请求消息，而对于所有已加入簇结构的节点，采用的路由方式包括单频分级路由和双频分级路由两种在协议中设置一个快速路由发送次数的上限值，当发往同一个目的地的路由请求次数小于此上限值时，采用双频分级的路由方式普通节点到簇首，簇 首再到普通节点或可达的其它簇首，直到找到目的节点；而当此路由请求次数已超过上限值时，说明高级网络可能不连通，则采用单频分级的路由方式普通节点到簇首，簇首到网关，网关再到可达的其它 簇首，直到找到目的节点。各低级节点在频段1上以最佳发射功率进 行通信，而各高级节点在频段2上以最大发射功率进行通信。另外，在发送路由请求报文RREQ过程中建立或更新反向路由以及返回路 由回复报文RREP过程中建立或更新正向路由时记录本条路由所使 用的信道，以保证数据包的正确传输。
5、 根据权利要求1所述的新的无线自组网双频分级路由方法，其特征是所述的传输路由维护具体内容包括对于洪泛路由及单频分级路由，各节点通过在频段1上周期性地交互HELLO报文来确认邻 居的存在，如节点在规定的时间间隔内连续多次没有收到其某一邻居 节点发来的HELLO报文，则认为该邻居节点已移动或故障，并将它 到该邻居节点的链路标为断开；而对于双频分级路由，各簇首通过在 频段2上周期性地交互HELLO报文来确认其可达的其它簇首的存 在，如节点在规定的时间间隔内连续多次没有收到其某一可达簇首发 来的HELLO报文，就认为该簇首己移动或故障，并将到它的链路标 为断开。
6、 根据权利要求1所述的新的无线自组网双频分级路由方法， 其特征是所述的路由差错控制具体内容包括如果节点在使用某个链 路时发现该链路断开，则从路由表中删除包含该断开链路的路由，并 发送"路由出错"报文RERR通知受链路断开影响的节点，通知相关 节点将对应路由从各自的路由表中删除，沿途转发RERR的节点也删 除自己路由表中的对应路由，并停止在这条断开路由上继续发送数 据。
7、 根据权利要求1所述的新的无线自组网双频分级路由方法， 其特征是所述的重新建立路由具体内容包括如果节点需要发送数据 包，而当传输路由中断，发现到目的节点的路由已经不存在时，则该 节点将要传输的数据包进行缓存，为目的节点继续寻找并建立一条新 的路由，路由建立成功后，将缓存里的数据包发送出去。
全文摘要
一种能够支持大规模无线自组网中节点间快速、可靠地建立路由和传输数据，能够降低无线传输中的干扰，进一步提高网络容量的新的无线自组网双频分级路由方法。技术方案是充分结合传统的单频分级与多频分级两种路由方式各自的优缺点，提出一种新的双频分级路由方法，其特征是包括下列步骤建立网络结构、分级结构维护、寻找传输路由、传输路由维护、路由差错控制和重新建立路由，其中，建立网络结构步骤又包括建立低级网络结构和建立高级网络结构两个步骤，寻找传输路由步骤包括单频分级路由和双频分级路由两种方式。
文档编号H04L12/56GK101262449SQ20081010512
公开日2008年9月10日 申请日期2008年4月25日 优先权日2008年4月25日
发明者刘海霞, 博 惠, 旭 李 申请人:北京交通大学