技术领域technical field
本发明涉及无线Mesh网络(WMN：Wireless Mesh Network)，尤其涉及一种无线Mesh网络的跨层路由优化的方法及装置。The present invention relates to a wireless Mesh network (WMN: Wireless Mesh Network), in particular to a method and device for cross-layer routing optimization of a wireless Mesh network.
背景技术Background technique
由于更低的成本、灵活的配置以及增强的网络覆盖和网络容量，使得无线Mesh网络(WMN：Wireless Mesh Network)技术应用越来越广泛，其优异的性能受到学术界和产业界的青睐，已经成为下一代无线网络中涌现出来的一种非常具有应用前景的新型无线组网技术。无线Mesh网络主要由Mesh终端和Mesh路由器组成。其中，各个Mesh路由器构成了无线网络的网络架构基础和骨干网络，并与有线网络进行互联组网，一起为Mesh终端提供多跳无线互联网络连接。Due to lower cost, flexible configuration, and enhanced network coverage and network capacity, Wireless Mesh Network (WMN: Wireless Mesh Network) technology has become more and more widely used, and its excellent performance has been favored by academia and industry. It has become a very promising new wireless networking technology emerging in the next generation wireless network. A wireless Mesh network is mainly composed of Mesh terminals and Mesh routers. Among them, each Mesh router constitutes the network architecture foundation and backbone network of the wireless network, and interconnects with the wired network to provide a multi-hop wireless Internet connection for the Mesh terminal.
传统的网络使用分层的协议模型，不同协议层之间彼此透明。协议开发和实现是一个简单而又可升级的过程。但是，由于无线网络的复杂性，分层协议设计的方法并不一定非常适合无线网络。例如，无线环境下的物理信道是变化的，容量和误比特率等都是不断变化的。采用优化的调制编码方案和差错控制方案可以改进物理信道的性能，但还是不能像更高层所期望的一样保证稳定的容量、低丢包率与可靠的连接性。因此，在无线网络中，高层协议必然会受到物理信道不稳定的影响。为了更进一步提高无线网络的性能，MAC(媒体接入控制，Media Access Control)、路由及传输协议必须要和物理层一起工作。此外，MAC、路由和传输协议也需要互相合作，这些交互需要在不同层协议之间的跨层设计。通过利用物理层、MAC层、路由层等协议层之间的联合设计是无线多媒体业务QoS(服务质量，Quality of Service)要求的一种行之有效的方法。Traditional networks use a layered protocol model, and different protocol layers are transparent to each other. Protocol development and implementation is a simple and scalable process. However, due to the complexity of wireless networks, the method of layered protocol design is not necessarily very suitable for wireless networks. For example, the physical channel in the wireless environment is changing, and the capacity and bit error rate are constantly changing. Using optimized modulation and coding schemes and error control schemes can improve the performance of the physical channel, but it still cannot guarantee stable capacity, low packet loss rate, and reliable connectivity as expected by higher layers. Therefore, in wireless networks, high-level protocols are bound to be affected by physical channel instability. In order to further improve the performance of the wireless network, MAC (Media Access Control, Media Access Control), routing and transmission protocols must work together with the physical layer. In addition, MAC, routing, and transport protocols also need to cooperate with each other, and these interactions require cross-layer design between different layer protocols. A joint design among protocol layers such as the physical layer, the MAC layer, and the routing layer is an effective method for the QoS (Quality of Service) requirement of wireless multimedia services.
现有技术中，OLSR(最优链路状态路由，Optimized Link State Routing)路由协议是一种基于多点中继的表驱动路由协议。每个节点使用一个或多个路由表来维护全网拓扑，并通过周期性地广播拓扑信息来保持路由表信息与网络拓扑变化之间的一致性，节点在发送数据分组时只要到达目的节点的路由存在，就能够立即得到到达目的节点的路由信息，因此具有时延小的特点。OLSR协议的优化技术是采用了多点中继MPR(Multipoint Relay)提供一种选择性洪泛机制，减少同一区域内的相同路由控制分组的重复转发次数来降低网络中广播分组的数量。只有被选做多点中继MPR的节点才会产生链路状态信息以及转发其他节点发送的信息，减少了网络中控制消息的数量，降低了控制分组的广播所带来的重复转发开销。In the prior art, the OLSR (Optimized Link State Routing, Optimized Link State Routing) routing protocol is a table-driven routing protocol based on multipoint relay. Each node uses one or more routing tables to maintain the topology of the entire network, and maintains the consistency between routing table information and network topology changes by periodically broadcasting topology information. When a node sends a data packet, it only needs to reach the destination node If the route exists, the route information to the destination node can be obtained immediately, so it has the characteristics of small delay. The optimization technology of the OLSR protocol is to use multipoint relay MPR (Multipoint Relay) to provide a selective flooding mechanism to reduce the number of repeated forwarding of the same route control packet in the same area to reduce the number of broadcast packets in the network. Only the nodes selected as MPR will generate link state information and forward information sent by other nodes, which reduces the number of control messages in the network and reduces the repeated forwarding overhead caused by the broadcast of control packets.
OLSR路由协议的问题在于，在多点中继MPR选择和路由计算的过程中，仅依靠节点覆盖度作为MPR节点的选取原则、没有考虑到节点的随机移动性引起路径中存在链路不稳定性等因素以及未考虑节点的处理负荷，网络拥塞状态以及无线链路的带宽、时延等性能参数导致MPR集的节点选择不准确，造成网络拥塞，影响网络性能。The problem with the OLSR routing protocol is that in the process of multi-point relay MPR selection and route calculation, it only relies on node coverage as the selection principle of MPR nodes, and does not take into account the random mobility of nodes, which causes link instability in the path. Factors such as node processing load, network congestion status, and performance parameters such as wireless link bandwidth and delay lead to inaccurate selection of nodes in the MPR set, resulting in network congestion and affecting network performance.
现有技术中，Performance-DSR(P-DSR)跨层路由协议是根据链路状态和节点发送缓存的状态信息对DSR(动态源路由协议，Dynamic Source Routing)进行了优化和改进而提出。P-DSR协议通过RPV(路由性能值，RoutePerformance Value)路由机制来考虑节点间无线链路状态对路由性能的影响，即链路的中断概率，同时又考虑了节点本身状态对路由性能的影响，即节点发送缓存溢出的概率，以此构建路由性能值RPV作为路由选择的标准，避免业务过于集中造成网络性能的下降。In the prior art, the Performance-DSR (P-DSR) cross-layer routing protocol is proposed by optimizing and improving DSR (Dynamic Source Routing) according to the state information of the link state and node transmission cache. The P-DSR protocol uses the RPV (Route Performance Value, RoutePerformance Value) routing mechanism to consider the influence of the wireless link state between nodes on the routing performance, that is, the link interruption probability, and at the same time consider the influence of the node's own state on the routing performance. That is, the probability of a node sending buffer overflow, based on which the routing performance value RPV is constructed as a routing selection standard to avoid network performance degradation caused by excessive business concentration.
P-DSR路由协议适应节点高速运动的场景，而在节点低速移动的网络中，由于中断概率和发送缓存不能很好的反映路径的实时状态以及网络的拥塞状况，未对信道的状态进行区分对待，导致路由更新不准确，性能较差。The P-DSR routing protocol adapts to the scenario where nodes move at high speed, but in a network where nodes move at a low speed, because the outage probability and sending buffer cannot reflect the real-time state of the path and the congestion of the network well, the state of the channel is not treated differently. , resulting in inaccurate routing updates and poor performance.
发明内容Contents of the invention
本发明所要解决的技术问题在于，提供一种无线Mesh网络的跨层路由优化的方法及装置，解决目前跨层路由时存在的因无法获得更准确的网络状态而造成的路由更新不准确及路由性能较差的问题。The technical problem to be solved by the present invention is to provide a method and device for cross-layer routing optimization of a wireless Mesh network, which solves the problem of inaccurate routing update and routing error caused by the inability to obtain more accurate network status in cross-layer routing. Problem with poor performance.
为了解决上述问题，本发明提出了一种基于信道状态的跨层路由优化的方法，包括：In order to solve the above problems, the present invention proposes a method for cross-layer routing optimization based on channel state, including:
步骤1：根据无线链路的传输效率参数估计当前网络的信道状态，在判断信道状态为传输性能差时，根据分组成功率、剩余负载率判断出当前丢包的原因，根据所述丢包原因调整最大重传次数；Step 1: Estimate the channel state of the current network according to the transmission efficiency parameters of the wireless link. When it is judged that the channel state is poor in transmission performance, the cause of the current packet loss is determined according to the packet composition power and the remaining load rate. According to the cause of the packet loss Adjust the maximum number of retransmissions;
步骤2：根据无线链路的传输效率参数获得整条路径的传输效率PTEP，获取除去源节点和目的节点后的路径的剩余负载率L_P，计算路径有效带宽ηB(c)，利用路径的传输效率PTEP，路径的剩余负载率L_P，路径有效带宽ηB(c)，构建路由决策函数，利用所述路由决策函数执行路由发现、路由维护操作，选择出源节点和目的节点之间的最佳分组传输路径。Step 2: Obtain the transmission efficiency PTEP of the entire path according to the transmission efficiency parameters of the wireless link, obtain the remaining load rate L_P of the path after removing the source node and the destination node, calculate the path effective bandwidth ηB (c), use the path The transmission efficiency PTEP of the path, the remaining load rate L_P of the path, and the effective bandwidth of the path ηB (c), construct a routing decision function, use the routing decision function to perform routing discovery and routing maintenance operations, and select the source node and the destination node The best packet transmission path between.
所述根据无线链路的传输效率参数估计当前网络的信道状态的步骤中：In the step of estimating the channel state of the current network according to the transmission efficiency parameters of the wireless link:
所述无线链路的传输效率参数是广播路由表的周期T内，从节点a到节点b的数据帧的传输成功效率利用指数加权移动平均算法(EWMA)进行平滑处理后的参数；当所述无线链路的传输效率参数小于第一阈值Threshold1时，判定信道状态为传输性能差。The transmission efficiency parameter of the wireless link is within the period T of the broadcast routing table, and the transmission success efficiency of the data frame from node a to node b is smoothed by an exponentially weighted moving average algorithm (EWMA); when the When the transmission efficiency parameter of the wireless link is less than the first threshold Threshold1 , it is determined that the channel state is poor transmission performance.
所述根据分组成功率、剩余负载率判断出当前丢包的原因的步骤中：In the step of judging the cause of the current packet loss according to the grouping power and the remaining load rate:
所述剩余负载率是广播路由表的周期T内，路径源节点的剩余负载率L_resa利用指数加权移动平均算法(EWMA)进行平滑处理后的剩余负载率The residual load rate is the residual load rate L_resa of the source node of the path in the period T of the broadcast routing table after being smoothed by an exponentially weighted moving average algorithm (EWMA)
利用路径分组成功率PSRa，b和剩余负载率构建用于区分无线信道状态类型的代价函数为：Use path grouping to form power PSRa, b and residual load rate The cost function constructed to distinguish the types of wireless channel states is:
0≤β≤1； 0≤β≤1;
当代价函数COST的统计值小于第二阈值Threshold2时，可判定当前丢包的原因为较严重的分组冲突造成的碰撞丢包；When the statistical value of the cost function COST is less than the second threshold Threshold2 , it can be determined that the cause of the current packet loss is the collision packet loss caused by a more serious packet collision;
当代价函数COST的统计值大于第二阈值Threshold2时，可判定当前丢包的原因为无线链路较高的随机差错率；When the statistical value of the cost function COST is greater than the second threshold Threshold2 , it can be determined that the cause of the current packet loss is the high random error rate of the wireless link;
其中β为加权因子，0＜Threshold2＜1。Where β is a weighting factor, 0<Threshold2 <1.
所述根据所述丢包原因调整最大重传次数的步骤中：In the step of adjusting the maximum number of retransmissions according to the packet loss cause:
所述丢包的原因为较严重的分组冲突造成的碰撞丢包时，降低最大重传次数Cmax；所述丢包的原因为无线链路较高的随机差错率时，增加最大重传次数Cmax。When the packet loss is due to collision and packet loss caused by more serious packet collisions, reduce the maximum number of retransmissions Cmax ; when the packet loss is due to a high random error rate of the wireless link, increase the maximum number of retransmissions Cmax .
所述最大重传次数Cmax的调整范围为[0，Cth]，所述调整范围的上限Cth是由传输效率参数、分组成功率和剩余负载率共同计算确定。The adjustment range of the maximum number of retransmissions Cmax is [0, Cth ], and the upper limit Cth of the adjustment range is jointly calculated and determined by transmission efficiency parameters, packet composition power and residual load rate.
所述根据无线链路的传输效率参数获得整条路径的传输效率PTEP的步骤中，所述PTEP表示为：In the step of obtaining the transmission efficiency PTEP of the entire path according to the transmission efficiency parameter of the wireless link, the PTEP is expressed as:
所述无线链路的传输效率参数是广播路由表的周期T内，从节点a到节点b的数据帧的传输成功效率利用指数加权移动平均算法(EWMA)进行平滑处理后的参数，为多跳连接路径中的其中一条从节点a到节点b的链路。The transmission efficiency parameter of the wireless link Is the parameter after smoothing the transmission success efficiency of the data frame from node a to node b in the period T of the broadcast routing table using the exponentially weighted moving average algorithm (EWMA), is one of the links from node a to node b in the multi-hop connection path.
所述路径的剩余负载率L_P表示为：The remaining load rateL_P of the path is expressed as:
所述表示路径源节点的剩余负载率L_resa利用指数加权移动平均算法(EWMA)进行平滑处理后的剩余负载率。said Indicates the remaining load rate L_resa of the source node of the path after smoothing with the Exponential Weighted Moving Average Algorithm (EWMA).
所述路由决策函数的构建定义如下：The construction definition of the routing decision function is as follows:
Frouting(ηB(c)，PTEp，L_p)＝w1×ηB(c)+w2×PTEp+w3×L_pFrouting (ηB (c), PTEp , L_p ) = w1 ×ηB (c)+w2 ×PTEp +w3 ×L_p
其中，w1、w2、w3均为加权因子，L_P表示路径的剩余负载率，ηB(c)为归一化有效带宽，即数据流有效带宽占总带宽的比例，PTEP为路径的传输效率。Among them, w1 , w2 , and w3 are weighting factors, L_P represents the remaining load rate of the path, ηB (c) is the normalized effective bandwidth, that is, the ratio of the effective bandwidth of the data flow to the total bandwidth, and PTEP is The transmission efficiency of the path.
所述利用所述路由决策函数执行路由发现、路由维护操作，选择出源节点和目的节点之间的分组传输路径的步骤中，目的节点对所有找到的路径参数应用灰色关联分析法进行优化，选择所述路由决策函数值最大的一条路径进行数据的传送。In the step of using the routing decision function to perform routing discovery and routing maintenance operations, and selecting a packet transmission path between the source node and the destination node, the destination node optimizes all found path parameters using the gray correlation analysis method, and selects A path with the largest value of the routing decision function is used for data transmission.
本发明还提供一种无线Mesh网络的跨层路由优化的装置，包括：The present invention also provides a device for cross-layer routing optimization of a wireless Mesh network, including:
用于计算传输效率参数的传输效率检测模块，用于计算分组成功率的分组成功率检测模块，用于计算节点剩余负载率的剩余负载率检测模块；A transmission efficiency detection module for calculating the transmission efficiency parameter, a packet composition power detection module for calculating the packet composition power, and a residual load rate detection module for calculating the node residual load rate;
信道状态估计模块，用于根据所述传输效率参数估计当前网络的信道状态，用于根据所述分组成功率、剩余负载率构建用于判断信道状态的代价函数，并在判断信道状态差时根据所述代价函数对信道状态进行估计，判断出丢包原因；The channel state estimation module is used for estimating the channel state of the current network according to the transmission efficiency parameter, for constructing a cost function for judging the channel state according to the packet composition power and the remaining load rate, and when judging that the channel state is poor according to The cost function estimates the channel state and determines the cause of packet loss;
最大重传次数调整模块，用于根据所述丢包原因调整增大或降低最大重传次数；The maximum number of retransmissions adjustment module is used to increase or decrease the maximum number of retransmissions according to the cause of packet loss;
路径剩余负载率检测模块，用于根据剩余负载率检测模块检测的节点剩余负载率获取除去源节点和目的节点后的路径的剩余负载率；The path residual load rate detection module is used to obtain the residual load rate of the path after removing the source node and the destination node according to the node residual load rate detected by the residual load rate detection module;
路径传输效率检测模块，用于根据所述传输效率检测模块获得的传输效率参数计算得到路径传输效率；A path transmission efficiency detection module, configured to calculate the path transmission efficiency according to the transmission efficiency parameters obtained by the transmission efficiency detection module;
路径有效带宽估计模块，用于基于概率统计的方法估计出路径的有效带宽；The path effective bandwidth estimation module is used to estimate the effective bandwidth of the path based on the method of probability statistics;
路由决策模块，用于根据路径的传输效率，路径的剩余负载率，路径有效带宽，构建路由决策函数，利用所述路由决策函数执行路由发现、路由维护过程，选择源节点和目的节点之间的分组传输路径。The routing decision module is used to construct a routing decision function according to the transmission efficiency of the path, the remaining load rate of the path, and the effective bandwidth of the path, and use the routing decision function to perform routing discovery and routing maintenance processes to select the route between the source node and the destination node. Packet transmission path.
所述路由决策模块所述路由决策函数的构建定义如下：The construction definition of the routing decision function of the routing decision module is as follows:
Frouting(ηB(c)，PTEp，L_p)＝w1×ηB(c)+w2×PTEp+w3×L_pFrouting (ηB (c), PTEp , L_p ) = w1 ×ηB (c)+w2 ×PTEp +w3 ×L_p
其中，w1、w2、w3均为加权因子，L_P表示路径的剩余负载率，ηB(c)为归一化有效带宽，即数据流有效带宽占总带宽的比例，PTEP为路径的传输效率。Among them, w1 , w2 , and w3 are weighting factors, L_P represents the remaining load rate of the path, ηB (c) is the normalized effective bandwidth, that is, the ratio of the effective bandwidth of the data flow to the total bandwidth, and PTEP is The transmission efficiency of the path.
所述信道状态估计模块根据分组成功率、剩余负载率判断出当前丢包的原因时：When the channel state estimation module judges the cause of the current packet loss according to the grouping power and the remaining load rate:
所述剩余负载率是广播路由表的周期T内，路径源节点的剩余负载率L_resa利用指数加权移动平均算法(EWMA)进行平滑处理后的剩余负载率The residual load rate is the residual load rate L_resa of the source node of the path in the period T of the broadcast routing table after being smoothed by an exponentially weighted moving average algorithm (EWMA)
所述信道状态估计模块利用路径分组成功率PSRa，b和剩余负载率构建的用于区分无线信道状态类型的代价函数为：The channel state estimation module uses the path grouping power PSRa, b and the remaining load rate The constructed cost function for differentiating wireless channel state types is:
0≤β≤1； 0≤β≤1;
当代价函数COST的统计值小于第二阈值Threshold2时，可判定当前丢包的原因为较严重的分组冲突造成的碰撞丢包；When the statistical value of the cost function COST is less than the second threshold Threshold2 , it can be determined that the cause of the current packet loss is the collision packet loss caused by a more serious packet collision;
当代价函数COST的统计值大于第二阈值Threshold2时，可判定当前丢包的原因为无线链路较高的随机差错率；When the statistical value of the cost function COST is greater than the second threshold Threshold2 , it can be determined that the cause of the current packet loss is the high random error rate of the wireless link;
其中β为加权因子，0＜Threshold2＜1。Where β is a weighting factor, 0<Threshold2 <1.
本发明的无线Mesh网络的跨层路由优化的方法及装置，通过动态测量无线链路的环境信息，对造成分组丢失的原因进行区分，动态调整MAC层的最大重传次数，优化MAC层的重传控制方案，降低链路失效概率，提高分组的成功传递率和网络吞吐量。针对WMN中路由判据单一或测量不准确导致路由性能较差的缺陷，在MAC层进行丢包区分的基础上，提出一种启发式的多目标跨层路由优化机制HEAOR。通过跨层设计技术，更加准确地感知MAC层的路径质量、链路可用带宽等状态信息，减少路由误判次数，降低路由维护开销给网络带来的消极影响，有效地提高网络平均吞吐率，满足无线多媒体业务的QoS要求。The method and device for cross-layer routing optimization of the wireless Mesh network of the present invention, by dynamically measuring the environmental information of the wireless link, distinguishing the cause of packet loss, dynamically adjusting the maximum number of retransmissions of the MAC layer, and optimizing the retransmission of the MAC layer The transmission control scheme reduces the probability of link failure and improves the successful delivery rate of packets and network throughput. Aiming at the defect of poor routing performance caused by single routing criterion or inaccurate measurement in WMN, a heuristic multi-objective cross-layer routing optimization mechanism HEAOR is proposed based on packet loss discrimination at the MAC layer. Through the cross-layer design technology, it can more accurately perceive the state information such as the path quality of the MAC layer and the available link bandwidth, reduce the number of routing misjudgments, reduce the negative impact of routing maintenance costs on the network, and effectively improve the average throughput of the network. Meet the QoS requirements of wireless multimedia services.
附图说明Description of drawings
图1是无线Mesh网络中基于信道状态的跨层路由优化的方法的总体流程图；Fig. 1 is the overall flowchart of the method for cross-layer routing optimization based on channel state in wireless Mesh network;
图2是本发明实施例中调整信道状态以及进行跨层路由优化的具体步骤示意图；FIG. 2 is a schematic diagram of specific steps for adjusting channel status and performing cross-layer routing optimization in an embodiment of the present invention;
图3是本发明实施例中用于进行跨层路由优化的装置的模块示意图。Fig. 3 is a block diagram of a device for performing cross-layer routing optimization in an embodiment of the present invention.
具体实施方式Detailed ways
为使本发明的目的、技术方案和优点更加清楚，以下结合附图对本发明作进一步地详细说明。In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings.
为了克服现有跨层技术中路由维护频繁、资源利用率较低的缺点，解决现有技术中存在的未对信道状态进行区分的问题。本发明的无线Mesh网络的基于信道状态的跨层路由优化的方法，包括MAC层的重传控制优化和网络层的跨层路由优化，尤其是基于IEEE 802.11的无线网络重传控制和联合路由优化。In order to overcome the shortcomings of frequent route maintenance and low resource utilization in the existing cross-layer technology, and solve the problem of not distinguishing channel states in the prior art. The channel state-based cross-layer routing optimization method of the wireless Mesh network of the present invention includes MAC layer retransmission control optimization and network layer cross-layer routing optimization, especially wireless network retransmission control and joint routing optimization based on IEEE 802.11 .
通过动态环境感知，对MAC层中因冲突或差错而导致发送失败的数据包进行自适应重传，通过对信道状态的判断，有效感知最佳重传次数，减少冲突概率，提高系统吞吐量。Through dynamic environment perception, adaptive retransmission is performed on data packets that fail to be sent due to conflicts or errors in the MAC layer. By judging the channel state, it can effectively perceive the optimal number of retransmissions, reduce the probability of collisions, and improve system throughput.
路由层通过启发式方法动态估计MAC层及物理层的链路状态信息对路由性能的影响，提出了一种启发式的基于环境感知的QoS(Quality of Service)路由优化选择算法HEAOR(Heuristic Environment-Aware Optimal Routing)。该HEAOR算法在基本不增加路由开销的基础上，能够更加准确地预测链路状态，更加有效的选择路由。The routing layer uses a heuristic method to dynamically estimate the impact of link state information on the MAC layer and the physical layer on routing performance, and proposes a heuristic environment-aware QoS (Quality of Service) routing optimization algorithm HEAOR (Heuristic Environment- Aware Optimal Routing). The HEAOR algorithm can predict the link state more accurately and select the route more effectively on the basis of basically not increasing the routing overhead.
如图1所示，一种基于信道状态的跨层路由优化的方法，包括：As shown in Figure 1, a method for cross-layer routing optimization based on channel state includes:
步骤1：根据无线链路的传输效率参数估计当前网络的信道状态，在判断信道状态为传输性能差时，根据分组成功率、剩余负载率判断出当前丢包的原因，根据所述丢包原因调整最大重传次数；Step 1: Estimate the channel state of the current network according to the transmission efficiency parameters of the wireless link. When it is judged that the channel state is poor in transmission performance, the cause of the current packet loss is determined according to the packet composition power and the remaining load rate. According to the cause of the packet loss Adjust the maximum number of retransmissions;
步骤2：根据无线链路的传输效率参数获得整条路径的传输效率PTEP，获取除去源节点和目的节点后的路径的剩余负载率L_P，计算路径有效带宽ηB(c)，利用路径的传输效率PTEP，路径的剩余负载率L_P，路径有效带宽ηB(c)，构建路由决策函数，利用所述路由决策函数执行路由发现、路由维护，选择源节点和目的节点之间的分组传输路径。Step 2: Obtain the transmission efficiency PTEP of the entire path according to the transmission efficiency parameters of the wireless link, obtain the remaining load rate L_P of the path after removing the source node and the destination node, calculate the path effective bandwidth ηB (c), use the path The transmission efficiency PTEP of the path, the remaining load rate L_P of the path, and the effective bandwidth of the path ηB (c), construct a routing decision function, use the routing decision function to perform routing discovery, routing maintenance, and select the route between the source node and the destination node Packet transmission path.
本发明是基于信道状态的自适应进行跨层优化路径选择，其关键点包括两个：第一，MAC层基于环境感知进行最大重传次数自适应调整；第二，路由层基于信道状态进行路由优化选择。下面针对上述两个关键点进行详细说明。The present invention is based on channel state self-adaption for cross-layer optimization path selection, and its key points include two: first, the MAC layer performs adaptive adjustment of the maximum number of retransmissions based on environmental perception; second, the routing layer performs routing based on channel state Optimize selection. The following two key points will be described in detail below.
由于信道状态会严重影响路由选择，因而，首先通过对MAC层的期望传输次数、分组成功率、剩余负载率等环境参数的统计分析，分辨出当前丢包的主要原因是包碰撞还是无线链路随机差错所致，针对不同的丢包原因自适应调整最大重传次数，合理控制MAC重传。Since the channel state will seriously affect the routing selection, first, through the statistical analysis of environmental parameters such as the expected transmission times, packet composition power, and residual load rate of the MAC layer, it is possible to distinguish whether the main cause of the current packet loss is packet collision or wireless link. Due to random errors, the maximum number of retransmissions is adaptively adjusted according to different reasons for packet loss, and MAC retransmissions are reasonably controlled.
在无线Mesh网络中，MAC层采用IEEE 802.11 DCF进行信道接入，基于RTS/CTS的4次握手模式及竞争退避机制实现数据传送。发送节点在发送数据帧前先发送请求发送子帧RTS，接收节点在收到RTS后，通过等待SIFS时间间隔后用控制帧CTS对RTS进行确认回复；发送节点收到确认的CTS后发送数据包，接收节点收到数据包之后，利用ACK进行确认。In the wireless Mesh network, the MAC layer uses IEEE 802.11 DCF for channel access, and realizes data transmission based on the 4-way handshake mode of RTS/CTS and the contention avoidance mechanism. The sending node sends a request to send subframe RTS before sending the data frame. After receiving the RTS, the receiving node confirms the RTS with the control frame CTS after waiting for the SIFS time interval; the sending node sends the data packet after receiving the confirmed CTS , after the receiving node receives the data packet, it confirms with ACK.
当产生分组丢失时，利用指数退避机制进行MAC重传，包重传次数被固定的设定为4(数据包)或7(RTS包)。若报文经过多次重传尝试(达到最大重传次数)仍无法将报文成功发送到下一跳，则丢弃该报文，同时准备发送下一个分组。由于此种重传机制未对链路的丢包原因进行区分，而实际链路的最佳重传次数往往与丢包原因密切相关，从而导致现有接入机制的不公平性，造成不必要的过度重传使网络性能急剧下降。When a packet loss occurs, the MAC retransmission is performed using an exponential backoff mechanism, and the number of packet retransmissions is fixedly set to 4 (data packets) or 7 (RTS packets). If the message cannot be successfully sent to the next hop after multiple retransmission attempts (up to the maximum number of retransmissions), the message is discarded and the next packet is prepared to be sent. Since this retransmission mechanism does not distinguish the cause of packet loss on the link, and the optimal number of retransmissions on the actual link is often closely related to the cause of packet loss, this leads to the unfairness of the existing access mechanism and unnecessary Excessive retransmissions degrade network performance dramatically.
根据分析可知，目前导致分组丢失的原因主要有两种：A.无线链路的随机差错；B.网络拥塞/碰撞丢包所致。现有的基于802.11的MAC层协议的各种算法并未对造成分组丢失的真正原因进行判断，导致路由层的负担加重，资源利用率较低。According to the analysis, there are two main reasons for packet loss: A. Random errors in wireless links; B. Network congestion/collision and packet loss. Various algorithms of the existing 802.11-based MAC layer protocol do not judge the real cause of packet loss, resulting in increased burden on the routing layer and low resource utilization.
首先需要判断当前网络状态，即通过无线链路的传输效率参数判断网络状态获知传输性能好还是传输性能差，在传输性能较差时再进一步判断其原因，针对不同原因自适应调整重传。First of all, it is necessary to judge the current network status, that is, judge the network status through the transmission efficiency parameters of the wireless link to know whether the transmission performance is good or poor. When the transmission performance is poor, the reason is further judged, and the retransmission is adaptively adjusted for different reasons.
定义MAC层的最大重传次数为Cmax。由于时延是有限的，当重传次数达到Cmax时数据包仍不能正确接收，则丢弃。网络中每个节点使用IEEE 802.11MAC_MIB中的变量ACK_count_Failure和RTS_count_Failure分别表示DATA帧和RTS帧的实际重传次数。假设从节点a到节点b成功发送第i个分组的重传次数为Cab(i)，Cab(i)实际上是DATA和RTS的重传次数的和(Cab(i)＝ACK_count_Failure(i)+RTS_count_Failure(i))。The maximum number of retransmissions at the MAC layer is defined as Cmax . Since the delay is limited, when the number of retransmissions reaches Cmax , the data packet still cannot be received correctly, and it is discarded. Each node in the network uses the variables ACK_count_Failure and RTS_count_Failure in the IEEE 802.11MAC_MIB to represent the actual retransmission times of the DATA frame and the RTS frame, respectively. Assuming that the number of retransmissions of the i-th packet successfully sent from node a to node b is Cab (i), Cab (i) is actually the sum of the retransmission times of DATA and RTS (Cab (i)=ACK_count_Failure( i)+RTS_count_Failure(i)).
在理想情况下，即成功传输一个分组，RTS和DATA应该各仅有一次传输。这样，从节点a到节点b的数据帧的传输成功效率FTEab(i)可按照公式(1)计算：In an ideal situation, that is, a packet is successfully transmitted, RTS and DATA should only be transmitted once each. Like this, the transmission success efficiency FTEab (i) of the data frame from node a to node b can be calculated according to formula (1):
该传输效率参数FTEab(i)表示成功发送RTS和DATA帧的概率，当重传次数越大时，FTE的值将越小；当没有发生帧丢失时，重传次数为0，FTEab为1，即从节点a发送到节点b的分组被100％成功发送。The transmission efficiency parameter FTEab (i) represents the probability of successfully sending RTS and DATA frames. When the number of retransmissions is larger, the value of FTE will be smaller; when no frame loss occurs, the number of retransmissions is 0, and FTEab is 1, that is, packets sent from node a to node b are sent 100% successfully.
为了避免无线链路瞬态特性给网络带来的突发抖动影响，在广播路由表的周期T内，节点a对链路的成功传输效率通过指数加权移动平均算法(EWMA)进行平滑处理。成功传输效率的EWMA计算的平均值如公式(2)所示。公式(2)中表示传输第i-1个分组时FTE的移动平均值，α1为加权因子，其值取决于信道变化的速度。In order to avoid the impact of sudden jitter caused by the transient characteristics of the wireless link to the network, in the period T of broadcasting the routing table, node a smoothes the successful transmission efficiency of the link through the exponentially weighted moving average algorithm (EWMA). The average value calculated by EWMA of successful transmission efficiency is shown in formula (2). In formula (2) Indicates the moving average of FTE when the i-1th packet is transmitted, α1 is a weighting factor, and its value depends on the speed of channel change.
0≤α1≤1(2) 0≤α1≤1(2)
在IEEE802.11中分布式协调函数DCF是最基本的媒体访问方法，即节点发送数据前先侦听信道的忙闲状态，如果信道空闲，说明当前信道不冲突，分组被传输；如果信道忙，说明当前信道冲突，被发送的分组等待一个DIFS的间隔。对于信道忙闲状态的判定本发明采用下述方法：In IEEE802.11, the distributed coordination function (DCF) is the most basic media access method, that is, the node listens to the busy status of the channel before sending data. If the channel is idle, it means that the current channel does not conflict and the packet is transmitted; if the channel is busy, Indicates that the current channel conflicts, and the sent packet waits for a DIFS interval. The present invention adopts following method for the judgment of channel busy state:
1)利用路径的分组成功率PSR(Packet Success Rate)来指示当前物理信道状态的忙闲，假设每条传输链路的分组错误率PER(a，b)(Packet Error Rate)相互独立，通过公式(3)计算路径的分组成功率PSR：1) Use the packet composition power PSR (Packet Success Rate) of the path to indicate the busyness of the current physical channel state, assuming that the packet error rate PER(a, b) (Packet Error Rate) of each transmission link is independent of each other, through the formula (3) Calculate the packet composition power PSR of the path:
其中PER(a，b)为从节点a到节点b的误包率，每一段传输区间的PER(a，b)相互独立。当解码端采用Viterbi解码，则链路的PER可以被近似估计出。Among them, PER(a, b) is the packet error rate from node a to node b, and the PER(a, b) of each transmission interval is independent of each other. When the decoding end adopts Viterbi decoding, the PER of the link can be estimated approximately.
2)判断信道状态的另一判据是节点a的剩余负载率，用L_resa来表示节点a的剩余负载率，反映网络的拥塞程度，如公式(4)所示定义L_resa为：2) Another criterion for judging the channel state is the residual load rate of node a. L_resa is used to represent the residual load rate of node a, which reflects the congestion degree of the network. As shown in formula (4), L_resa is defined as:
其中，Occupa表示数据缓存区中已占用的数据大小，Capa表示节点a固定的最大数据缓存容量。L_resa则可以看作节点a的数据缓存区中尚未被使用的缓存比例。Among them, Occupa represents the data size occupied in the data cache area, and Capa represents the fixed maximum data cache capacity of node a. L_resa can be regarded as the unused cache ratio in the data cache area of node a.
从公式(4)可看出L_resa越大，说明节点可利用的数据缓存区就越大，节点当前可接受的负载能力越强，相对来说，就认为这些节点较“空闲”，从公平使用网络资源角度讲，应该让这些节点尽可能参与网络业务的路由。为了减小误差影响，同样采用EWMA算法对节点的剩余负载率进行平滑，EWMA算法处理后的节点剩余负载率如公式(5)所示：It can be seen from formula (4) that the larger L_resa is, the larger the data buffer area available to the node, and the stronger the load capacity currently acceptable to the node. Relatively speaking, these nodes are considered to be "idle", and fair From the perspective of using network resources, these nodes should be allowed to participate in the routing of network services as much as possible. In order to reduce the impact of errors, the EWMA algorithm is also used to smooth the remaining load rate of the node. The remaining load rate of the node processed by the EWMA algorithm is shown in formula (5):
0≤α2≤1(5) 0≤α2 ≤1(5)
基于对分组成功率和剩余负载率的统计分析，进一步可构建一个可以区分无线信道状态类型的代价函数为：Based on the statistical analysis of packet composition power and residual load rate, a cost function that can distinguish wireless channel state types can be further constructed as:
0≤β≤1， 0≤β≤1,
其中β为加权因子。当代价函数COST的统计值较小(COST＜Threshold2，0＜Threshold2＜1)，表明分组发送的成功率较低，或者剩余负载率较小，则进一步可判定当前无线信道状态为忙，分组冲突较高，此时过度增加重传次数只能导致网络性能的恶化；反之，分组发送成功率较高，链路有更多的可用资源，则判定当前信道为空闲状态。Where β is the weighting factor. When the statistical value of the cost function COST is small (COST<Threshold2 , 0<Threshold2 <1), it indicates that the success rate of packet transmission is low, or the remaining load rate is small, then it can be further determined that the current wireless channel state is busy, Packet conflicts are high, and excessively increasing the number of retransmissions at this time can only lead to deterioration of network performance; on the contrary, the success rate of packet transmission is high, and the link has more available resources, then the current channel is judged to be idle.
基于上述参数，如图2所示，最大重传次数的自适应调整过程如下：Based on the above parameters, as shown in Figure 2, the adaptive adjustment process of the maximum number of retransmissions is as follows:
第一步，首先利用无线链路的传输效率参数FTE估计当前网络的整体状态，当经过指数加权移动平均平滑处理的成功传输效率较小(0＜Threshold1＜1)，说明当前链路ab的传输性能较差。The first step is to use the transmission efficiency parameter FTE of the wireless link to estimate the overall state of the current network, when the successful transmission efficiency after smoothing the exponentially weighted moving average smaller ( 0<Threshold1 <1), indicating that the transmission performance of the current link ab is poor.
导致链路ab的性能较差的原因主要包括：较严重的分组冲突或者无线链路较高的随机差错率。The reasons for the poor performance of the link ab mainly include: relatively serious packet collision or a high random error rate of the wireless link.
为了进一步区分这两种原因，通过构建的无线链路代价函数COST的值来区分导致分组丢失严重的真正原因。In order to further distinguish these two reasons, the real cause of severe packet loss is distinguished by the value of the constructed wireless link cost function COST.
当COST较小时，(COST＜Threshold2，0＜Threshold2＜1))，信道处于忙状态，即判定当前碰撞丢包占主要部分，分组冲突严重。此时，若增加重传只能浪费宝贵的信道资源，使拥塞或冲突更加严重；为了缓解网络的拥塞，MAC层应降低最大重传次数Cmax，同时为了避免网络的突发波动，进行自减一操作，即Cmax＝Cmax-1，路由层相应地调用路由维护策略。When the COST is small, (COST<Threshold2 , 0<Threshold2 <1)), the channel is in a busy state, that is, it is determined that the current collision and packet loss account for the main part, and the packet collision is serious. At this time, increasing retransmissions can only waste precious channel resources and make congestion or conflicts more serious; in order to alleviate network congestion, the MAC layer should reduce the maximum number of retransmissions Cmax Subtract one operation, that is, Cmax =Cmax -1, and the routing layer invokes the routing maintenance strategy accordingly.
当COST较大时(COST＞Threshold2)，在无线链路传输性能较差的情况下，可以推断当前链路随机差错率可能较高，无线信道有较严重误码，此时可通过增加MAC层的最大重传次数Cmax，例如进行自加一操作Cmax＝Cmax+1来提高信道抗误码的能力，路由层同时避免路由维护以免浪费信道带宽。When the COST is large (COST>Threshold2 ), in the case of poor wireless link transmission performance, it can be inferred that the random error rate of the current link may be high, and the wireless channel has serious bit errors. The maximum number of retransmissions Cmax of the layer, for example, the self-increment operation Cmax =Cmax +1 is performed to improve the channel's ability to resist bit errors, and the routing layer avoids route maintenance at the same time to avoid wasting channel bandwidth.
当经过指数加权移动平均平滑处理的成功传输效率较大时，说明无线信道有较高的传输效率，基本上可排除信道出现较严重的冲突或较高的误码率的情况，为了进一步提高网络的性能，应用层的H.264视频编码器可以适当提高发送速率，避免路由维护，增加网络吞吐量，提高无线资源的利用率。The successful transfer efficiency when smoothed by an exponentially weighted moving average bigger When , it shows that the wireless channel has a high transmission efficiency, which can basically eliminate the situation of serious collision or high bit error rate in the channel. In order to further improve the performance of the network, the H.264 video encoder at the application layer can be properly Increase the sending rate, avoid route maintenance, increase network throughput, and improve the utilization of wireless resources.
为了避免最大重传次数Cmax的无限制的增加或减小，提高重传调整的有效性，利用传输效率参数FTE、分组成功率PSR和剩余负载率L_res构建一个Cmax的调整极限值如公式(6)所示，上述重传次数的调整范围为[0，Cth]。In order to avoid the unlimited increase or decrease of the maximum number of retransmissions Cmax and improve the effectiveness of retransmission adjustment, a Cmax adjustment limit value is constructed by using the transmission efficiency parameter FTE, packet composition power PSR and residual load rate L_res as shown in the formula As shown in (6), the adjustment range of the above retransmission times is [0, Cth ].
基于信道状态的自适应综合判决策略的算法示例如表1所示。An algorithm example of an adaptive comprehensive decision strategy based on channel state is shown in Table 1.
表1：基于信道状态自适应调整重传的算法Table 1: Algorithm for adaptively adjusting retransmission based on channel state
第二步，利用路径的传输效率PTEP，路径的剩余负载率L_P，路径的有效带宽ηB(c)，构建路由决策函数，利用所述路由决策函数执行路由发现、路由维护，选择源节点和目的节点之间的路由路径。The second step is to use the transmission efficiency PTEP of the path, the remaining load rateL_P of the path, and the effective bandwidth ηB (c) of the path to construct a routing decision function, use the routing decision function to perform routing discovery, routing maintenance, and select the source The routing path between a node and a destination node.
根据IEEE802.11中的MAC层机制，用于建立连接的RTS、CTS以及数据帧的丢失或延迟，定时器超时，MAC层协议都将启动数据帧重发机制。本发明采用路径的平均传输效率PTE(PTE：Path Transmission Efficiency)反映每跳路径的质量和拥塞情况，并作为混合路由判决之一，根据公式(2)中链路期望传输效率的计算方法(其中α1＝0.3)，可进一步得到整条路径的传输效率如公式(7)所示，其中为多跳连接路径中的其中一条从节点a到节点b的链路。According to the MAC layer mechanism in IEEE802.11, the RTS and CTS used to establish a connection, as well as the loss or delay of data frames, and the timer overtime, the MAC layer protocol will start the data frame retransmission mechanism. The present invention adopts the average transmission efficiency PTE (PTE: Path Transmission Efficiency) of the path to reflect the quality and the congestion situation of each hop path, and as one of the mixed routing judgments, according to the calculation method of the expected transmission efficiency of the link in the formula (2) (wherein α1 =0.3), the transmission efficiency of the entire path can be further obtained as shown in formula (7), where is one of the links from node a to node b in the multi-hop connection path.
通过公式(4)和(5)对一个节点剩余负载率的定义，可以计算出一条路径的剩余负载率。路径的剩余负载率定义为这条路径上除去源节点和目的节点后，剩余节点的最小剩余负载率。路径的剩余负载率可以反映这条路径的负载能力。假设有一条从源节点s到目的节点d的路径，记为P，这条路径P的剩余负载率记为L_P，可表示为公式(8)所示。路径的剩余负载率越大说明这条路径越空闲，可接受的负载能力越强，数据分组从此路径转发数据的成功概率也就越大。Through formulas (4) and (5) to define the residual load rate of a node, the residual load rate of a path can be calculated. The residual load rate of a path is defined as the minimum residual load rate of the remaining nodes after removing the source node and the destination node on this path. The remaining load rate of a path can reflect the load capacity of this path. Suppose there is a path from the source node s to the destination node d, denoted as P, and the remaining load rate of this path P is denoted asL_P , which can be expressed as shown in formula (8). The greater the residual load rate of the path, the more idle the path is, the stronger the acceptable load capacity is, and the greater the success probability of data packet forwarding from this path is.
本发明采用基于分组延迟及概率违背的带宽预测方法对无线链路的有效带宽进行估计。该方法首先统计分组经历的总延迟，该延迟包括队列延迟和服务时间的延迟，通过利用最大背离理论，如公式(9)所示分组延迟D超过最大延迟范围Dmax的概率可近似为：The invention uses a bandwidth prediction method based on packet delay and probability violation to estimate the effective bandwidth of the wireless link. This method first counts the total delay experienced by the packet, which includes queue delay and service time delay. By using the maximum deviation theory, as shown in formula (9), the probability that the packet delay D exceeds the maximum delay range Dmax can be approximated as:
其中θB＝cηB-1(c)，而ηB(c)为数据流的有效带宽，c为信道的恒定服务率，在已知c的情况下可利用上述公式(9)近似计算信道的可用带宽，如公式(10)所示，可得到有效带宽为：where θB = cηB-1 (c), and ηB (c) is the effective bandwidth of the data stream, c is the constant service rate of the channel, and the above formula (9) can be used to approximate the calculation of the channel when c is known The available bandwidth of , as shown in formula (10), the available effective bandwidth is:
公式(10)在满足一定概率范围内保证分组的端到端延迟小于Dmax，且充分考虑了时延特性。利用这种统计特性可提高有效带宽估计的准确性。Formula (10) guarantees that the end-to-end delay of the packet is less than Dmax within a certain probability range, and fully considers the delay characteristics. Utilizing this statistical property can improve the accuracy of effective bandwidth estimation.
在判断路径好坏时，需要对各种路径质量信息进行综合考虑，如图2所示，本发明提出的HEAOR路径选择算法中，目的节点要对所有找到的路径应用灰色关联分析法进行优化，最后选择路由决策函数值最大的一条路径进行数据的传送。When judging whether the path is good or bad, it is necessary to comprehensively consider various path quality information, as shown in Figure 2, in the HEAOR path selection algorithm proposed by the present invention, the destination node will optimize all paths found by the gray correlation analysis method, Finally, a path with the largest routing decision function value is selected for data transmission.
本发明定义的路由决策函数如公式(11)所示：Routing decision function defined by the present invention is shown in formula (11):
Frouting(ηB(c)，PTEp，L_p)＝w1×ηB(c)+w2×PTEp+w3×L_p (11)Frouting (ηB (c), PTEp , L_p ) = w1 ×ηB (c)+w2 ×PTEp +w3 ×L_p (11)
其中，w1、w2、w3均为加权因子；ηB(c)为归一化有效带宽，即数据流有效带宽占总带宽的比例。Among them, w1 , w2 , and w3 are all weighting factors; ηB (c) is the normalized effective bandwidth, that is, the ratio of the effective bandwidth of the data stream to the total bandwidth.
为了获取各度量和属性之间的相关性，采用灰色关联分析法计算权值w1、w2、w3。首先利用当前及缓存的度量值构建评估矩阵A如公式(12)所示，通过求解判决矩阵A的最大特征根λmax，得到相应的特征向量w(w＝(w1，w2，w3)T)，如公式(13)所示，这样就可以得到需要的权值向量。In order to obtain the correlation between each measure and attribute, weights w1 , w2 , and w3 are calculated by gray relational analysis method. First, use the current and cached metric values to construct an evaluation matrix A as shown in formula (12), and obtain the correspondingeigenvector w (w=(w1 , w2 , w3 )T ), as shown in formula (13), so that the required weight vector can be obtained.
考虑到求解矩阵的复杂性，当信道出现连续丢包时才更新矩阵A，同时计算权值，这样不仅可以降低计算的复杂度，同时也保证了矩阵A的非相关性(保证特征根的存在)。Considering the complexity of solving the matrix, the matrix A is updated when there is continuous packet loss in the channel, and the weights are calculated at the same time, which not only reduces the complexity of the calculation, but also ensures the non-correlation of the matrix A (guarantees the existence of the characteristic root ).
其中 in
在确定路由决策函数后，可以应用该路由决策函数进行路由发现与路由维护。路由选择算法是一种基于按需的源路由选择算法，当某节点需要获得到达另一节点的路由时，该节点将作为源节点发起一路由发现过程。After the routing decision function is determined, the routing decision function can be used for route discovery and route maintenance. The routing algorithm is an on-demand source routing algorithm. When a node needs to obtain a route to another node, the node will initiate a route discovery process as a source node.
源节点首先发送路由请求信息(RREQ)，该请求包括路由请求的生命周期TTL(一般为跳数限制)、包序号与目的地址等信息。此外，路由请求的HEAOR包头还应含有路径质量的结构体，用于存放路径质量信息，路径质量的结构体如公式(14)所示，结构体中包括路径的传输效率PTEP，路径的剩余负载率L_P，路径有效带宽ηB(c)等参数。The source node first sends a routing request message (RREQ), which includes information such as the life cycle TTL of the routing request (generally a hop limit), packet sequence number, and destination address. In addition, the HEAOR header of the routing request should also contain a path quality structure, which is used to store path quality information. The path quality structure is shown in formula (14). The structure includes the path transmission efficiency PTEP , and the path remaining Load rate L_P , path effective bandwidth ηB (c) and other parameters.
Path_Quality_StructPath_Quality_Struct
(14) (14)
{float ηB(c)；float PTEp；float L_p；}{ float ηB (c); float PTEp ; floatL_p ; }
中间节点收到该路由请求后，首先更新该路由请求所携带路径质量的结构体，然后判断本节点是否应该忽略该路由请求。判断的内容包括包序号、路径优劣、节点可用资源是否过载及TTL是否到期等。After receiving the routing request, the intermediate node first updates the structure of the path quality carried in the routing request, and then judges whether the node should ignore the routing request. The content of the judgment includes the packet sequence number, the quality of the path, whether the available resources of the node are overloaded, and whether the TTL has expired.
中间节点若从缓存中找到到达目的节点的路径，则根据式(11)提出的多判据路由决策函数来判断缓存路由是否比路由请求所携带的路径更好，若是，则返回该路径；否则，放弃缓存回复。If the intermediate node finds the path to the destination node from the cache, it judges whether the cached route is better than the path carried by the routing request according to the multi-criteria routing decision function proposed by formula (11), and returns the path if it is; otherwise , to discard cached replies.
目的节点收到路由请求后，首先更新路径质量的结构体，同时调用路由回复(RREP)过程将路由请求的路径和路径质量信息(最小剩余带宽、链路质量及网络负荷)发送给源节点。当目的节点连续收到多个路由请求时，若通过路由决策函数(式(11))验证当前路由请求所携带的路径质量比已转发的路径更优，节点将再次进行路由回复，否则丢弃该路由请求。After the destination node receives the routing request, it first updates the structure of the path quality, and at the same time calls the route reply (RREP) process to send the path and path quality information (minimum remaining bandwidth, link quality and network load) of the routing request to the source node. When the destination node receives multiple routing requests consecutively, if it is verified by the routing decision function (Formula (11)) that the path quality carried by the current routing request is better than the forwarded path, the node will reply the routing again, otherwise discard the Routing requests.
源节点通过路由回复数据包获得所需路径及路径质量等信息并将其添加到路由缓存中，同时查看数据缓存中是否有数据需要发送。在路由回复阶段，若其它节点接收到反馈消息，可以从消息中提取有用路径的相关信息并添加到自身的路由缓存中。The source node obtains information such as the required path and path quality through the routing reply data packet and adds it to the routing cache, and at the same time checks whether there is data to be sent in the data cache. In the routing reply phase, if other nodes receive the feedback message, they can extract information about the useful path from the message and add it to their own routing cache.
HEAOR路由算法采用了与DSR协议相同的路由维护机制，当路径中的链路失效时，链路上游节点发送路由错误分组(RERR)，进行路由维护。但与DSR不同的是节点对数据发送过程中最大路由错误数进行判断，若超过指定值，则丢弃该包，防止数据包被循环转发导致网络瘫痪。The HEAOR routing algorithm uses the same routing maintenance mechanism as the DSR protocol. When the link in the path fails, the upstream node of the link sends a routing error packet (RERR) for routing maintenance. However, the difference from DSR is that the node judges the maximum number of routing errors during the data transmission process. If it exceeds the specified value, the packet is discarded to prevent the network from being paralyzed by the circular forwarding of the data packet.
路由维护中通过路由缓存查找到达目的节点的路径，如果存在，则使用该路径发送数据包，若没有找到则重新发起路由请求消息(RREQ)，获得到达目的节点的路由；同时，节点查看IFQ队列中是否有使用该链路的数据包，判断是否要改变原有路径。In route maintenance, the path to the destination node is searched through the route cache. If it exists, the path is used to send the data packet. If not found, the route request message (RREQ) is re-initiated to obtain the route to the destination node; at the same time, the node checks the IFQ queue Whether there is a data packet using the link in the network, and judge whether to change the original path.
如图3所示，本发明还给出了一种无线Mesh网络的跨层路由优化的装置，包括：As shown in Figure 3, the present invention also provides a device for cross-layer routing optimization of a wireless Mesh network, including:
用于计算传输效率参数的传输效率检测模块，用于计算分组成功率的分组成功率检测模块，用于计算节点剩余负载率的剩余负载率检测模块；A transmission efficiency detection module for calculating the transmission efficiency parameter, a packet composition power detection module for calculating the packet composition power, and a residual load rate detection module for calculating the node residual load rate;
信道状态估计模块，用于根据所述传输效率参数估计当前网络的信道状态，根据所述分组成功率、剩余负载率构建用于判断信道状态的代价函数，并在判断信道状态差时根据所述代价函数对信道状态进行估计，判断出丢包原因；The channel state estimation module is used for estimating the channel state of the current network according to the transmission efficiency parameter, constructing a cost function for judging the channel state according to the packet composition power and the remaining load rate, and according to the The cost function estimates the channel state and determines the cause of packet loss;
最大重传次数调整模块，用于根据所述丢包原因自适应调整最大重传次数；A maximum number of retransmissions adjustment module, configured to adaptively adjust the maximum number of retransmissions according to the packet loss cause;
路径剩余负载率检测模块，用于根据剩余负载率检测模块检测的节点剩余负载率获取除去源节点和目的节点后的路径的剩余负载率；The path residual load rate detection module is used to obtain the residual load rate of the path after removing the source node and the destination node according to the node residual load rate detected by the residual load rate detection module;
路径传输效率检测模块，用于根据所述传输效率检测模块获得的传输效率参数计算得到路径传输效率；A path transmission efficiency detection module, configured to calculate the path transmission efficiency according to the transmission efficiency parameters obtained by the transmission efficiency detection module;
路径有效带宽估计模块，用于估计出路径的有效带宽；A path effective bandwidth estimation module is used to estimate the effective bandwidth of the path;
路由决策模块，用于根据路径的传输效率，路径的剩余负载率，路径有效带宽，构建路由决策函数，利用所述路由决策函数执行路由发现、路由维护选择源节点和目的节点之间的分组传输路径。The routing decision module is used to construct a routing decision function according to the transmission efficiency of the path, the remaining load rate of the path, and the effective bandwidth of the path, and use the routing decision function to perform route discovery and route maintenance to select the packet transmission between the source node and the destination node path.
其中，所述信道状态估计模块利用无线链路的传输效率参数FTE估计当前网络的整体状态，当经过指数加权移动平均平滑处理的成功传输效率较小(0＜Threshold1＜1)，说明当前链路ab的传输性能较差。Wherein, the channel state estimation module uses the transmission efficiency parameter FTE of the wireless link to estimate the overall state of the current network, when the successful transmission efficiency after smoothing the exponentially weighted moving average smaller ( 0<Threshold1 <1), indicating that the transmission performance of the current link ab is poor.
其中，所述信道状态估计模块基于对分组成功率和剩余负载率的统计分析，进一步可构建一个可以区分无线信道状态类型的代价函数为：Wherein, the channel state estimation module can further construct a cost function that can distinguish wireless channel state types based on statistical analysis of packet composition power and residual load rate as:
0≤β≤1，其中β为加权因子。 0≤β≤1, where β is the weighting factor.
当COST较小时，(COST＜Threshold2，0＜Threshold2＜1))，信道处于忙状态，即判定当前碰撞丢包占主要部分，分组冲突严重。此时，若增加重传只能浪费宝贵的信道资源，使拥塞或冲突更加严重；为了缓解网络的拥塞，MAC层应降低最大重传次数Cmax，同时为了避免网络的突发波动，进行自减一操作，即Cmax＝Cmax-1，路由层相应地调用路由维护策略。When the COST is small, (COST<Threshold2 , 0<Threshold2 <1)), the channel is in a busy state, that is, it is determined that the current collision and packet loss account for the main part, and the packet collision is serious. At this time, increasing retransmissions can only waste precious channel resources and make congestion or conflicts more serious; in order to alleviate network congestion, the MAC layer should reduce the maximum number of retransmissions Cmax Subtract one operation, that is, Cmax =Cmax -1, and the routing layer invokes the routing maintenance strategy accordingly.
当COST较大时(COST＞Threshold2)，在无线链路传输性能较差的情况下，可以推断当前链路随机差错率可能较高，无线信道有较严重误码，此时可通过增加MAC层的最大重传次数Cmax，例如进行自加一操作Cmax＝Cmax+1来提高信道抗误码的能力，路由层同时避免路由维护以免浪费信道带宽。When the COST is large (COST>Threshold2 ), in the case of poor wireless link transmission performance, it can be inferred that the random error rate of the current link may be high, and the wireless channel has serious bit errors. The maximum number of retransmissions Cmax of the layer, for example, the self-increment operation Cmax =Cmax +1 is performed to improve the channel's ability to resist bit errors, and the routing layer avoids route maintenance at the same time to avoid wasting channel bandwidth.
所述装置进一步还可包括：重传次数的极限值调整模块，用于确定最大重传次数的极限值。为了避免最大重传次数Cmax的无限制的增加或减小，提高重传调整的有效性，利用传输效率参数FTE、分组成功率PSR和剩余负载率L_res构建一个Cmax的调整极限值如公式(6)所示，上述重传次数的调整范围为[0，Cth]。The device may further include: a limit value adjustment module for the number of retransmissions, configured to determine a limit value for the maximum number of retransmissions. In order to avoid the unlimited increase or decrease of the maximum number of retransmissions Cmax and improve the effectiveness of retransmission adjustment, a Cmax adjustment limit value is constructed by using the transmission efficiency parameter FTE, packet composition power PSR and residual load rate L_res as shown in the formula As shown in (6), the adjustment range of the above retransmission times is [0, Cth ].
所述路由决策模块构建的路由决策函数如公式(11)所示：The routing decision function that described routing decision module builds is as shown in formula (11):
Frouting(ηB(c)，PTEp，L_p)＝w1×ηB(c)+w2×PTEp+w3×L_p (11)Frouting (ηB (c), PTEp , L_p ) = w1 ×ηB (c)+w2 ×PTEp +w3 ×L_p (11)
其中，w1、w2、w3均为加权因子；ηB(c)为归一化有效带宽，即数据流有效带宽占总带宽的比例。Among them, w1 , w2 , and w3 are all weighting factors; ηB (c) is the normalized effective bandwidth, that is, the ratio of the effective bandwidth of the data stream to the total bandwidth.
路由决策模块在利用路由决策函数进行路由优化时，会构建一个路径质量的结构体如公式(14)所示，结构体中包括路径的传输效率PTEP，路径的剩余负载率L_P，路径有效带宽ηB(c)等参数。When the routing decision-making module uses the routing decision-making function for routing optimization, it will construct a structure of path quality as shown in formula (14), which includes the transmission efficiency PTEP of the path, the remaining load rate of the path L_P , and the path effective Bandwidth ηB (c) and other parameters.
Path_Quality_StructPath_Quality_Struct
(14) (14)
{float ηB(c)；float PTEp；float L_p；}{ float ηB (c); float PTEp ; floatL_p ; }
在路径选择算法中，节点根据结构体获取所需参数，目的节点要对所有找到的路径应用灰色关联分析法进行优化，选择路由决策函数值最大的一条路径进行数据的传送，从而确定出源节点和目的节点之间的分组传输路径。In the path selection algorithm, the node obtains the required parameters according to the structure, and the destination node should apply the gray correlation analysis method to optimize all the found paths, and select a path with the largest routing decision function value for data transmission, so as to determine the source node The packet transmission path between the destination node and the destination node.
本发明的方法及装置，通过动态测量无线链路的环境信息，对造成分组丢失的原因进行区分，动态调整MAC层的最大重传次数，优化MAC层的重传控制方案，降低链路失效概率，提高分组的成功传递率和网络吞吐量。针对WMN中路由判据单一或测量不准确导致路由性能较差的缺陷，在MAC层进行丢包区分的基础上，提出一种启发式的多目标跨层路由优化机制HEAOR。通过跨层设计技术，更加准确地感知MAC层的路径质量、链路可用带宽等状态信息，减少路由误判次数，降低路由维护开销给网络带来的消极影响，有效地提高网络平均吞吐率，满足无线多媒体业务的QoS要求。The method and device of the present invention distinguish the cause of packet loss by dynamically measuring the environmental information of the wireless link, dynamically adjust the maximum retransmission times of the MAC layer, optimize the retransmission control scheme of the MAC layer, and reduce the link failure probability , to improve the successful delivery rate of packets and network throughput. Aiming at the defect of poor routing performance caused by single routing criterion or inaccurate measurement in WMN, a heuristic multi-objective cross-layer routing optimization mechanism HEAOR is proposed based on packet loss discrimination at the MAC layer. Through the cross-layer design technology, it can more accurately perceive the state information such as the path quality of the MAC layer and the available link bandwidth, reduce the number of routing misjudgments, reduce the negative impact of routing maintenance costs on the network, and effectively improve the average throughput of the network. Meet the QoS requirements of wireless multimedia services.
以上所述仅为本发明的实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的权利要求范围之内。The above description is only an embodiment of the present invention, and is not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the scope of the claims of the present invention.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201010277382.4ACN102387559B (en) | 2010-09-03 | 2010-09-03 | Cross-layer route optimization method and device for wireless Mesh network |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201010277382.4ACN102387559B (en) | 2010-09-03 | 2010-09-03 | Cross-layer route optimization method and device for wireless Mesh network |
| Publication Number | Publication Date |
|---|---|
| CN102387559A CN102387559A (en) | 2012-03-21 |
| CN102387559Btrue CN102387559B (en) | 2015-06-03 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201010277382.4AExpired - Fee RelatedCN102387559B (en) | 2010-09-03 | 2010-09-03 | Cross-layer route optimization method and device for wireless Mesh network |
| Country | Link |
|---|---|
| CN (1) | CN102387559B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103369599B (en)* | 2013-06-24 | 2016-07-06 | 天津理工大学 | A kind of many radio frequencies multi-Channel Wireless Mesh Network resource cross-layer optimizing method |
| CN103338471A (en)* | 2013-06-27 | 2013-10-02 | 南京邮电大学 | Service quality index evaluating method for wireless multi-hop network based on model |
| US9374151B2 (en) | 2013-08-08 | 2016-06-21 | Intel IP Corporation | Coverage extension level for coverage limited device |
| US9763210B2 (en)* | 2014-01-30 | 2017-09-12 | Intel Corporation | Evolved node-B and user equipment and methods for operation in a coverage enhancement mode |
| CN105578555A (en)* | 2014-10-16 | 2016-05-11 | 北京信威通信技术股份有限公司 | Routing method of wireless ad hoc network, node apparatus and system |
| CN104661260B (en)* | 2015-01-20 | 2018-07-20 | 中南大学 | A kind of Wireless Mesh intelligent grid method for routing of QoS perception and load balancing |
| WO2016172983A1 (en)* | 2015-04-30 | 2016-11-03 | 华为技术有限公司 | Path selection method, device and system |
| CN105281975B (en)* | 2015-09-10 | 2018-08-14 | 昆明理工大学 | A kind of service path selection quality judging method based on real-time response |
| CN106941397B (en)* | 2016-01-04 | 2020-04-24 | 中兴通讯股份有限公司 | Method and apparatus for communicating over unlicensed frequency bands |
| CN106302215A (en)* | 2016-08-30 | 2017-01-04 | 华为技术有限公司 | A kind of method and device E-Packeted |
| CN109257292B (en)* | 2017-07-14 | 2023-05-23 | 中兴通讯股份有限公司 | RCS load balancing method and device |
| CN109688615B (en)* | 2017-10-19 | 2022-05-10 | 富士通株式会社 | Wireless link routing cost assessment method, device and terminal equipment |
| CN108901053B (en)* | 2018-06-28 | 2021-07-13 | 广东工业大学 | An industrial wireless mesh router deployment method, device and system |
| CN110351885B (en)* | 2019-06-29 | 2020-10-30 | 中国人民解放军军事科学院国防科技创新研究院 | Wireless distributed cooperative network opportunistic channel access method based on threshold measurement |
| CN110505533B (en)* | 2019-07-09 | 2021-06-01 | 杭州亿圣信息技术有限公司 | Method for error code retransmission control in TCP video transmission |
| CN110351189B (en)* | 2019-07-12 | 2021-06-15 | 北京智芯微电子科技有限公司 | Routing control method for real-time edge computing |
| CN110391879B (en)* | 2019-07-15 | 2020-08-18 | 湖南大学 | Packet loss recovery method, device and computer equipment for data transmission network |
| CN111212456B (en)* | 2020-01-16 | 2022-07-08 | 中国电建集团成都勘测设计研究院有限公司 | Multi-path routing method for low-power-consumption long-distance Internet of things based on geographic position |
| CN111405630B (en)* | 2020-03-19 | 2021-10-01 | 深圳市吉祥腾达科技有限公司 | Mesh path selection method and system |
| CN113297027B (en)* | 2020-08-31 | 2025-02-28 | 阿里巴巴集团控股有限公司 | Method, device and database for selecting computing nodes |
| CN114040467B (en)* | 2021-10-25 | 2023-10-03 | 中国联合网络通信集团有限公司 | A method, device, server and storage medium for determining a transmission path |
| TWI804337B (en)* | 2022-06-02 | 2023-06-01 | 晶絡科技股份有限公司 | Method to reduce packet transmission delay |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101674630A (en)* | 2009-09-25 | 2010-03-17 | 南京邮电大学 | A Congestion-Aware Cross-Layer Routing Implementation Method |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP1988851A2 (en)* | 2006-02-14 | 2008-11-12 | Sadra Medical, Inc. | Systems and methods for delivering a medical implant |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101674630A (en)* | 2009-09-25 | 2010-03-17 | 南京邮电大学 | A Congestion-Aware Cross-Layer Routing Implementation Method |
| Title |
|---|
| A Novel Ant Colony Based Cross-layer QoS Routing Algorithm for Wireless Mesh Networks;Zhang Hui 等;《IEEE Xplore DIGITAL LIBRARY》;IEEE;20081112;第66-68页* |
| ext=.pdf》.Springer,2010,正文全文.* |
| Hai-tao Zhao 等.A Cross-Layer Routing Scheme Using Adaptive Retransmission Strategy for Wireless Mesh Networks.《http://download.springer.com/static/pdf/614/art%253A10.1007%252Fs11277-010-0137-y.pdf?auth66=1402747844_bc3ca9a510d269e7ff391ae5a46a62e3&* |
| Publication number | Publication date |
|---|---|
| CN102387559A (en) | 2012-03-21 |
| Publication | Publication Date | Title |
|---|---|---|
| CN102387559B (en) | Cross-layer route optimization method and device for wireless Mesh network | |
| CN101938770B (en) | Wireless network maximum retransmission times optimization method based on network channel state | |
| Kliazovich et al. | Cross-layer congestion control in ad hoc wireless networks | |
| CN107846706B (en) | Congestion-avoiding code-aware wireless mesh network multi-path routing method | |
| Flora et al. | A survey on congestion control techniques in wireless sensor networks | |
| CN101296180B (en) | Wireless Mesh network self-adapting routing method based on throughput performance | |
| CN101932062B (en) | Multipath routing method in Ad Hoc network environment | |
| CN111479306A (en) | Q-learning-based QoS (quality of service) routing method for self-organizing network | |
| CN103118413B (en) | A kind of IPv6 industrial wireless sensor network method for routing based on deterministic schedule | |
| CN101286930A (en) | A Congestion Adaptive Routing Method for Multi-Hop Wireless Ad Hoc Networks | |
| Zhu et al. | On accurate energy consumption models for wireless ad hoc networks | |
| Alipio et al. | RT-CaCC: A reliable transport with cache-aware congestion control protocol in wireless sensor networks | |
| CN102438290A (en) | A Wireless Network Routing Method Based on Directional Antenna | |
| Wang et al. | ECCO: A novel end-to-end congestion control scheme in multi-hop cognitive radio ad hoc networks | |
| Zafar et al. | A survey of transport layer protocols for wireless sensor networks | |
| CN117098181A (en) | Cross-layer perception-based Internet of vehicles joint congestion control method | |
| CN103108372A (en) | Interference sensing cross-layer routing method based on node sending and receiving capacity | |
| CN108135020A (en) | A kind of wireless sensor network opportunistic routing protocol design method based on network code | |
| Chakeres et al. | Perceptive admission control for wireless network quality of service | |
| CN110868727A (en) | Optimization method of data transmission delay in wireless sensor network | |
| CN102413540B (en) | Cognitive-Based Network Coding and Routing Combined Unicast Method for Ad Hoc Networks | |
| CN114531716A (en) | Routing method based on energy consumption and link quality | |
| CN105262643A (en) | Method for differentiating packet loss based on TD-LTE mobile network transmission characteristics | |
| CN109618385B (en) | A reliable and efficient method for detecting selfish nodes in opportunistic networks | |
| Tao et al. | A novel congestion detection and avoidance algorithm for multiple class of traffic in sensor network |
| 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 | ||
| CF01 | Termination of patent right due to non-payment of annual fee | Granted publication date:20150603 |