CN1333535C

CN1333535C - Method for realizing shortest route based on receiver channel self-adapting

Info

Publication number: CN1333535C
Application number: CNB2004100015395A
Authority: CN
Inventors: 田辉; 谢芳; 张平
Original assignee: Spreadtrum Communications Shanghai Co Ltd; Beijing University of Posts and Telecommunications
Current assignee: Spreadtrum Communications Shanghai Co Ltd; Beijing University of Posts and Telecommunications
Priority date: 2004-01-13
Filing date: 2004-01-13
Publication date: 2007-08-22
Anticipated expiration: 2024-01-13
Also published as: CN1558568A

Abstract

The present invention provides a method for realizing the shortest path routing based on the channel adaptation of the receiver in the mobile communication system, the method includes the steps of: the mobile station collects the information of the mobile communication network in real time; the mobile station communicates with other mobile The channel between stations performs quality estimation, and determines the modulation rate with other mobile stations; the mobile station calculates the channel quality factor of link i with other mobile stations through the following formula; determines based on the following formula The link cost of the link i between the mobile station X and the mobile station Y; each mobile station maintains a link state matrix CSM; based on the link state matrix, determine the shortest path from the mobile station to the destination node .

Description

A Method of Realizing Shortest Path Routing Based on Receiver-Based Channel Adaptation

技术领域technical field

本发明涉及一种采用自适应调制技术的无线系统，尤其涉及一种自组织(Ad hoc)移动网络和中继系统中最短径路由的实现方法。The present invention relates to a wireless system using adaptive modulation technology, in particular to a method for realizing the shortest path routing in an ad hoc mobile network and a relay system.

背景技术Background technique

随着移动通信技术的发展和互联网的应用普及，未来的移动通信系统希望能够提供局域和广域的通信环境，满足人们随时随地的信息访问、计算和通信的需求。With the development of mobile communication technology and the popularization of Internet applications, the future mobile communication system hopes to provide a local and wide area communication environment to meet people's needs for information access, computing and communication anytime and anywhere.

自组织(Ad hoc)移动网络方便、快捷、不受时间和地点限制的特点，使其不仅可以单独使用，满足人们直接通信的需求，而且可以叠加在现有基础设施的网络，以加强覆盖和扩展业务，为用户提供自适应的、灵活的接入服务。Self-organizing (Ad hoc) mobile network is convenient, fast, and not limited by time and place, so that it can not only be used alone to meet the needs of people's direct communication, but also can be superimposed on the existing infrastructure network to strengthen coverage and Expand services and provide users with adaptive and flexible access services.

对于一般的通信网络，其性能的一个主要因素是路由选择。优化的路由算法应该是基于目前的网络状态，即应该是动态或自适应的。评价一个路由算法，主要依赖于它所要优化的目标函数。在通常情况下，路由算法应该力图实现下列一个或者几个目标：快速、准确地传递分组；自适应网络拓扑结构的变化；适应源和目的节点之间业务量的变化；具有避开临时拥塞链路的能力；决定网络连通性的能力；低开销。For general communication networks, a major factor in their performance is routing. The optimized routing algorithm should be based on the current network state, ie it should be dynamic or adaptive. The evaluation of a routing algorithm mainly depends on the objective function it needs to optimize. Under normal circumstances, the routing algorithm should try to achieve one or more of the following goals: fast and accurate delivery of packets; adaptive network topology changes; adapt to changes in traffic between source and destination nodes; avoid temporary congestion chains The ability of the road; the ability to determine the connectivity of the network; low overhead.

