CN100591029C - A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree - Google Patents
A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree Download PDFInfo
- Publication number
- CN100591029C CN100591029C CN200710031834A CN200710031834A CN100591029C CN 100591029 C CN100591029 C CN 100591029C CN 200710031834 A CN200710031834 A CN 200710031834A CN 200710031834 A CN200710031834 A CN 200710031834A CN 100591029 C CN100591029 C CN 100591029C
- Authority
- CN
- China
- Prior art keywords
- node
- root
- nodes
- message
- tree
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Images
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种基于分区树的多跳无线自组织网络构建方法,包括各分区根节点的确定过程、根节点之间的互连过程、根节点之间互连路由维护过程、分区树的生成过程、分区树的动态维护过程和基于分区树的路由选择过程。本发明与传统的无线组网技术相比,是一种扩展性好、网络结构规模可控、网络系统开销小、路由效率高的新型多跳无线自组织网络构建方式,从而有效提高网络的传输效率和网络性能。
The invention discloses a method for constructing a multi-hop wireless self-organizing network based on a partition tree, including the determination process of each partition root node, the interconnection process between the root nodes, the interconnection route maintenance process between the root nodes, and the construction of the partition tree. The generation process, the dynamic maintenance process of the partition tree and the routing selection process based on the partition tree. Compared with the traditional wireless networking technology, the present invention is a new type of multi-hop wireless self-organizing network construction method with good scalability, controllable network structure scale, small network system overhead and high routing efficiency, thereby effectively improving network transmission efficiency and network performance.
Description
技术领域 technical field
本发明属于无线通信网络技术领域,具体来说涉及一种多跳无线自组织网络的构建方法与路由技术。The invention belongs to the technical field of wireless communication networks, and in particular relates to a construction method and routing technology of a multi-hop wireless self-organizing network.
背景技术 Background technique
无线通信系统有两种网络结构:有基础设施网络和无基础设施网络。有基础设施网络结构通常是对有线通信网的一种扩展,有线网络被用作骨干网,连接到特殊的有线/无线转接点,即基站BS(Base Station)或接入点AP(Access Point),它们负责协调覆盖区域内的移动节点通过一个或多个传输信道接入网络。传输信道可以是FDMA(Frequency-DivisionMultiple Access)中的某个频带,也可以是TDMA(Time Division Multiple Access)中的某个时隙,或者是CDMA(Code Division Multiple Access)中的某个码道。BS或AP与有线骨干网相连并且覆盖一个区域,必须预先规划、设计和布署,构成有基础设施网络结构,如蜂窝移动通信系统、无线局域网等。There are two types of network structures in wireless communication systems: networks with infrastructure and networks without infrastructure. The infrastructure network structure is usually an extension of the wired communication network. The wired network is used as the backbone network and connected to a special wired/wireless transfer point, that is, the base station BS (Base Station) or the access point AP (Access Point ), they are responsible for coordinating the mobile nodes in the coverage area to access the network through one or more transmission channels. The transmission channel can be a certain frequency band in FDMA (Frequency-Division Multiple Access), or a certain time slot in TDMA (Time Division Multiple Access), or a certain code channel in CDMA (Code Division Multiple Access). The BS or AP is connected to the wired backbone network and covers an area. It must be pre-planned, designed and deployed to form an infrastructure network structure, such as a cellular mobile communication system and a wireless local area network.
无基础设施网络结构一般也称为Ad Hoc网络或无线自组织网络,简称无线自组网,它是由多个移动节点组成的多跳无线网络。这是由于无线自组织网络具有动态变化的网络拓扑结构,采用异步通信技术,多个节点共享同一个通信信道。为了提高信道利用率,移动节点的发射功率较低,加上信号受到无线信道中的噪声、信道衰落和障碍物的影响,使得移动节点的通信距离受到限制,因此,无线自组织网络的无线信道共享方式不是一跳共享的,而是多跳共享广播信道,如图1所示,节点A和节点E无法直接通信,但节点A的数据可以通过路径A→B→C→D→E多跳到达节点E,从而完成通信。移动节点之间是一种对等的关系,每个节点都具备路由器的功能,可以通过存储转发技术帮助其他节点构成通信链路。与有基础设施网络最大的区别是不需要预设的基础实施(BS和AP),网络的组织是临时的、按需的、自动的,采用分布式的控制方式。由此,无线自组织网络特别适用于要求临时、快速组网的某些特殊环境,如军事领域、灾难求援、会议室、家庭等场合。The infrastructure-free network structure is generally also called Ad Hoc network or wireless ad hoc network, referred to as wireless ad hoc network, which is a multi-hop wireless network composed of multiple mobile nodes. This is because the wireless ad hoc network has a dynamically changing network topology and uses asynchronous communication technology, and multiple nodes share the same communication channel. In order to improve the channel utilization, the transmission power of the mobile node is low, and the signal is affected by the noise, channel fading and obstacles in the wireless channel, so that the communication distance of the mobile node is limited. Therefore, the wireless channel of the wireless ad hoc network The sharing method is not one-hop sharing, but multi-hop sharing of the broadcast channel. As shown in Figure 1, node A and node E cannot communicate directly, but the data of node A can be multi-hop through the path A→B→C→D→E Arrives at node E, thus completing the communication. There is a peer-to-peer relationship between mobile nodes, and each node has the function of a router, which can help other nodes form communication links through store-and-forward technology. The biggest difference from a network with infrastructure is that it does not require a preset infrastructure (BS and AP), and the organization of the network is temporary, on-demand, and automatic, and adopts a distributed control method. Therefore, the wireless self-organizing network is especially suitable for some special environments that require temporary and fast networking, such as military fields, disaster relief, conference rooms, homes, and other occasions.
作为一种无中心分布控制网络,无线自组网是一种自治的无线多跳网络,整个网络没有固定的基础设施,可以在不利用或不便利用现有网络基础设施的情况下,提供一种通信支撑环境,拓宽了移动网络的应用场合。在自组网中每个节点不仅能移动,而且都兼有路由器和主机两种功能,能完成发现和维持到其他节点的路由,以任意的方式动态地保持与其他节点的联系。因此,无线自组网的突出特点在于“自组织性”、“多跳组网”、“分布式控制”和“动态变化的网络拓扑结构”。As a distributed control network without a center, the wireless ad hoc network is an autonomous wireless multi-hop network. The entire network has no fixed infrastructure and can provide an The communication support environment broadens the application occasions of the mobile network. In the ad-hoc network, each node can not only move, but also has two functions of router and host, which can complete the discovery and maintain the route to other nodes, and dynamically maintain contact with other nodes in any way. Therefore, the prominent features of wireless ad hoc networks are "self-organization", "multi-hop networking", "distributed control" and "dynamically changing network topology".
针对无线自组网的特点,组网方式不同于有中心接入并且是单跳网络的包含固定基础网络设施的网络,需要构建一种新型的、具有良好可扩展性的网络结构,因为自组网的多跳、动态本质导致它的配置信息不可能使全网所有节点都严格地同步更新,如果扩展性不好,当网络中存在大量可移动节点的情况下,网络的性能和通信业务质量都会受到影响。According to the characteristics of the wireless ad hoc network, the networking method is different from the network with a central access and a single-hop network containing fixed infrastructure network facilities. It is necessary to build a new type of network structure with good scalability, because the ad hoc The multi-hop and dynamic nature of the network makes it impossible for all nodes in the entire network to update its configuration information strictly synchronously. If the scalability is not good, when there are a large number of mobile nodes in the network, the performance of the network and the quality of communication services will be affected. will be affected.
初始的无线自组网是一种平面结构,网络中各节点地位是相同的,能够建立无线链路的节点之间构成邻居关系。平面结构的主要优点是网络中没有特殊的节点,网络流量均匀地分散在网络中,路由算法易于实现;主要缺点是可扩展性差,在一定程度上限制了网络的规模。为了降低自组织网络的系统开销、提高网络路由的效率、解决自组织网络的扩展性问题,可以对网络进行逻辑划分,某些在地里空间上相邻的节点构成一个相对独立的区域,使整个网络由若干个逻辑上相对独立的分区构成,实现网络的分层结构。分层网络结构可扩展性好,适用于大型网络的构建。The initial wireless ad hoc network is a flat structure, the status of each node in the network is the same, and the nodes that can establish wireless links form a neighbor relationship. The main advantage of the planar structure is that there are no special nodes in the network, the network traffic is evenly distributed in the network, and the routing algorithm is easy to implement; the main disadvantage is that the scalability is poor, which limits the scale of the network to a certain extent. In order to reduce the system overhead of the self-organizing network, improve the efficiency of network routing, and solve the scalability problem of the self-organizing network, the network can be logically divided, and some adjacent nodes in the ground space form a relatively independent area, so that The entire network is composed of several logically independent partitions to realize the hierarchical structure of the network. The layered network structure has good scalability and is suitable for the construction of large-scale networks.
路由协议与网络结构密切相关,按照路由协议所依据的网络逻辑拓扑结构形式的不同,无线自组网路由协议可分为平面结构路由协议和分层结构路由协议。在平面结构路由协议中,所有节点都处于同一平面中,每个节点的功能也都相同,路由协议实现相对容易。但当无线自组网规模增大,平面结构路由协议就会因链接和处理开销的增加而变得不适用,此时就需要采用分级路由技术以获得可扩展的有效路由,也即分层结构路由协议。分层结构路由协议可以降低开销和减少拓扑结构变化对路由带来的影响。Routing protocols are closely related to the network structure. According to the different logical topological structures of the network on which the routing protocols are based, wireless ad hoc network routing protocols can be divided into planar routing protocols and hierarchical routing protocols. In the flat structure routing protocol, all nodes are in the same plane, and the functions of each node are also the same, so the routing protocol is relatively easy to implement. However, when the scale of the wireless ad hoc network increases, the flat structure routing protocol will become inapplicable due to the increase in link and processing overhead. At this time, it is necessary to use hierarchical routing technology to obtain scalable and effective routing, that is, hierarchical structure Routing Protocol. Hierarchical routing protocols can reduce overhead and reduce the impact of topology changes on routing.
在目前的自组织网络研究中,已提出了一些分层网络结构及路由协议的构建方法:In the current self-organizing network research, some hierarchical network structures and routing protocol construction methods have been proposed:
(1)自组网路标路由协议LANMAR(Landmark Ad hoc Routing Protocol)。LANMAR将整个网络划分为许多逻辑子网,每个逻辑子网中的成员很可能趋向于在一起作为一个整体移动,而且在每个逻辑子网中选择一个节点作为界标(Landmark)节点,依靠Landmark节点进行全网范围内数据分组的路由。LANMAR的每个节点都维护两种路由:到自己某个限定范围内所有节点的本地路由和到网络中所有Landmark节点的距离矢量路由。当目的节点在本地路由范围内时,根据本地路由转发数据分组;否则首先向目的节点所属逻辑子网的Landmark节点转发,一旦目的节点出现某一中间节点的本地路由范围内时,就根据中间节点的本地路由进行转发。LANMAR减少了控制开销和路由表大小,是一种易于扩展的路由框架。(1) LANMAR (Landmark Ad hoc Routing Protocol). LANMAR divides the entire network into many logical subnets, members in each logical subnet are likely to tend to move together as a whole, and select a node in each logical subnet as a landmark (Landmark) node, relying on Landmark Nodes route data packets across the network. Each node of LANMAR maintains two kinds of routes: the local route to all nodes within a certain limited range and the distance vector route to all Landmark nodes in the network. When the destination node is within the range of the local route, the data packet is forwarded according to the local route; otherwise, it is first forwarded to the Landmark node of the logical subnet to which the destination node belongs. The local route for forwarding. LANMAR reduces control overhead and routing table size, and is an easy-to-extend routing framework.
(2)区域路由协议ZRP(Zone Routing Protocol)。ZRP以多范围(Multi-scope)技术为基础,将整个网络分成若干个以节点为中心,一定的跳数为半径的虚拟区,构建一种区域路由框架。在区域内采用先应式路由协议时刻维护着路由信息,区域外采用反应式路由协议按需进行路由选择,且区域的大小可以进行调整,每个区域的半径长度可以由用户设定,以适应局部或暂时的网络变化,使网络的整体性能最佳。(2) Zone Routing Protocol ZRP (Zone Routing Protocol). Based on the multi-scope technology, ZRP divides the entire network into several virtual areas with nodes as the center and a certain number of hops as the radius, and constructs a regional routing framework. In the area, the proactive routing protocol is used to maintain routing information at all times, and the reactive routing protocol is used outside the area to select routes on demand, and the size of the area can be adjusted. The radius length of each area can be set by the user to suit Local or temporary network changes to optimize the overall performance of the network.
(3)虚拟基站VBS(Virtual Base Station)。VBS的基本思想是模仿移动蜂窝网的结构和操作,为无线自组网设计一种集中式的体系结构--虚拟基站结构,并以此为基础设计路由协议。根据某种原则,网络中的一些节点被其邻近节点选为虚拟基站,负责管理数据分组的转发,当节点发送数据时,发送至自己的虚拟基站即可,由虚拟基站负责先转发至目的节点所属的虚拟基站,然后再转发至目的节点。即使两个节点属于同一个虚拟基站,也需要依靠虚拟基站转发,不能直接通信。虚拟基站还接收其他虚拟基站转发的、目的节点在自己管辖范围内的分组并转发至目的节点。VBS有利于提供通信的QoS保证和自组网移动用户的管理。(3) Virtual base station VBS (Virtual Base Station). The basic idea of VBS is to imitate the structure and operation of the mobile cellular network, design a centralized system structure for the wireless ad hoc network - virtual base station structure, and design routing protocols based on this. According to a certain principle, some nodes in the network are selected as virtual base stations by their neighboring nodes, responsible for managing the forwarding of data packets. When a node sends data, it can be sent to its own virtual base station, and the virtual base station is responsible for forwarding to the destination node first. The virtual base station to which it belongs, and then forward it to the destination node. Even if two nodes belong to the same virtual base station, they need to rely on the virtual base station for forwarding and cannot communicate directly. The virtual base station also receives packets forwarded by other virtual base stations and the destination node is within its jurisdiction and forwards them to the destination node. VBS is beneficial to provide communication QoS guarantee and management of mobile users in ad hoc networks.
(4)群首网关交换路由CGSR(Clusterhead Gateway Switch Routing)。CGSR是在DSDV(Destination-Sequenced Distance Vector)协议的基础上结合分级路由机制设计的,所使用的网络结构是整个网络被划分为重叠的群(Cluster),在每个群中选出一个群首,管理群中的其他的成员,控制对信道的访问,进行路由及带宽分配。所有在群首通信范围一跳内的节点都属于该群,在两个以上群首通信范围一跳内的节点称为网关节点,两个群首不能直接通信,必须通过网关节点。CGSR中只有群首和网关节点才转发分组,减少了路由中涉及的节点个数。(4) Clusterhead Gateway Switch Routing CGSR (Clusterhead Gateway Switch Routing). CGSR is designed on the basis of the DSDV (Destination-Sequenced Distance Vector) protocol combined with a hierarchical routing mechanism. The network structure used is that the entire network is divided into overlapping clusters (Cluster), and a cluster leader is selected in each cluster. , manage other members in the group, control access to channels, and perform routing and bandwidth allocation. All the nodes within one hop of the communication range of the group leader belong to the group, and the nodes within one hop of the communication range of two or more group leaders are called gateway nodes. Two group leaders cannot communicate directly, but must pass through the gateway node. In CGSR, only the cluster leader and the gateway node forward packets, which reduces the number of nodes involved in routing.
(5)分级状态路由HSR(Hierarchical State Routing)。HSR是一种在逻辑上分为多层的分级链路状态协议,它将移动节点进行逻辑划分并多层次分群,节点分为三类:群首节点、网关节点、内部节点,整个网络由分群和群首组成。协议中每个节点都至少有一个HID(Hierarchical ID)表示的分级地址,低层的群首可作为高层的成员。每个节点监视并在群内广播其邻居节点的状态信息,群首总结本群的链路状态消息,并在处于更高一层的邻居群首中传播。上层节点向其下层的群内成员广播上层的链路状态信息,最后每个节点都得到以HID表示的全部节点的分级路由信息,并汇总到该节点的HSR表中。物理分群中的各个节点相互广播其链路信息,群首负责对分群节点的信息进行总结并通过网关向邻近群首发送信息。HSR中每个节点又具有逻辑地址,根据节点的逻辑地址对其位置进行管理,在每个逻辑子网内至少存在一个归属代理(Home Agent),负责管理本子网内节点逻辑地址与当前物理地址之间的对应关系,并为所管理的节点转发数据分组。节点需要向归属代理进行注册,通告最新的物理地址。由于采用网络的逻辑地址与分级地址进行路由选择,因此可以适应网络结构的变化。(5) Hierarchical State Routing HSR (Hierarchical State Routing). HSR is a hierarchical link state protocol that is logically divided into multiple layers. It logically divides mobile nodes into multi-level clusters. Nodes are divided into three categories: cluster leader nodes, gateway nodes, and internal nodes. The entire network is divided into clusters and group leaders. Each node in the protocol has at least one hierarchical address represented by HID (Hierarchical ID), and the low-level group leader can be a member of the high-level group. Each node monitors and broadcasts the state information of its neighbor nodes in the group, and the group leader summarizes the link state information of the group and spreads it among the neighbor group leaders at a higher level. The upper layer node broadcasts the link state information of the upper layer to the members of the lower layer group, and finally each node obtains the hierarchical routing information of all nodes represented by HID, and summarizes it into the HSR table of the node. Each node in the physical grouping broadcasts its link information to each other, and the group leader is responsible for summarizing the information of the grouping nodes and sending the information to the adjacent group leader through the gateway. Each node in the HSR has a logical address, and its location is managed according to the logical address of the node. There is at least one home agent (Home Agent) in each logical subnet, which is responsible for managing the logical address and current physical address of the node in the subnet. The corresponding relationship between them, and forward data packets for the managed nodes. The node needs to register with the home agent and announce the latest physical address. Since the logical address and hierarchical address of the network are used for routing selection, it can adapt to changes in the network structure.
以上技术中,(1)适应于节点比较密集的网络,但在漂移节点和孤立节点数目过多的情况下,协议的控制和存储开销较大;(2)可以根据网络特性对节点的路由区域半径进行调整,使系统的整体路由开销最小,但是采用何种路由区域半径的调整方法,对其性能的影响较大;(3)虽然有利于提供通信业务的QoS保证,但在网络中节点移动速度较高的情况下,维护虚拟基站及路由的开销较大;(4)可以通过使用群首--网关序列来高效地传递数据分组,但由于限定分组的传输必须经过群首网关序列,有可能产生非最优路径;(5)协议比较复杂,得到的路径可能为非最优路径,当网络中节点移动速度较高时,路由开销较大。这些已有的网络分层构建方法在可靠性、开销控制、有效性和复杂性等方面还不能很好地满足多跳无线自组织网络的要求。Among the above technologies, (1) it is suitable for networks with relatively dense nodes, but in the case of too many drifting nodes and isolated nodes, the control and storage overhead of the protocol is relatively large; (2) the routing area of nodes can be adjusted according to the characteristics of the network The radius is adjusted to minimize the overall routing overhead of the system, but the method of adjusting the radius of the routing area has a greater impact on its performance; (3) Although it is beneficial to provide QoS guarantees for communication services, nodes move in the network When the speed is high, the overhead of maintaining virtual base stations and routing is relatively large; (4) data packets can be efficiently transmitted by using the cluster leader-gateway sequence, but because the transmission of the limited packet must pass through the cluster leader gateway sequence, there are A non-optimal path may be generated; (5) The protocol is more complicated, and the obtained path may be a non-optimal path. When the moving speed of nodes in the network is high, the routing overhead is relatively large. These existing network layered construction methods can not meet the requirements of multi-hop wireless ad hoc networks in terms of reliability, overhead control, effectiveness and complexity.
发明内容 Contents of the invention
本发明的目的针对现有技术的不足提供一种基于分区树的多跳无线自组织网络构建方法,实现一种网络结构规模可控、扩展性好,并且网络系统开销小的多跳无线自组织网络,有效地提高网络的路由效率和网络性能。The object of the present invention is to provide a method for constructing a multi-hop wireless ad hoc network based on a partition tree to realize a multi-hop wireless ad hoc network structure with controllable network structure, good scalability, and small network system overhead. network, effectively improving the routing efficiency and network performance of the network.
一种基于分区树的多跳无线自组织网络构建方法,其特征在于包括各分区中心节点(称为根节点)的确定过程、根节点之间的互连过程、根节点之间互连路由维护过程、分区树的生成过程、分区树的动态维护过程和基于分区树的路由选择过程,如图2所示。所述的各分区中心节点(根节点)的确定过程、根节点之间的互连过程、根节点之间互连路由维护过程、分区树的生成过程、分区树的动态维护过程和基于分区树的路由选择过程分别采用下面的具体步骤实现。A method for constructing a multi-hop wireless self-organizing network based on a partition tree, characterized in that it includes the determination process of each partition center node (called root node), the interconnection process between root nodes, and the maintenance of interconnection routes between root nodes The process, the generation process of the partition tree, the dynamic maintenance process of the partition tree and the routing selection process based on the partition tree are shown in Figure 2. The process of determining the central node (root node) of each partition, the interconnection process between the root nodes, the interconnection routing maintenance process between the root nodes, the generation process of the partition tree, the dynamic maintenance process of the partition tree and the process based on the partition tree The routing selection process is realized by the following specific steps respectively.
各分区中心节点(根节点)的确定过程,其具体步骤包括:The process of determining the central node (root node) of each partition, its specific steps include:
(1)初始网络中的所有节点处于平等的地位,各节点都具有网络唯一标识符(ID或地址),各节点类型均设置为“初始节点”;(1) All nodes in the initial network are on an equal footing, each node has a network unique identifier (ID or address), and each node type is set to "initial node";
(2)根据节点间的相互连接关系,采用下述的方式一或方式二在网络中选取某些节点确定为分区的中心节点,这些被选取的分区中心节点称为根节点,它们的节点类型设置为“根节点”;(2) According to the mutual connection relationship between nodes, select some nodes in the network to determine as the central nodes of the partition using the following
方式一:通过手工方式采用静态配置的方法确定各分区的根节点,根节点的配置信息至少包括节点类型等基本参数;Method 1: manually determine the root node of each partition by static configuration, and the configuration information of the root node includes at least basic parameters such as node type;
方式二:通过根节点自动发现的方式;首先给定一规则,确定成为根节点必须满足的条件(如ID Number、邻居节点的个数、处理能力大小、剩余电量的大小、稳定性高低或其他可衡量的量化值);然后实施根节点自动发现过程:从网络中任选一个节点(一般可以选择方便管理的节点),向全网广播根节点自动发现请求消息RADRQ(Root AutoDiscoveringReQuest),该分组中包含源节点ID、消息类型、根节点选择条件等内容,RADRQ消息的格式如图3所示。所有节点都对收到的RADRQ消息进行转发,并记录收到该消息的邻居ID,满足根节点选择条件的节点向源节点回复应答消息RADRP(Root AutoDiscoveringRePly),通知自己已经成为根节点,RADRP沿RADRQ的反向路由到达源节点,RADRP消息的格式如图4所示。通过全部返回的RADRP消息可以获取全网根节点的信息。Method 2: through the automatic discovery of the root node; first, a rule is given to determine the conditions that must be met to become the root node (such as ID Number, the number of neighbor nodes, processing capacity, remaining power, stability or other measurable quantified value); then implement the root node automatic discovery process: choose a node from the network (generally you can choose a node that is convenient for management), and broadcast the root node automatic discovery request message RADRQ (Root AutoDiscoveringReQuest) to the whole network, the group Include the source node ID, message type, root node selection conditions and other content, the format of the RADRQ message is shown in Figure 3. All nodes forward the received RADRQ message, and record the neighbor ID that received the message, and the node that meets the root node selection condition replies to the source node with a response message RADRP (Root AutoDiscovering Reply), notifying itself that it has become the root node, and RADRP follows The reverse route of RADRQ reaches the source node, and the format of the RADRP message is shown in Figure 4. Information about the root node of the entire network can be obtained through all returned RADRP messages.
(3)根节点广播自己的节点信息,信息内容至少包括节点ID、节点类型;(3) The root node broadcasts its own node information, and the information content includes at least node ID and node type;
(4)根节点记录收到的其他根节点的信息。(4) The root node records the received information of other root nodes.
分区中心节点(根节点)确定过程的流程如图5所示。The process of determining the partition center node (root node) is shown in FIG. 5 .
根节点之间的互连过程,其具体步骤包括:The interconnection process between root nodes, the specific steps include:
(1)根节点通过收到其他根节点的广播消息获取其他根节点的信息;(1) The root node obtains the information of other root nodes by receiving broadcast messages from other root nodes;
(2)ID Number小的根节点(源节点)向ID Number大的根节点(目的节点)广播发送路由请求消息RREQ(Route Request);或者是ID Number大的根节点(源节点)向IDNumber小的根节点(目的节点)广播发送路由请求消息RREQ;RREQ的内容包括消息类型、目的节点ID、目的节点序列号、源节点ID、源节点序列号等;(2) The root node (source node) with a small ID Number broadcasts and sends a routing request message RREQ (Route Request) to the root node (destination node) with a large ID Number; The root node (destination node) broadcasts and sends the routing request message RREQ; the content of RREQ includes message type, destination node ID, destination node serial number, source node ID, source node serial number, etc.;
(3)收到RREQ的中间节点根据RREQ中的信息,建立到源节点的路由;(3) The intermediate node that receives the RREQ sets up a route to the source node according to the information in the RREQ;
(4)如果中间节点有最新的到达目的根节点的路由,则通过应答消息RREP(RouteReply)回复该RREQ,否则继续广播该RREQ消息;RREP的内容包括消息类型、目的节点ID、目的节点序列号、源节点ID等;(4) If the intermediate node has the latest route to the destination root node, then reply the RREQ by reply message RREP (RouteReply), otherwise continue to broadcast the RREQ message; the content of RREP includes message type, destination node ID, destination node serial number , source node ID, etc.;
(5)目的根节点收到RREQ后,比较收到的所有RREQ消息,选取一条最优的路由(最优的条件可以是跳数最少、或时延最小、或能量消耗最小、或稳定度最高或其他可衡量的量化值等);(5) After receiving the RREQ, the destination root node compares all received RREQ messages, and selects an optimal route (the optimal condition can be the least number of hops, or the smallest delay, or the smallest energy consumption, or the highest stability or other measurable quantitative values, etc.);
(6)目的根节点沿最优路由的反向路由向源根节点回复应答消息RREP;(6) The destination root node replies to the source root node with a response message RREP along the reverse route of the optimal route;
(7)收到RREP的中间节点建立到目的根节点的路由,并设置自己的节点类型为“互连节点”;(7) The intermediate node that receives the RREP establishes a route to the destination root node, and sets its own node type as "interconnected node";
(8)收到RREP的源根节点建立到目的根节点的路由。(8) The source root node receiving the RREP establishes a route to the destination root node.
根节点之间互连过程的流程如图6所示。The flow of the interconnection process between root nodes is shown in Figure 6.
根节点之间互连路由维护过程,其具体步骤包括:The specific steps of the interconnection routing maintenance process between root nodes include:
(1)根节点与互连节点都周期性地向相邻的互连节点或根节点发送一个特定的确认消息(如“Hello消息”)来确保路由的有效性;(1) Both the root node and the interconnection node periodically send a specific confirmation message (such as "Hello message") to the adjacent interconnection node or root node to ensure the validity of the route;
(2)如果根节点或互连节点检测到下一跳不可达,就向利用该损坏链路的活跃上游互连节点或根节点发送RERR(Route ERRor)消息;RERR的内容包括消息类型、不可达的目的节点ID、不可达的目的节点序列号、不可达的节点个数等;(2) If the root node or interconnection node detects that the next hop is unreachable, it sends a RERR (Route ERRor) message to the active upstream interconnection node or root node utilizing the damaged link; the content of RERR includes message type, unreachable The ID of the destination node reached, the serial number of the destination node unreachable, the number of unreachable nodes, etc.;
(3)发送或收到这个RERR消息的互连节点将自己的节点类型设置为“初始节点”;(3) The interconnection node that sends or receives this RERR message sets its own node type as "initial node";
(4)收到这个RERR消息的互连节点再依次将该RERR消息转发到它们各自的活跃邻居互连节点或根节点;(4) The interconnected nodes receiving the RERR message forward the RERR message to their respective active neighbor interconnected nodes or root nodes in turn;
(5)源根节点在收到该RERR消息后,则发起新的互连过程。(5) After receiving the RERR message, the source root node initiates a new interconnection process.
分区树的生成过程,其具体步骤包括:The generation process of the partition tree, its specific steps include:
(1)定义“树节点”为加入到分区树中的节点;节点的“深度”为“树节点”与根节点之间的跳数,根节点设置自己的深度为0,初始节点、互连节点的深度为空;(1) Define "tree node" as the node added to the partition tree; the "depth" of the node is the number of hops between the "tree node" and the root node, the root node sets its own depth to 0, the initial node, interconnection The depth of the node is null;
(2)根节点、树节点周期性地广播“分区树建立消息”,消息的内容包括节点ID、节点类型、节点深度、子孙节点数、其他可选参数(包括邻居节点数、剩余电量、处理能力、稳定性等);“分区树建立消息”格式如图7所示;(2) The root node and the tree node periodically broadcast the "partition tree establishment message". capability, stability, etc.); the format of the "partition tree establishment message" is shown in Figure 7;
(3)收到“分区树建立消息”的初始节点设置自己的类型为“树节点”、自己的深度在“分区树建立消息”中的深度上加1、父节点设置为“分区树建立消息”中节点ID,并向父节点回复“树节点更新消息”,消息的内容包括节点ID、节点类型、节点深度、子孙节点数、节点路由列表;“树节点更新消息”格式如图8所示;(3) The initial node that receives the "Partition Tree Establishment Message" sets its own type as "Tree Node", its own depth plus 1 to the depth in the "Partition Tree Establishment Message", and the parent node is set to "Partition Tree Establishment Message" ", and reply the "tree node update message" to the parent node. The content of the message includes node ID, node type, node depth, number of descendant nodes, and node routing list; the format of the "tree node update message" is shown in Figure 8 ;
(4)父节点收到“树节点更新消息”后,更新自己的子孙节点数、节点路由列表,并继续向自己的父节点发送“树节点更新消息”,直到根节点;(4) After the parent node receives the "tree node update message", it updates its descendant node number and node routing list, and continues to send the "tree node update message" to its parent node until the root node;
(5)如果初始节点收到多个“分区树建立消息”,将根据给定的选择规则选取其中一个消息予以回复,丢弃其余的“分区树建立消息”。选择规则为比较节点深度、子孙节点数和其他可选参数,选取最优的节点作为自己的父节点;(5) If the initial node receives multiple "Partition Tree Establishment Messages", it will select one of the messages to reply according to the given selection rules, and discard the rest of the "Partition Tree Establishment Messages". The selection rule is to compare the node depth, the number of descendant nodes and other optional parameters, and select the optimal node as its parent node;
(6)如果时间T(T>0)后还有初始节点由于只与互连节点相连无法加入分区树,这时与该初始节点相邻的所有互连节点中的一个升级为根节点,并从最近的根节点获取其他根节点的路由信息,并通知其他根节点自己已升级成为根节点;(6) If after time T (T>0) there is still an initial node that cannot join the partition tree because it is only connected to the interconnection node, then one of all the interconnection nodes adjacent to the initial node is upgraded to the root node, and Obtain the routing information of other root nodes from the nearest root node, and notify other root nodes that they have been upgraded to become root nodes;
(7)直到所有的初始节点加入到分区树中成为树节点;(7) until all initial nodes are added to the partition tree to become tree nodes;
(8)互连节点不发送“分区树建立消息”,收到“分区树建立消息”的根节点和互连节点将丢弃该分组。(8) The interconnection node does not send the "Partition Tree Establishment Message", and the root node and interconnection node that receive the "Partition Tree Establishment Message" will discard the packet.
分区树生成过程的流程如图9所示。The process flow of the partition tree generation process is shown in FIG. 9 .
分区树的动态维护过程,其具体步骤包括:The dynamic maintenance process of the partition tree, its specific steps include:
(1)子节点通过父节点周期性发送的“分区树建立消息”来识别父节点是否仍然存在;(1) The child node identifies whether the parent node still exists through the "partition tree establishment message" periodically sent by the parent node;
(2)父节点通过与子节点之间的信息交换来识别子节点是否仍然存在,如果在规定的时间内子节点没有信息需要发给父节点,则子节点主动发送一个特定的消息(如“Hello消息”)来维持它们之间的父子邻接关系;(2) The parent node identifies whether the child node still exists by exchanging information with the child node. If the child node has no information to send to the parent node within the specified time, the child node actively sends a specific message (such as "Hello message") to maintain the parent-child adjacency relationship between them;
(3)如果父节点检测到某个子节点的邻接关系已不存在,则将该子节点从邻接关系表中删除,更新自己的子孙节点数、节点路由列表,并通过“树节点更新消息”通告自己的父节点;(3) If the parent node detects that the adjacency relationship of a certain child node no longer exists, it will delete the child node from the adjacency relationship table, update its own descendant node number, node routing list, and notify through the "tree node update message" own parent node;
(4)如果子节点检测到父节点的邻接关系已经不存在,则设置自己的类型为“初始节点”,并通过“树节点释放消息”通告自己所有的子孙节点将节点类型设置为“初始节点”,清空与分区树相关的所有参数;“树节点释放消息”格式如图10所示;(4) If the child node detects that the adjacency relationship of the parent node does not exist, then set its own type as "initial node", and notify all its descendant nodes through the "tree node release message" to set the node type as "initial node ", clear all parameters related to the partition tree; the format of "tree node release message" is shown in Figure 10;
(5)类型设置为“初始节点”的节点开始重新加入分区树。(5) The node whose type is set to "initial node" starts to rejoin the partition tree.
基于分区树的路由选择过程,其具体步骤包括:The specific steps of the routing selection process based on the partition tree include:
(1)每个根节点通过根节点之间的互连过程获得了到达其他根节点的路由信息;(1) Each root node obtains routing information to other root nodes through the interconnection process between root nodes;
(2)在分区树的生成过程中,父节点通过“树节点更新消息”中的节点路由列表获得了自己所有子孙节点的路由信息,根节点知道所在分区树的所有节点的路由信息;(2) During the generation of the partition tree, the parent node obtains the routing information of all its descendant nodes through the node routing list in the "tree node update message", and the root node knows the routing information of all nodes in the partition tree;
(3)如果数据分组的目的节点是自己的子孙节点,则直接发送至该节点;(3) If the destination node of the data packet is its descendant node, then send it directly to the node;
(4)如果数据分组的目的节点不是自己的子孙节点,则将分组发送给自己的父节点;(4) If the destination node of the data packet is not one's own descendant node, then the grouping is sent to one's own parent node;
(5)如果数据分组是由互连节点发出,且查询不到路由信息时,则将分组发给最近的根节点;(5) If the data packet is sent by the interconnection node, and the routing information cannot be queried, then the packet is sent to the nearest root node;
(6)如果根节点查询不到数据分组目的节点的路由信息,将向其他根节点发送路由查询消息,消息的内容包括消息类型、目的根节点ID、源根节点ID、数据分组目的节点ID;(6) If the root node queries the routing information of the data packet destination node, it will send a routing query message to other root nodes, and the content of the message includes message type, destination root node ID, source root node ID, data packet destination node ID;
(7)知道数据分组目的节点路由信息的根节点或互连节点向源根节点回复路由应答消息,消息内容包括消息类型、目的根节点ID、源根节点ID、数据分组目的节点ID;(7) The root node or interconnection node that knows the routing information of the data packet destination node replies to the source root node with a routing response message, and the message content includes message type, destination root node ID, source root node ID, data packet destination node ID;
(8)收到路由应答消息后,根节点将数据分组发给知道最优路由的根节点或互连节点;(8) After receiving the routing response message, the root node sends the data packet to the root node or interconnection node that knows the optimal route;
(9)根节点或互连节点接收到数据分组后,根据已有路由将分组发送至目的节点。(9) After receiving the data packet, the root node or the interconnection node sends the packet to the destination node according to the existing route.
基于分区树的路由选择过程的流程如图11所示。The flow of the routing selection process based on the partition tree is shown in FIG. 11 .
以上六个过程组成了基于分区树的多跳无线自组织网络的构建方法,该方法适用于各种规模的多跳无线自组织网络。The above six processes constitute a method for constructing a multi-hop wireless ad hoc network based on a partition tree, and the method is applicable to multi-hop wireless ad hoc networks of various scales.
本发明所提供的一种基于分区树的多跳无线自组织网络构建方法,具有如下优点:A method for constructing a multi-hop wireless ad hoc network based on a partition tree provided by the present invention has the following advantages:
(1)采用了分层的网络结构,根节点和互连节点组成了网络的骨干部分,一颗分区树就构成了一个分区,且树节点的移动只会产生局部的调整,因此具有分布式特点,适合于大规模无线自组织网络,可扩展性好。(1) A layered network structure is adopted. The root node and interconnection nodes form the backbone of the network. A partition tree constitutes a partition, and the movement of tree nodes will only produce local adjustments, so it has a distributed Features, suitable for large-scale wireless self-organizing network, good scalability.
(2)通过设置相应的策略来确定根节点的选择和分区树的生成,可以灵活控制骨干部分和分区树的规模,从而有效控制网络的整体布署和网络的传输效率。(2) By setting corresponding strategies to determine the selection of the root node and the generation of the partition tree, the size of the backbone part and the partition tree can be flexibly controlled, thereby effectively controlling the overall deployment of the network and the transmission efficiency of the network.
(3)骨干部分和分区树都具有自适应的维护过程,能保证网络中数据的传输效率和可靠性。(3) Both the backbone part and the partition tree have an adaptive maintenance process, which can ensure the transmission efficiency and reliability of data in the network.
(4)节点不需要维护到达其他所有节点的路由信息,其中根节点只需要维护到达其他根节点的路由信息和自己子孙节点的路由信息,互连节点只需要维护经过它的互连路由信息,树节点只需要维护自己的子孙节点的路由信息,这样降低了系统信息对节点资源的消耗,减少了系统信息的转发次数,由此降低了网络系统的开销。(4) The node does not need to maintain the routing information to all other nodes. The root node only needs to maintain the routing information to other root nodes and the routing information of its own descendant nodes. The interconnection node only needs to maintain the interconnection routing information passing through it. The tree node only needs to maintain the routing information of its own descendant nodes, which reduces the consumption of system information on node resources, reduces the number of forwarding times of system information, and thus reduces the overhead of the network system.
(5)路由实现是路由算法与树形拓扑结构相结合,其中根节点之间的互连采用路由算法,而分区树内的数据传输不需要采用路由算法,因为分区树的生成就已具备寻路的功能,因此降低了无线组网和路由算法的难度,提高了网络的可靠性和稳定性。(5) The implementation of routing is the combination of routing algorithm and tree topology, in which the interconnection between the root nodes adopts routing algorithm, and the data transmission in the partition tree does not need to use routing algorithm, because the generation of partition tree already has the ability to search Therefore, it reduces the difficulty of wireless networking and routing algorithms, and improves the reliability and stability of the network.
(6)路由选择具有先应式路由和按需路由的特点,路由选择开销小。分区树中的父节点都掌握了自己子孙节点的路由信息,因此分区树内部的路由信息就形成了先应式路由;分区树之间也有部分先应式路由,那就是根节点之间已有的互连路由;只有当根节点也不知道目的节点的路由时,才会发起路由查询的过程,这就是按需路由,但是这个过程并不需要建立新的路由,只需要在已有的互连路由中选择一条即可,与建立新的路由相比,路由过程时延小。(6) Routing has the characteristics of proactive routing and on-demand routing, and the routing cost is small. The parent nodes in the partition tree have mastered the routing information of their own descendant nodes, so the routing information inside the partition tree forms a proactive route; there are also some proactive routes between partition trees, that is, there are existing routes between the root nodes. only when the root node does not know the route of the destination node, the process of route query will be initiated, which is on-demand routing, but this process does not need to establish a new route, only needs to be established in the existing interconnection Just choose one of the connected routes. Compared with establishing a new route, the routing delay is small.
综上所述,本发明所提供的一种基于分区树的多跳无线自组织网络构建方法,与传统的无线组网技术相比,是一种扩展性好、网络结构规模可控、网络系统开销小、路由效率高的新型多跳无线自组织网络构建方式,从而有效提高网络的传输效率和网络性能。To sum up, the multi-hop wireless ad hoc network construction method based on the partition tree provided by the present invention is a network system with good scalability, controllable network structure scale, and A new multi-hop wireless self-organizing network construction method with low overhead and high routing efficiency, thereby effectively improving network transmission efficiency and network performance.
附图说明 Description of drawings
图1多跳无线通信示意图,其中节点之间的连线表示两个节点之间存在无线链路,可以直接通信。Figure 1 is a schematic diagram of multi-hop wireless communication, in which the connection between nodes indicates that there is a wireless link between two nodes, which can communicate directly.
图2本发明所提供方法的组成示意图。Fig. 2 is a schematic composition diagram of the method provided by the present invention.
图3根节点自动发现请求消息RADRQ的格式。Figure 3 shows the format of the root node auto-discovery request message RADRQ.
图4根节点自动发现应答消息RADRP的格式。Figure 4 shows the format of the RADRP response message for automatic discovery of the root node.
图5分区中心节点(根节点)确定过程流程图。Fig. 5 is a flow chart of the determination process of the partition center node (root node).
图6根节点之间互连过程流程图。Figure 6 is a flowchart of the interconnection process between root nodes.
图7“分区树建立消息”格式。Figure 7 "Partition tree establishment message" format.
图8“树节点更新消息”格式。Figure 8 "Tree Node Update Message" format.
图9分区树生成过程流程图。Figure 9 is a flow chart of the partition tree generation process.
图10“树节点释放消息”格式。Figure 10 "Tree Node Release Message" format.
图11基于分区树的路由选择过程流程图。Fig. 11 is a flowchart of routing selection process based on partition tree.
图12实施例初始网络图,其中节点之间的连线表示两个节点之间存在无线链路,可以直接通信。Figure 12 is the initial network diagram of the embodiment, where the connection lines between the nodes indicate that there is a wireless link between the two nodes, and they can communicate directly.
图13实施例中根节点确定后的网络示意图。Figure 13 is a schematic diagram of the network after the root node is determined in the embodiment.
图14实施例中根节点之间互连后的网络示意图。Fig. 14 is a schematic diagram of a network after root nodes are interconnected in the embodiment.
图15实施例中根节点之间互连路由的维护示意图。FIG. 15 is a schematic diagram of maintenance of interconnection routes between root nodes in the embodiment.
图16实施例中分区树生成过程的网络示意图。Figure 16 is a schematic network diagram of the partition tree generation process in the embodiment.
图17实施例中分区树生成过程完成后的网络示意图。Fig. 17 is a schematic diagram of the network after the partition tree generation process in the embodiment is completed.
图18实施例中分区树动态维护过程的网络示意图。FIG. 18 is a schematic network diagram of the dynamic maintenance process of the partition tree in the embodiment.
图19实施例中网络节点重新加入分区树的网络示意图。FIG. 19 is a schematic network diagram of a network node rejoining a partition tree in the embodiment.
图20实施例中节点S发送数据分组给节点12的路由示意图。In the embodiment of FIG. 20, a schematic diagram of a route for node S to send a data packet to
具体实施方式 Detailed ways
本发明所提供的一种基于分区树的多跳无线自组织网络构建方法,涉及到如下一些概念:A method for constructing a multi-hop wireless ad hoc network based on a partition tree provided by the present invention involves the following concepts:
初始节点:初始网络中的所有节点,它们之间处于一种平等的地位。Initial node: All nodes in the initial network are in an equal position.
分区、分区树:根据本发明方法所生成的一颗树形成一个相对独立的区域,每一个这样区域称为一个“分区”,所生成的树即称为“分区树”。Partition, partition tree: A tree generated according to the method of the present invention forms a relatively independent area, each such area is called a "partition", and the generated tree is called a "partition tree".
根节点:即分区树的根节点,是一个分区的中心节点。Root node: the root node of the partition tree, which is the central node of a partition.
互连节点:根节点之间互连路由所包含的节点,特殊情况下,互连节点可以升级成为根节点。Interconnection node: The node included in the interconnection route between the root nodes. Under special circumstances, the interconnection node can be upgraded to become the root node.
树节点:分区树中除根节点之外的其他所有节点。Tree node: All nodes in the partition tree except the root node.
深度:分区树中树节点到根节点的跳数。根节点的深度为0,初始节点的深度为空。Depth: The number of hops from a tree node to the root node in a partitioned tree. The depth of the root node is 0, and the depth of the initial node is empty.
父节点:分区树中一个树节点的上一级节点。Parent node: The parent node of a tree node in the partition tree.
子节点:分区树中一个树节点或根节点的下一级节点。Child node: A tree node or the next-level node of the root node in the partition tree.
子孙节点:分区树中一个树节点或根节点的所有下级节点。Descendant nodes: a tree node or all subordinate nodes of the root node in the partition tree.
下面结合附图和实施例对本发明作进一步地说明:Below in conjunction with accompanying drawing and embodiment the present invention will be further described:
实施例1Example 1
初始网络如图12所示,总共22个节点,它们都为初始节点,具有网络唯一标识符(ID或地址),处于对等的地位,节点之间有连线表示两个节点之间存在无线链路,可以直接通信。The initial network is shown in Figure 12. There are a total of 22 nodes, all of which are initial nodes, have network unique identifiers (ID or addresses), and are in a peer-to-peer position. A connection between nodes indicates that there is a wireless connection between two nodes. Link, can communicate directly.
一、确定各分区中心节点(根节点)1. Determine the central node (root node) of each partition
首先,给定一个选择根节点的条件,这个实施例中假设邻居节点数大于等于4的节点即可成为根节点。然后有两种方式来确定根节点,一种方式是通过手工方式采用静态配置的方法将满足条件的初始节点配置为“根节点”;另一种方式通过根节点自动发现方式,从网络中任选一个源节点(如图12中的节点S),向全网广播根节点自动发现请求消息RADRQ,所有节点都对收到的RADRQ消息进行转发,并记录收到该消息的邻居ID,满足根节点选择条件的节点配置自己的节点类型为“根节点”,并向源节点S回复应答消息RADRP,通知自己已经成为根节点,RADRP沿RADRQ的反向路由到达源节点S,通过接收到的全部RADRP消息,S可以获取全网根节点的信息。First, a condition for selecting a root node is given. In this embodiment, it is assumed that a node whose number of neighbor nodes is greater than or equal to 4 can become a root node. Then there are two ways to determine the root node. One way is to manually configure the initial node that meets the conditions as the "root node" through static configuration; the other way is to automatically discover the root node from any network. Select a source node (like node S in Figure 12), broadcast the root node automatic discovery request message RADRQ to the whole network, all nodes forward the received RADRQ message, and record the neighbor ID that received the message, satisfying the requirement of root node The node with the node selection condition configures its own node type as "root node", and replies the response message RADRP to the source node S, notifying itself that it has become the root node. RADRP reaches the source node S along the reverse route of RADRQ, and passes all received RADRP message, S can obtain the information of the root node of the whole network.
图12中有三个节点满足成为根节点的条件,并被配置为“根节点”,如图13所示的节点1、2、3。节点1、2、3将广播自己的节点信息,内容包括节点ID和节点类型。三个根节点都将记录收到的其他两个根节点的信息。In Figure 12, there are three nodes that meet the conditions to become root nodes and are configured as "root nodes", such as
二、根节点之间的互连2. Interconnection between root nodes
根节点1、2、3获取了其他根节点的信息后,就可以开始它们之间的互连过程。本实施例假设由ID Number小的根节点(源节点)向ID Number大的根节点(目的节点)广播发送路由请求消息RREQ,即1向2、3发送,2向3发送,这样可以避免重复的路由查询。After the
收到RREQ的中间节点根据RREQ中的信息,建立到源节点的路由。如果中间节点有最新的到达目的根节点的路由,则通过应答消息RREP回复该RREQ,否则继续广播该RREQ消息。The intermediate node that receives the RREQ establishes a route to the source node according to the information in the RREQ. If the intermediate node has the latest route to the destination root node, it will reply the RREQ through the response message RREP, otherwise it will continue to broadcast the RREQ message.
目的根节点2或3收到RREQ后,比较收到的所有RREQ消息,选取一条最优的路由(假设本实施例的最优的条件是跳数最少,如果跳数相等,则选取负荷低的节点),并沿最优路由的反向路由向源根节点回复应答消息RREP。如图14所示,节点1和2是邻居,所以2选取到1的路由是直连路由;1和3之间的最优路由是1→4→3;2和3之间的路由有两条跳数均为3,它们是2→1→4→3和2→5→6→3,但由于1为根节点,且有一条路由已经过节点4,所以选择2→5→6→3。收到RREP的中间节点4、5、6建立到目的根节点的路由,并设置自己的节点类型为“互连节点”。收到RREP的源根节点1或2建立到目的根节点的路由。After
三、根节点之间互连路由的维护3. Maintenance of interconnection routes between root nodes
根节点与互连节点都周期性地向相邻的互连节点或根节点发送“Hello消息”来确保路由的有效性,如果根节点或互连节点检测到下一跳不可达,就向利用该损坏链路的活跃上游互连节点或根节点发送RERR消息。如图15所示,当节点5检测到节点6发生故障变得不可达,将向上游节点2发送RERR消息,并设置自己的节点类型为“初始节点”。Both the root node and the interconnection node periodically send a "Hello message" to the adjacent interconnection node or root node to ensure the validity of the route. If the root node or interconnection node detects that the next hop is unreachable, it sends the The active upstream interconnect node or root node of the damaged link sends a RERR message. As shown in Figure 15, when
根节点2在收到该RERR消息后,确定到节点3的路由已经失效,则发起新的路由查询过程,建立新的互连路由2→1→4→3。After receiving the RERR message,
四、分区树的生成Fourth, the generation of partition tree
首先,根节点1、2、3设置自己的深度为0,初始节点、互连节点的深度为空;然后,根节点1、2、3开始周期性地广播“分区树建立消息”。以图16中节点1所在分区树的建立为例,收到“分区树建立消息”的初始节点7、8设置自己的类型为“树节点”、自己的深度设置为1、父节点设置为节点1,并向父节点1回复“树节点更新消息”。节点7、8成为树节点后也开始广播“分区树建立消息”,收到该消息的节点9将设置自己的类型为“树节点”、自己的深度设置为2、父节点设置为节点7,并向父节点7回复“树节点更新消息”;收到“分区树建立消息”的节点S、10将设置自己的类型为“树节点”、自己的深度设置为2、父节点设置为节点8,并向父节点8回复“树节点更新消息”。First, the
父节点收到“树节点更新消息”后,更新自己的子孙节点数、节点路由列表,并继续向自己的父节点发送“树节点更新消息”,直到根节点。这样节点1所在的分区树建立完成,根节点2、3所在的分区树将也按相同的过程予以建立。After the parent node receives the "tree node update message", it updates its own descendant node number and node routing list, and continues to send the "tree node update message" to its parent node until the root node. In this way, the partition tree where
如果初始节点如S收到节点8和9发送“分区树建立消息”,将根据给定的选择规则(本实施例的规则为选择深度较小的节点作为父节点)选取节点8的消息予以回复,丢弃节点9的“分区树建立消息”。If the initial node such as S receives the "partition tree establishment message" sent by
如果时间T(T>0)后还有初始节点如图16中的节点11由于只与互连节点和初始节点相连而无法加入分区树,这时与初始节点11相邻的互连节点5升级为根节点,并从最近的根节点2获取其他根节点的路由信息,并通知其他根节点1、3自己已升级成为根节点。如果这时需要了解全网的根节点信息,只需重新发起根节点自动发现过程即可。If there is still an initial node after time T (T>0) as shown in
升级成为根节点的节点5将广播“分区树建立消息”,这样节点11、12就可以加入到根节点5所在的分区树。直到所有的初始节点都加入到分区树中成为树节点后,分区树生成过程结束,如图17所示。The
五、分区树的动态维护5. Dynamic maintenance of partition tree
子节点通过父节点周期性发送的“分区树建立消息”来识别父节点是否仍然存在;父节点通过与子节点之间的信息交换来识别子节点是否仍然存在,如果在规定的时间内子节点没有信息需要发给父节点,则子节点主动发送一个“Hello消息”来维持它们之间的父子邻接关系。The child node identifies whether the parent node still exists through the "partition tree establishment message" sent periodically by the parent node; the parent node identifies whether the child node still exists through information exchange with the child node, and if the child node does not The information needs to be sent to the parent node, and the child node actively sends a "Hello message" to maintain the parent-child adjacency relationship between them.
如果父节点检测到某个子节点的邻接关系已不存在,则将该子节点从邻接关系表中删除,更新自己的子孙节点数、节点路由列表,并通过“树节点更新消息”通告自己的父节点;如果子节点检测到父节点的邻接关系已经不存在,则设置自己的类型为“初始节点”,并通过“树节点释放消息”通告自己所有的子孙节点将节点类型设置为“初始节点”,清空与分区树相关的所有参数。类型设置为“初始节点”的节点开始重新加入分区树。If the parent node detects that the adjacency relationship of a certain child node no longer exists, it will delete the child node from the adjacency relationship table, update the number of its own descendant nodes and node routing list, and notify its parent through the "tree node update message" node; if the child node detects that the adjacency relationship of the parent node no longer exists, set its own type as "initial node", and notify all its descendant nodes through the "tree node release message" to set the node type as "initial node" , to clear all parameters related to the partition tree. Nodes with type set to "initial node" start rejoining the partition tree.
如图18中节点8由于发生故障无法发送任何消息,当父节点1检测到与8的邻居关系已不存在,就将子节点8从邻接关系表中删除,更新自己的子孙节点数、节点路由列表,由于1为根节点,所以不需要发送“树节点更新消息”通告自己的父节点。当子节点S和10检测到与父节点8的邻接关系已不存在,就设置自己的类型为“初始节点”,由于S和10没有子节点,所以不需要发送“树节点释放消息”通告自己的子孙节点。As shown in Figure 18,
类型设置为“初始节点”的节点S和10将分别以节点9和节点13为父节点重新加入分区树,如图19所示。Nodes S and 10 whose type is set to "initial node" will rejoin the partition tree with
六、基于分区树的路由选择6. Routing selection based on partition tree
如图17所示,本实施例的网络中有四个根节点1、2、3和5,它们两两之间具有互连路由,在建立的四颗分区树中,父节点知道自己所有子孙节点的路由信息,四个根节点就知道所在分区树的所有节点的路由信息。As shown in Figure 17, there are four
如果数据分组的目的节点是自己的子孙节点,则直接发送至该节点;如果数据分组的目的节点不是自己的子孙节点,则将分组发送给自己的父节点。如果数据分组是由互连节点发出,且查询不到路由信息时,则将分组发给最近的根节点。If the destination node of the data packet is its own descendant node, it will be directly sent to this node; if the destination node of the data packet is not its own descendant node, the packet will be sent to its own parent node. If the data packet is sent by the interconnection node, and the routing information cannot be queried, the packet is sent to the nearest root node.
如果根节点查询不到数据分组目的节点的路由信息,将向其他根节点发送路由查询消息,知道数据分组目的节点路由信息的根节点或互连节点向源根节点回复路由应答消息。收到路由应答消息后,根节点将数据分组发给知道最优路由的根节点或互连节点,根节点或互连节点接收到数据分组后,根据已有路由将分组发送至目的节点。If the root node cannot query the routing information of the data packet destination node, it will send a routing query message to other root nodes, and the root node or interconnection node that knows the routing information of the data packet destination node will reply to the source root node with a routing response message. After receiving the routing response message, the root node sends the data packet to the root node or interconnection node that knows the optimal route. After receiving the data packet, the root node or interconnection node sends the packet to the destination node according to the existing route.
假设图17中节点S有数据分组需要发送给节点12,由于S没有子节点,S将数据分组发给父节点8,节点8查到目的节点12不属于自己的子孙节点,就将数据分组发给根节点1,在节点1具备的路由信息中也查不到到达节点12的路由,于是,节点1向另外3个根节点2、3、5发送路由查询消息,根节点5知道节点12的路由信息,将向根节点1回复路由应答消息,告知节点1自己知道到达节点12的路由信息。根节点1收到根节点5的路由应答消息后,就将数据分组发送给根节点5,根节点5收到数据分组后,将其转发给子节点11,由于节点12是节点11的子节点,节点11直接将数据分组发送给节点12,如图20所示。Assuming that node S in Figure 17 has a data packet that needs to be sent to
以上实施例说明的就是本发明所提供的一种基于分区树的多跳无线自组织网络构建方法的具体实施方式。本发明所提供的组网技术具有路由效率高、可扩展性好、网络开销小等优点,从而能有效提高网络的传输效率和网络性能。The above embodiments illustrate the specific implementation of a partition tree-based multi-hop wireless ad hoc network construction method provided by the present invention. The networking technology provided by the invention has the advantages of high routing efficiency, good scalability, small network overhead, etc., thereby effectively improving network transmission efficiency and network performance.
Claims (8)
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN200710031834A CN100591029C (en) | 2007-11-30 | 2007-11-30 | A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN200710031834A CN100591029C (en) | 2007-11-30 | 2007-11-30 | A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree |
Publications (2)
Publication Number | Publication Date |
---|---|
CN101197748A CN101197748A (en) | 2008-06-11 |
CN100591029C true CN100591029C (en) | 2010-02-17 |
Family
ID=39547909
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN200710031834A Expired - Fee Related CN100591029C (en) | 2007-11-30 | 2007-11-30 | A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree |
Country Status (1)
Country | Link |
---|---|
CN (1) | CN100591029C (en) |
Families Citing this family (35)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
TWI396410B (en) | 2008-12-29 | 2013-05-11 | Ind Tech Res Inst | Wireless communication network and routing method |
CN101784093B (en) * | 2009-01-15 | 2012-12-05 | 财团法人工业技术研究院 | Wireless communication network and routing method |
CN101635882B (en) * | 2009-07-30 | 2011-09-14 | 广州海格通信集团股份有限公司 | Method for realizing all network voice broadcast in multi-hop Ad Hoc radio station network |
CN101808338B (en) * | 2010-03-01 | 2012-12-12 | 东南大学 | Quality overhead ratio hop cluster-based service discovery method and mobility model establishing method |
CN101854693A (en) * | 2010-05-21 | 2010-10-06 | 南京邮电大学 | A Calculation Method of Routing Stability Applied in Mobile Ad Hoc Networks |
CN102098729B (en) * | 2010-10-21 | 2014-03-26 | 无锡泛联软件科技有限公司 | Construction method and related packet forwarding method for tree backbone structure in wireless network |
CN102098173A (en) * | 2010-12-23 | 2011-06-15 | 山东省计算中心 | Household appliances wireless control method and system |
CN102413542B (en) * | 2011-11-25 | 2014-08-20 | 广州杰赛科技股份有限公司 | Wireless mesh network routing method and wireless mesh network |
CN102572958B (en) * | 2011-12-20 | 2014-12-10 | 中国船舶重工集团公司第七0九研究所 | Resource organization system and resource query method applicable to wireless mobile grid |
CN102761883B (en) * | 2011-12-30 | 2015-04-15 | 慕福奇 | Multi-hop broadband wireless communication system and wireless node device thereof |
CN102625484A (en) * | 2012-03-31 | 2012-08-01 | 佛山市艾科电子工程有限公司 | Wireless ad hoc network system for data acquisition in building |
CN102665227B (en) * | 2012-04-12 | 2015-03-11 | 江苏运赢物联网产业发展有限公司 | Gateway-based relaying method based on wireless network |
CN103249106A (en) * | 2012-08-13 | 2013-08-14 | 四川九洲电器集团有限责任公司 | Method for improving communication quality of wireless network |
CN105282777A (en) * | 2014-07-14 | 2016-01-27 | 中兴通讯股份有限公司 | Mobile ad hoc network, center node dynamic selection method and center node |
CN104394576A (en) * | 2014-10-10 | 2015-03-04 | 珠海中慧微电子有限公司 | Method for discovering neighbor and accessing network by dissociated node in wireless electricity meter management system |
CN105743789B (en) * | 2014-12-08 | 2019-01-08 | 中国科学院声学研究所 | A kind of tree structured network autonomous management and node Adding Way |
CN105682212A (en) * | 2016-04-01 | 2016-06-15 | 中国联合网络通信集团有限公司 | Ad hoc network information transfer method and ad hoc network |
CN105848240B (en) * | 2016-05-16 | 2019-05-21 | 努比亚技术有限公司 | A kind of route device and method |
CN107454653B (en) * | 2016-05-31 | 2021-06-15 | 陕西尚品信息科技有限公司 | Network sharing system and network sharing method |
CN106102019A (en) * | 2016-06-02 | 2016-11-09 | 山东有人信息技术有限公司 | A kind of data transmission method based on WIFI broadcast packet and data transmission system |
WO2017214819A1 (en) * | 2016-06-13 | 2017-12-21 | 深圳天珑无线科技有限公司 | Distributed network message returning method, node and system |
WO2017214812A1 (en) * | 2016-06-13 | 2017-12-21 | 深圳天珑无线科技有限公司 | Distributed network message transmission method and node |
CN107948339B (en) * | 2016-10-12 | 2021-06-15 | 斑马智行网络(香港)有限公司 | A network addressing method, device and device |
CN106535139B (en) * | 2016-11-15 | 2019-06-21 | 国网黑龙江省电力有限公司信息通信公司 | Method of wireless communication for outage maintenance |
CN108574970B (en) * | 2017-03-07 | 2020-09-04 | 华为技术有限公司 | Father node selection method, network node and system |
KR20200014194A (en) * | 2018-07-31 | 2020-02-10 | 아서스테크 컴퓨터 인코포레이션 | Method and apparatus of updating routing table of an iab (integrated access backhaul) node in a wireless communication system |
CN109246790B (en) * | 2018-10-15 | 2019-08-09 | 西北工业大学 | A topology discovery method for underwater wireless multi-hop networks |
CN110365584B (en) * | 2019-08-06 | 2022-03-01 | 北京润科通用技术有限公司 | Network management method and device |
CN112751890B (en) * | 2019-10-29 | 2023-05-05 | 贵州白山云科技股份有限公司 | Data transmission control method and device |
CN111083758A (en) * | 2019-12-18 | 2020-04-28 | 华南理工大学 | A high-efficiency sound-electricity cooperative transmission network routing system and method |
CN111182557B (en) * | 2020-02-25 | 2023-07-07 | 广州致远电子股份有限公司 | Detection networking system, method and storage medium based on tree network |
CN113708946B (en) * | 2020-05-20 | 2024-01-05 | 平头哥(杭州)半导体有限公司 | Computing system and message routing method |
CN113747473B (en) * | 2021-09-01 | 2025-01-28 | 苏州佩林软件技术有限公司 | A self-organizing network method and self-organizing network system |
CN115333608B (en) * | 2022-08-15 | 2024-06-25 | 重庆两江卫星移动通信有限公司 | Satellite Internet of things terminal ground networking method and system |
CN115767565B (en) * | 2022-10-17 | 2024-08-02 | 北京交通大学 | Multi-level network construction method based on hierarchical networking and hierarchical resource scheduling method |
-
2007
- 2007-11-30 CN CN200710031834A patent/CN100591029C/en not_active Expired - Fee Related
Non-Patent Citations (1)
Title |
---|
无线自组织网络中的组播路由算法. 赵素芬.硕士学位论文. 2005 * |
Also Published As
Publication number | Publication date |
---|---|
CN101197748A (en) | 2008-06-11 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
CN100591029C (en) | A Multi-hop Wireless Ad Hoc Network Construction Method Based on Partition Tree | |
CN100442786C (en) | Routing Method Based on Tree Structure | |
Villasenor-Gonzalez et al. | HOLSR: a hierarchical proactive routing mechanism for mobile ad hoc networks | |
Niu et al. | Hybrid cluster routing: An efficient routing protocol for mobile ad hoc networks | |
CN111556550A (en) | Routing method for unmanned aerial vehicle network communication | |
CN101262449B (en) | A New Dual-frequency Hierarchical Routing Method for Ad Hoc Networks | |
Bhangwar et al. | On routing protocols for high performance | |
Saini et al. | Mobile ad-hoc network routing protocols: Comparative study | |
Qabajeh et al. | A survey on scalable multicasting in mobile ad hoc networks | |
Lee et al. | Issues in scalable clustered network architecture for mobile ad hoc networks | |
Kumbharey et al. | Renovated Cluster Based Routing Protocol for MANET | |
CN115551047A (en) | Wireless communication network and communication method thereof | |
Hamatta et al. | Comparative review for routing protocols in mobile ad-hoc networks | |
Imani et al. | DSDV-Het: a new scalable routing protocol for large heterogeneous ad hoc networks | |
Shahzamal | Lightweight mobile ad-hoc network routing protocols for smartphones | |
Sruthy et al. | Variants of AODV routing protocol: A review | |
Paul et al. | Self-adjusting transmission range control of mobile hosts in ad hoc wireless networks for stable communication | |
Ali et al. | A state-of-the-art of routing protocols for mobile ad-hoc networks (MANET) | |
Srivastava et al. | A performance analysis of routing protocols in mobile ad-hoc networks | |
Srijeevitha et al. | An Efficient Data Transmission using Relay Node Based Opportunistic Routing | |
Adebanjo et al. | An evaluation of improved cluster-based routing protocol in ad-hoc wireless network | |
Rao et al. | An elliptical routing protocol for wireless mesh networks: Performance analysis | |
Aakanksha et al. | A self-organizing self-healing on-demand loop-free path routing protocol using mobile process groups for mobile ad-hoc networks | |
Patel et al. | A survey of energy efficient routing protocols for mobile ad-hoc networks | |
Wang et al. | An adaptive forwarding cluster routing protocol for large scale wireless mobile ad hoc networks |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
C06 | Publication | ||
PB01 | Publication | ||
C10 | Entry into substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
C14 | Grant of patent or utility model | ||
GR01 | Patent grant | ||
C17 | Cessation of patent right | ||
CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20100217 Termination date: 20131130 |