对于Ad hoc移动网络来讲，由于其动态的拓扑结构和无线资源的限制，使路由算法的研究更富有挑战性。已有的Ad hoc路由的研究着重于强调在源节点和目的节点之间建立路由，两个节点之间的通信链路是否存在取决于两者之间的距离是大于还是低于某一个门限距离。所有“存在”的连接被认为具有相同的链路质量而不考虑无线信道的不可靠和不稳定因素，如Ad hoc按需路由协议(AODV)和动态源路由协议(DSR)等，上面这种假设在有线信道中是正确的，但是在无线信道中却并非如此。受到严重衰落或处于高密度区域中的节点，将经历超负荷和多用户干扰。尽管节点间的地理位置没有发生变化，但通过这种链路和节点的通信将是无效的。而有效的路由应该能够根据信道质量自适应地改变路径，从而获得更好的网络性能。For Ad hoc mobile network, due to its dynamic topological structure and wireless resource limitation, the research of routing algorithm is more challenging. The existing Ad hoc routing research focuses on establishing a route between the source node and the destination node. Whether the communication link between the two nodes exists depends on whether the distance between them is greater than or lower than a certain threshold distance. . All "existing" connections are considered to have the same link quality without considering the unreliable and unstable factors of the wireless channel, such as Ad hoc on-demand routing protocol (AODV) and dynamic source routing protocol (DSR), etc., the above The assumption is true in a wired channel, but not in a wireless channel. Nodes subject to severe fading or in high-density areas will experience overload and multi-user interference. Although the geographic location between nodes has not changed, communication with nodes over such links will be ineffective. And effective routing should be able to adaptively change the path according to the channel quality, so as to obtain better network performance.

考虑链路状态的路由协议中，基于关联的按需路由协议(ABR)是基于路径寿命的按需路由协议，其主要目标在于提供节点间最稳定的路径，这样可以降低重建路由的频率，从而降低开销，节省带宽资源。信号稳定路由(SSR路由)将建立一条最短并且都在强信号链路上的最佳路径，它同样考虑了连接的稳定度问题，并且分为动态路由协议(DRP)和静态路由协议(SRP)两部分。基于分集码的多径路由协议，对每个数据分组进行编码，并以优化的方法将编码后的信息在多条路径上分配，以最小化分组丢失率，平衡业务，改进系统的端到端时延性能。针对跳频分组无线网络提出的基于接收机干扰的自适应、分布式路由，把路径上的干扰量化为路径阻抗，然后寻找最小路径阻抗路由，因而能够有效地处理跳频分组无线网络中的干扰，增加吞吐量和分组成功传输的概率。Among the routing protocols considering the link state, the association-based on-demand routing protocol (ABR) is an on-demand routing protocol based on path life, and its main goal is to provide the most stable path between nodes, which can reduce the frequency of re-routing, thereby Reduce overhead and save bandwidth resources. Signal stable routing (SSR routing) will establish a shortest and best path on a strong signal link. It also considers the stability of the connection and is divided into dynamic routing protocol (DRP) and static routing protocol (SRP). two parts. Based on the multi-path routing protocol of diversity code, each data packet is encoded, and the encoded information is distributed on multiple paths in an optimized way to minimize the packet loss rate, balance the business, and improve the end-to-end of the system Latency performance. Adaptive and distributed routing based on receiver interference proposed for frequency hopping packet wireless networks, quantifies the interference on the path as path impedance, and then finds the minimum path impedance route, so it can effectively deal with interference in frequency hopping packet wireless networks , increasing the throughput and the probability of successful packet transmission.

但是这些算法都没有考虑接收机的状态，并且不能有效地提高带宽利用率。But these algorithms do not consider the state of the receiver, and cannot effectively improve the bandwidth utilization.

发明内容Contents of the invention

考虑无线信道的不可靠和不稳定因素，本发明提出一种适用于自组织Ad hoc移动网络和中继系统的最短径路由实现方法，即基于接收机的信道自适应实现最短径路由(RB-CASPR)的方法。RB-CASPR中的链路代价同时考虑通信信道质量和分组在接收机处可能经历的时延因素，从而进一步发挥自适应调制技术的优势，减小分组的平均传输时延和丢失率。Considering the unreliable and unstable factors of the wireless channel, the present invention proposes a shortest path routing implementation method suitable for self-organizing Ad hoc mobile networks and relay systems, that is, receiver-based channel adaptation realizes the shortest path routing (RB- CASPR) method. The link cost in RB-CASPR takes into account both the communication channel quality and the delay factors that packets may experience at the receiver, so as to further take advantage of the adaptive modulation technology and reduce the average transmission delay and loss rate of packets.

根据本发明的适用于自组织Ad hoc移动网络和中继系统的路由实现方法，既考虑了信道特性，又考虑了接收机节点处的特性。其基本构思在于，利用自适应信道编码和调制技术，将链路吞吐量转变为信道质量因数，同时利用接收机队列的长度代表分组在接收机处可能经历的时延因素，链路代价由信道质量因数和接收机队列的长度组成，根据链路代价来决定最短径路由。According to the routing implementation method suitable for self-organizing Ad hoc mobile networks and relay systems of the present invention, both the channel characteristics and the characteristics of the receiver node are considered. The basic idea is to use adaptive channel coding and modulation technology to convert the link throughput into a channel quality factor, and at the same time use the length of the receiver queue to represent the delay factor that the packet may experience at the receiver, and the link cost is determined by the channel The quality factor and the length of the receiver queue are used to determine the shortest path route according to the link cost.

根据本发明，提供了一种在移动通信系统中基于接收机的信道自适应来实现最短径路由的方法，所述方法包括步骤：According to the present invention, there is provided a method for implementing shortest path routing based on channel adaptation of a receiver in a mobile communication system, the method comprising the steps of:

(1)移动台实时收集移动通信网络的信息；(1) The mobile station collects the information of the mobile communication network in real time;

(2)所述移动台对于与其他移动台之间的信道进行质量估计，并且确定与其他移动台之间的调制速率；(2) The mobile station performs quality estimation on channels with other mobile stations, and determines modulation rates with other mobile stations;

(3)所述移动台通过以下的公式计算与其他移动台之间链路i的信道质量因数： $Q_{i} (t) = \frac{C_{i} (t)}{C_{0}},$ (3) The mobile station calculates the channel quality factor of the link i with other mobile stations by the following formula: $Q_{i} (t) = \frac{C_{i} (t)}{C_{0}},$

其中i＝0，1，2，...k-1，C₀代表最佳信道状态条件下的最大传输速率，C_i代表两个移动台X和Y之间链路i的实际调制速率；Wherein i=0, 1, 2,...k-1, C ₀ represents the maximum transmission rate under the optimal channel state condition, C _i represents the actual modulation rate of the link i between the two mobile stations X and Y;

(4)基于以下的公式来确定移动台X与移动台Y之间链路i的链路代价：(4) Determine the link cost of link i between mobile station X and mobile station Y based on the following formula:

${C C}_{XY X Y} = = \frac{11}{{Q Q}_{XY X Y}} + + β β \times \times {N N}_{Y Y}$

其中Q_xy是移动台X与移动台Y之间链路i的信道质量因数，N_Y是接收机节点Y队列中的分组数目，系数β为所述接收队列的长度在所述链路代价中的权重；where Q _xy is the channel quality factor of link i between mobile station X and mobile station Y, _NY is the number of packets in the queue of receiver node Y, and the coefficient β is the length of the receiving queue in the link cost the weight of;

(5)每个所述移动台维持一个链路状态矩阵CSM，即(5) Each mobile station maintains a link state matrix CSM, namely

CSM＝{E(x，y)_N×N|1≤x，y≤N}CSM＝{E(x,y) _N×N |1≤x, y≤N}

$E E. ((x x,, y the y)) = = {E E.}_{x x}^{y the y} ((t t)) = = \frac{11}{{Q Q}_{XY X Y}} + + β β \times \times {N N}_{Y Y}$

E_x ^y(t)∈{∞，E₀，E₁，...E_i...E_k-1}；E _x ^y (t) ∈ {∞, E ₀ , E ₁ , ... E _i ... E _k-1 };

(6)基于所述链路状态矩阵，确定所述移动台到目的节点的最短路径。(6) Determine the shortest path from the mobile station to the destination node based on the link state matrix.

附图说明Description of drawings

下面参考附图并结合实施例详细描述本发明，其中：Describe the present invention in detail below with reference to accompanying drawing and in conjunction with embodiment, wherein:

图1是基于多状态马尔可夫链的信道模型；Figure 1 is a channel model based on a multi-state Markov chain;

图2是不同的分组到达间隔下平均时延与Beta的关系曲线；Fig. 2 is the relationship curve between average delay and Beta under different packet arrival intervals;

图3(a)-(c)的表示在一定的分组到达间隔下，不同的Beta与平均时延的关系曲线。Figure 3(a)-(c) shows the relationship curves between different Betas and the average time delay under a certain packet arrival interval.

具体实施方式Detailed ways

第一步，对信道进行分析建模：The first step is to analyze and model the channel:

自适应调制系统中，信道的信噪干扰比(SINR)已经被量化为若干阶，并与一定的调制方式一一对应，因此，自适应调制系统的信道变迁转移可以用多状态马尔可夫链来表示。图1示出了基于多状态马尔可夫链的信道模型。In the adaptive modulation system, the signal-to-noise-interference ratio (SINR) of the channel has been quantized into several orders, and corresponds to a certain modulation method one by one. Therefore, the channel transition of the adaptive modulation system can use a multi-state Markov chain To represent. Figure 1 shows a channel model based on a multi-state Markov chain.

在瑞利信道下，令A代表接受信号的信噪比，则A与信号包络的平方成正比。A的概率密度分布是指数形式的，可以写成Under the Rayleigh channel, let A represent the signal-to-noise ratio of the received signal, and A is proportional to the square of the signal envelope. The probability density distribution of A is exponential and can be written as

$P_{A} (a) = \frac{1}{ρ} \exp {- \frac{a}{ρ}}$ 这里，ρ＝E[A]， a≥0 (1) $P_{A} (a) = \frac{1}{ρ} \exp {- \frac{a}{ρ}}$ Here, ρ=E[A], a≥0 (1)

令f_m代表最大多普勒频移，在蜂窝移动通信中， $f_{m} = \frac{v}{λ},$ 其中，v为移动台的速度，λ为波长。而在移动Ad hoc网络中，相互通信的双方都在运动，具有双倍的移动性，这时的最大多普勒频移 $f_{m} = f_{m 1 &RightArrow; 2} = \frac{v 1 + v 2}{c} f_{c},$ 其中，v₁、v₂为节点的速度，f_c为载频。则单位时间内，信噪比衰落至某一给定水平a的次数(类似于电平通过率，可称为信噪比通过率)N_a是一个由f_m和p_A(a)共同影响的函数，则有：Let f _m represent the maximum Doppler frequency shift, in cellular mobile communication, $f_{m} = \frac{v}{λ},$ Among them, v is the speed of the mobile station, and λ is the wavelength. However, in a mobile Ad hoc network, both parties communicating with each other are moving and have double mobility. At this time, the maximum Doppler frequency shift $f_{m} = f_{m 1 &Right Arrow; 2} = \frac{v 1 + v 2}{c} f_{c},$ Among them, v ₁ and v ₂ are the speed of the node, and f _c is the carrier frequency. Then, the number of times the signal-to-noise ratio declines to a given level a per unit time (similar to the level pass rate, can be called the SNR pass rate) N _a is a function jointly affected by f _m and p _A (a) function, there are:

${N N}_{a a} = = \sqrt{\frac{22 πa πa}{ρ ρ}} {f f}_{m m} exp exp {{- - \frac{a a}{ρ ρ}}} - - - - - - ((22))$

令0＝A₀＜A₁＜A₂＜…＜A_k＝∞为SNR的阈值。可以将瑞利信道的信噪比量化为K个状态。如果a∈[A_k，A_k+1)，则称a属于状态S_k，k＝0，1，...，K-1，而这些状态，在自适应调制系统中，可以与不同的调制编码组合方式相对应。Let 0=A ₀ <A ₁ <A ₂ <...<A _k =∞ be the threshold of SNR. The signal-to-noise ratio of a Rayleigh channel can be quantized into K states. If a∈[A _k , A _k+1 ), it is said that a belongs to the state S _k , k=0, 1, ..., K-1, and these states, in the adaptive modulation system, can be different from Corresponding to the combination of modulation and encoding.

根据式(1)，可以写出信噪比在k状态的稳态概率为：According to formula (1), the steady-state probability of the signal-to-noise ratio in state k can be written as:

${p p}_{k k} = = {&Integral; &Integral;}_{k k}^{{A A}_{k k + + 11}} \frac{11}{ρ ρ} exp exp {{- - \frac{x x}{ρ ρ}}} dx dx = = exp exp {{- - \frac{{A A}_{k k}}{ρ ρ}}} - - exp exp {{- - \frac{{A A}_{k k + + 11}}{ρ ρ}}} - - - - - - ((33))$

在我们的研究中，假定信道的衰落足够慢，使得状态的改变只可能发生在相邻状态之间。这个假设在实际应用中的意义在于对信道的预测和反馈能够跟得上信道的变化。令p_i，j表示状态i，j之间的转移概率，则有p_i，j＝0，|i-j|＞1。In our study, it is assumed that the fading of the channel is slow enough that a state change is only possible between adjacent states. The significance of this assumption in practical applications is that the prediction and feedback of the channel can keep up with the change of the channel. Let p _{i, j} represent the transition probability between states i, j, then p _{i, j} =0, |ij|>1.

基于这样的假设，下面求转移概率p_i，j。Based on such an assumption, the transition probability p _i,j is calculated below.

由于转移只能在相邻状态之间。那么，事件：从状态k向状态k-1的转移概率应当是阈值为A_k的信噪比通过率除以每秒内发生k状态的次数。设链路的符号速率为R symbols/s，则每秒内，发生k状态的次数可以用每秒内在k状态传送的符号数目R^k来表示，并有Since transitions can only be between adjacent states. Then, the event: the transition probability from state k to state k−1 should be the SNR pass rate with threshold A _k divided by the number of occurrences of state k per second. Assuming that the symbol rate of the link is R symbols/s, the number of occurrences of state k in one second can be represented by the number of symbols R ^k transmitted in state k in one second, and there is

R^k＝R×p_k。 (4)R ^k =R×p _k . (4)

记每秒内SINR下降至门限A_k之下的次数为N_k，k＝1，2，3，…，K-1。Record the number of times the SINR drops below the threshold A _k per second as N _k , where k=1, 2, 3, . . . , K-1.

由(2)，有From (2), there are

${N N}_{k k} = = \sqrt{\frac{22 π π {A A}_{k k}}{ρ ρ}} {f f}_{m m} exp exp {{- - \frac{{A A}_{k k}}{ρ ρ}}} - - - - - - ((55))$

则，可得马尔可夫链的转移概率为：Then, the transition probability of the Markov chain can be obtained as:

${p p}_{k k,, k k + + 11} = = \frac{{N N}_{k k + + 11}}{{R R}^{k k}},, k k = = 0,1,2,3 0,1,2,3,, \cdot &Center Dot; \cdot \cdot \cdot &Center Dot;,, K K - - 22 - - - - - - ((66))$

${p p}_{k k,, k k - - 11} = = \frac{{N N}_{k k}}{{R R}^{k k}},, k k = = 1,2,3 1,2,3,, \cdot &Center Dot; \cdot &Center Dot; \cdot &Center Dot;,, K K - - 22 . . - - - - - - ((77))$

p_k，k＝1-p_k，k+1-p_k，k-1，k＝1，2，3，…，K-2 (8)p _{k, k} = 1-p _{k, k+1} -p _{k, k-1} , k=1, 2, 3, ..., K-2 (8)

p_0，0＝1-p_0，1；p_K-1，K-1＝1-p_K-1，K-2 (9)p _0,0 =1-p _0,1 ; p _K-1,K-1 =1-p _K-1,K-2 (9)

可以通过马尔可夫链的平衡特性验证上述推导。The above derivation can be verified by the balance properties of Markov chains.

例如，在状态S₀，根据平衡方程，有For example, in state S ₀ , according to the equilibrium equation, we have

p₀×p_0，1＝p₁×p_1，0 (10)p ₀ ×p _0,1 = p ₁ ×p _1,0 (10)

将(4)-(6)式代入(10)，方程左右两边都等于N₁/R同样，可以验证状态S_k下的平衡方程。Substituting (4)-(6) into (10), the left and right sides of the equation are equal to N ₁ /R. Similarly, the balance equation in state S _k can be verified.

p_k×(p_k，k+1+p_k，k-1)＝p_k-1×p_k-1，k+p_k+1×p_k+1，k (11)p _k ×(p _k,k+1 +p _k,k-1 )=p _k-1 ×p _k-1,k +p _k+1 ×p _k+1,k (11)

再将(4)-(6)式代入(11)，可以看到方程左边为Substituting (4)-(6) into (11), we can see that the left side of the equation is

$\frac{{R R}^{k k}}{R R} \times \times ((\frac{{N N}_{k k + + 11}}{{R R}^{k k}} + + \frac{{N N}_{k k}}{{R R}^{k k}})) = = \frac{11}{R R} (({N N}_{k k + + 11} + + {N N}_{k k}))$

方程右边等于The right side of the equation is equal to

$\frac{{R R}^{k k - - 11}}{R R} \times \times \frac{{N N}_{k k}}{{R R}^{k k - - 11}} + + \frac{{R R}^{k k + + 11}}{R R} \times \times \frac{{N N}_{k k + + 11}}{{R R}^{k k + + 11}} = = \frac{11}{R R} (({N N}_{k k + + 11} + + {N N}_{k k}))$

方程左右两边是相等的，这证明上述的转移概率和稳态概率求取方法能够满足马尔可夫链的稳态平衡特性。The left and right sides of the equation are equal, which proves that the above-mentioned calculation method of transition probability and steady-state probability can satisfy the steady-state equilibrium characteristics of the Markov chain.

上面讨论中，(3)式中的A₀、A₁、A₂、…A_K等值都是预先设定的。因此，信道信噪比(SNR)处于状态S_k的概率分布仅与ρ有关。如果发射功率一定，接收机结构相同，则ρ的大小主要受路径损耗的影响。不同的位置，移动台的ρ值不一样，使得它们所对应的马尔可夫链的稳态概率和各状态间的转移概率也不一样。另外，如果能够测量出节点的移动速度，根据公式 $f_{m} = f_{m 1 &RightArrow; 2} = \frac{v 1 + v 2}{c} f_{c}$ 以及式(4)-(6)式可以估算出状态转移概率。如果节点移动速度不能够测量，则需要节点依据实际测量的SNR变化情况，直接进行统计分析，求出状态转移概率。In the above discussion, the values of A ₀ , A ₁ , A ₂ , ... A _K in formula (3) are all preset. Therefore, the probability distribution that the channel signal-to-noise ratio (SNR) is in state S _k depends only on p. If the transmission power is constant and the receiver structure is the same, the size of ρ is mainly affected by the path loss. In different locations, the ρ value of the mobile station is different, so that the steady-state probability of their corresponding Markov chains and the transition probabilities between states are also different. In addition, if the moving speed of the node can be measured, according to the formula $f_{m} = f_{m 1 &Right Arrow; 2} = \frac{v 1 + v 2}{c} f_{c}$ And formulas (4)-(6) can estimate the state transition probability. If the moving speed of the node cannot be measured, it is necessary for the node to directly perform statistical analysis based on the actual measured SNR change to obtain the state transition probability.

SNR的状态是与一定的调制阶数和信道编码方案一一对应的，而调制阶数和信道编码方案又对应着一定的链路传输速率。因此，我们可以将上述马尔可夫链的各个状态与相应的链路传输速率相对应，就得到了速率变化的马尔可夫链路模型。The state of SNR corresponds to a certain modulation order and channel coding scheme one by one, and the modulation order and channel coding scheme correspond to a certain link transmission rate. Therefore, we can correspond each state of the above-mentioned Markov chain to the corresponding link transmission rate, and obtain a Markov link model of rate change.

信道自适应最短径路由的研究中，由于运用有限状态马尔可夫信道模型对衰落信道进行建模，并且采用了自适应信道编码和调制技术。移动终端之间的时变信道所产生的信道吞吐量也是时变的。这样就可以在路由的研究中，将物理层的技术细节屏蔽起来，使得研究易于进行。In the study of channel adaptive shortest path routing, the fading channel is modeled by using the finite state Markov channel model, and adaptive channel coding and modulation techniques are used. The channel throughput generated by the time-varying channel between mobile terminals is also time-varying. In this way, the technical details of the physical layer can be shielded in the research of routing, making the research easy to carry out.

第二步，利用按需路由协议或者表驱动路由协议中的有关机制实时收集移动通信网络信息，建立路由表(P9)，用矩阵来记录每对节点之间的即时链路状况和转移到下一状态的概率。The second step is to use the on-demand routing protocol or the relevant mechanisms in the table-driven routing protocol to collect real-time mobile communication network information, establish a routing table (P9), and use the matrix to record the instant link status between each pair of nodes and transfer to the next step. probability of a state.

第三步，计算信道质量因数。如果用s＝{C₀，C₁，...C_k-1}代表一系列有限的信道状态，C₀代表最好信道状态条件下的最大传输速率(也就是对应于最高的调制阶数)，C_i代表两个终端之间链路i的实际调制速率，则两个终端之间链路i的信道质量因数为： $Q_{i} (t) = \frac{C_{i} (t)}{C_{0}}$ i＝0，1，2，...k-1，由The third step is to calculate the channel quality factor. If s={C ₀ , C ₁ ,...C _k-1 } represent a series of finite channel states, C ₀ represents the maximum transmission rate under the best channel state conditions (that is, corresponds to the highest modulation order ), C _i represents the actual modulation rate of link i between two terminals, then the channel quality factor of link i between two terminals is: $Q_{i} (t) = \frac{C_{i} (t)}{C_{0}}$ i=0,1,2,...k-1, by

它反映信道质量的好坏。所以，最好链路的质量因数是1，而其它链路的质量因数随着C_i的减小而小于1。It reflects the quality of the channel. Therefore, the quality factor of the best link is 1, while the quality factors of other links are less than 1 as C _i decreases.

第四步，计算链路代价。在基于接收机的信道自适应最短径路由(RB-CASPR)中，链路代价是The fourth step is to calculate the link cost. In receiver-based channel-adaptive shortest path routing (RB-CASPR), the link cost is

${C C}_{XY X Y} = = \frac{11}{{Q Q}_{XY X Y}} \times \times β β \times \times {N N}_{Y Y}$

其中，

是X到Y链路代价的信道质量部分，由调制阶数决定，N_Y是接收机节点Y队列中的分组数目，系数β的选择是基于这两部分在总代价中的权重，可以通过计算机仿真进行代价系数的选择。in,

is the channel quality part of the link cost from X to Y, which is determined by the modulation order, _NY is the number of packets in the receiver node Y queue, and the choice of coefficient β is based on the weight of these two parts in the total cost, which can be calculated by computer The simulation carries out the selection of the cost coefficients.

第五步，每个移动台维持一个链路状态矩阵(CSM)。In the fifth step, each mobile station maintains a link state matrix (CSM).

CSM＝{E(x，y)_N×N|1≤x，y≤N}CSM＝{E(x,y) _N×N |1≤x, y≤N}

$E E. ((x x,, y the y)) = = {E E.}_{x x}^{y the y} ((t t)) = = \frac{11}{{Q Q}_{XY X Y}} + + β β \times \times {N N}_{Y Y},,$ ${E E.}_{x x}^{y the y} ((t t)) &Element; &Element; {{\infty \infty,, {E E.}_{00},, {E E.}_{11,,},, . . . . . . {E E.}_{i i} . . . . . . {E E.}_{k k - - 11}}}$

如果E_x ^y(t)不等于无穷，则说明节点x能够直接发送数据包给节点y。否则，节点x和节点y则不能直接通信。If E _x ^y (t) is not equal to infinity, it means that node x can directly send data packets to node y. Otherwise, node x and node y cannot communicate directly.

第六步，根据连接状态矩阵CSM，每一个源移动台利用基于贝尔曼．福特(Bellman-Ford)最短路径算法的距离向量方法来寻找最短径路由，这样就可以得到一条通往目的节点的、具有最小代价的最短路径。In the sixth step, according to the connection state matrix CSM, each source mobile station uses the Bellman-based. The distance vector method of the Ford (Bellman-Ford) shortest path algorithm is used to find the shortest path route, so that a shortest path with the minimum cost to the destination node can be obtained.

本发明图2中的三条曲线分别对应三种不同的分组到达率，横轴代表系数β。β等于0时，即为信道自适应最短径(CASPR)路由。The three curves in FIG. 2 of the present invention respectively correspond to three different packet arrival rates, and the horizontal axis represents the coefficient β. When β is equal to 0, it is Channel Adaptive Shortest Path (CASPR) routing.

可以看出当分组到达率比较小时(2packets/s)，β的变化对时延没有影响。也就是对于小的分组到达率来讲，到达的分组能够马上被处理，不会造成分组在队列中的排队，所以与不考虑队列长度时的路由效果区别不大；但随着分组到达率的增加，RB-CASPR与CASPR之间的差别就显示出来了：总的趋势是β值大于2以后，时延随着β的增加而增加，并且分组到达率越大，时延增加的越快。而在β等于0.5、1和1.5时表现出RB-CASPR性能好于CASPR。It can be seen that when the packet arrival rate is relatively small (2packets/s), the change of β has no effect on the delay. That is to say, for a small packet arrival rate, the arriving packets can be processed immediately without causing packets to be queued in the queue, so the routing effect is not much different from that when the queue length is not considered; but as the packet arrival rate increases Increase, the difference between RB-CASPR and CASPR is displayed: the general trend is that after the value of β is greater than 2, the delay increases with the increase of β, and the greater the packet arrival rate, the faster the delay increases. And when β is equal to 0.5, 1 and 1.5, the performance of RB-CASPR is better than that of CASPR.

因β增加，队列长度在路由代价中占的比重加大，而大到一定程度，信道速率的作用就不明显了，有可能出现只是根据节点队列长度来选择路由的情况。但所选择的路径有可能信道质量差(容量低)，从而造成大的分组时延，所以β值必须在某一取值范围(即信道和接收机处的条件在代价中占合适的比例)时，RB-CASPR路由才能对分组时延性能有所改善。为进一步验证上述结论，图3(a)、(b)、(c)显示了β分别取0、0.5、1、1.5和2时，时延与分组到达率的关系。As β increases, the proportion of the queue length in the routing cost increases, but to a certain extent, the effect of the channel rate is not obvious, and it may happen that the route is selected only according to the node queue length. However, the selected path may have poor channel quality (low capacity), resulting in a large packet delay, so the value of β must be within a certain value range (that is, the conditions at the channel and the receiver account for an appropriate proportion of the cost) , RB-CASPR routing can improve packet delay performance. To further verify the above conclusions, Figure 3(a), (b), and (c) show the relationship between delay and packet arrival rate when β is 0, 0.5, 1, 1.5, and 2 respectively.

从图3(a)-(c)中看出，在我们的仿真环境下，β的合适取值为1和1.5。而低业务量时(数据速率小于5 Packets/Second)，β取1.5时的性能略逊于取1时的性能；高业务量时，β的三个取值(0.5、1、1.5)都可以获得好的性能。It can be seen from Figure 3(a)-(c) that in our simulation environment, the appropriate values of β are 1 and 1.5. When the traffic is low (data rate is less than 5 Packets/Second), the performance when β is 1.5 is slightly worse than that when 1 is used; when the traffic is high, the three values of β (0.5, 1, 1.5) are all acceptable. get good performance.

总之，针对具体的应用环境，通过实验选择合适的链路代价系数，RB-CASPR路由可以优化CASPR的时延性能。In short, according to the specific application environment, RB-CASPR routing can optimize the delay performance of CASPR by selecting the appropriate link cost coefficient through experiments.

Claims

1. A method for implementing shortest path routing based on channel adaptation of a receiver in a mobile communication system, said method comprising steps:

(1) The mobile station collects the information of the mobile communication network in real time;

(2) The mobile station performs quality estimation on channels with other mobile stations, and determines modulation rates with other mobile stations;

(3) The mobile station calculates the channel quality factor of the link i with other mobile stations by the following formula:

Q_{i} (t) = \frac{C_{i} (t)}{C_{0}},

Wherein i=0, 1, 2,...k-1, C ₀ represents the maximum transmission rate under the optimal channel state condition, C _i represents the actual modulation rate of the link i between the two mobile stations X and Y;

(4) Determine the link cost of link i between mobile station X and mobile station Y based on the following formula:

{C C}_{XY X Y} = = \frac{11}{{Q Q}_{XY X Y}} + + β β \times \times {N N}_{Y Y}

where Q _xy is the channel quality factor of link i between mobile station X and mobile station Y, _NY is the number of packets in the queue of receiver node Y, and the coefficient β is the length of the receiving queue in the link cost the weight of;

(5) Each mobile station maintains a link state matrix CSM, namely

CSM＝{E(x,y) _N×N |1≤x, y≤N}

E E. ((x x,, y the y)) = = {E E.}_{x x}^{y the y} ((t t)) = = \frac{11}{{Q Q}_{XY X Y}} + + β β \times \times {N N}_{Y Y}

{E E.}_{x x}^{y the y} = = ((t t)) &Element; &Element; {{\infty \infty,, {E E.}_{00},, {E E.}_{11},, . . . . . . {E E.}_{i i} . . . . . . {E E.}_{k k - - 11}}};;

(6) Determine the shortest path from the mobile station to the destination node based on the link state matrix.

2. The method according to claim 1, wherein said mobile station collects information of said mobile communication network in real time using an on-demand routing protocol or table-driven routing.

3. The method according to claim 1, wherein said channel quality factor Q _i (t) < 1.

4. The method according to claim 1, wherein the maximum transmission rate under optimum channel state conditions is achieved by the highest modulation order.

5. The method according to claim 1, wherein said weight [beta] is determined based on the channel quality and the length of the queue in the receiver.

6. The method of claim 1, wherein said mobile station determines a shortest path from said mobile station to a destination node based on said link state matrix and using a distance vector method based on a Bellman-Ford shortest path algorithm.