当前位置：文档之家 › 计算无线通信网络2_终点可靠性的快速算法

计算无线通信网络2_终点可靠性的快速算法

  • 格式：pdf
  • 大小：254.39 KB
  • 文档页数：4

收稿日期:2003-07-10;修订日期:2003-09-16 基金项目:国家自然科学基金资助项目(69973011) 作者简介:高飞(1968-),男,辽宁铁岭人,讲师,博士研究生,主要研究方向:网络容错分析;　王光兴(1937-),男,辽宁沈阳人,教授,博士生导师,主要研究方向:网络管理系统、网络容错系统;　阎家斌(1964-),男,辽宁沈阳人,副教授,主要研究方向:数值分析.文章编号:1001-9081(2004)01-0025-03计算无线通信网络22终点可靠性的快速算法高　飞1,王光兴1,阎家斌2(东北大学信息科学与工程学院,辽宁沈阳110003;　2.东北大学数学系,辽宁沈阳110003)(gaofei1968@ )摘　要:提出计算无线通信网络从源点到汇点(ST )可靠性的一个新拓扑公式。

该公式本质上是将容斥原理公式和不交和公式融合在一起,公式中各项和网络的一类特殊子网络一一对应,与相应的Satyanarayanna 公式比较,该公式包含更少的项和更少的算术运算。

提出一个计算从网络源点到汇点(ST )可靠性算法。

这个算法本质上是通过系统地枚举网络的一类特殊子网络而计算其ST 可靠性或生成可靠性表达式。

由于所需枚举的子网络数量小于相应的Satyanarayanna 算法需枚举的子网络数量,因此新算法性能优于Satyanarayanna 算法。

最后通过一个具体例子说明了这个结论。

关键词:算法;可靠性;可靠性表达式;容斥原理;无线通信网络中图分类号:TP393.04;TP302.7 文献标识码:AA R apid Algorithm for Computing STR eliability of R adio 2communication N et worksG AO Fei 1,WAN G Guang 2xing 1,YAN Jia 2bin 2(1.School of Inf orm ation Science and Technology ,Northeastern U niversity ,S henyang L iaoning 110003,China ;2.Depart ment of M aths ,Northeastern U niversity ,S henyang L iaoning 110003,China )Abstract :A new topological formula for computing ST reliability of radio 2communication networks (RCN )from sources to terminals is bining Inclusion Exclusion principle with disjoint sum of products formula ,the new formula contains terms which corres pond one by one to a class of special subnetworks.For a given network ,terms of the new formula are fewer than those corres ponding Satyaranayanna formula.An algorithm for computing ST reliability is presented.It com 2putes ST reliability or produces a ST reliability expression by enumerating a class of special subnetworks of given networks.Because the number of this class of subnetworks needed to be enumerated is relativel y small ,the new algorithm πs performance is better than Satyaranayanna πs algorithm.Finally an example illustrates the conclusion.K ey w ords :algorithm ;reliability ;reliability expression ;inclusion exclusion principle ;radio 2communication network1　引言无线通信网络不仅价格便宜,而且适合某些特殊场合,例如:移动通信网络、自组网及数据采集系统等,其可靠性问题已经引起人们的重视。

在文献[1]中提出一个概率无向图模型,并且证明了计算RCN 的K 2终点可靠性是NP 2难问题,提出一个计算RCN 的22终点可靠性的近似算法。

对于一些特殊的RCN 也被研究[2,3],在文献[4]中给出了K 2终点可靠性的因子分解算法。

文献[6]是网络可靠性的研究的重大突破,对此网络可靠性学者已经取得了共识[7]。

在文献[6]中提出了P 无圈子图的概念,使得计算网络的ST 可靠性最终归结为枚举网络中所有P 无圈子图。

后来Satyanarayanna 等人将上述思想推广到计算SA T 和SKT 可靠性[7,8]。

文献[5]改进了文献[6]的结果,提出了adp 无圈子图的概念,使得网络的ST 可靠性计算归结为网络中所有adp 无圈子图枚举,因为adp 无圈子图是一类特殊的P 无圈子图,一般地说,给定一个网络,其adp 无圈子图的数量远远小于P 无圈子图的数量。

本文考虑的RCN 网络可用一概率有向图G (V ,E )表示,其结点有两种状态运行和失效,边可靠,结点失效概率已知且相互独立,V 中有两个特殊结点s 和t ,RCN22可靠性是指s 能传送信息到达t 的概率。

由于并行边在RCN 中并不起作用,因此为了讨论方便假定RCN 中无并行边。

容斥原理是解决有线网络可靠性的有效方法,该原理对于RCN 同样成立。

在本文中提出了最简路概念,给出一个计算有向RCN 的ST 可靠性的拓扑公式,根据该拓扑公式给出了一个计算RCN 的22终点可靠性的快速算法。

2　定义、符号2.1　定义P ij :一条从i 到j 的路。

最简路S P ij :一条从i 到j 的路,且路上所有结点集合没有子集可以组成P ij 。

P 图:图G 每条弧至少在它的一条从源点s 到汇点t 的S P 路上。

第24卷第1期2004年1月计算机应用Computer ApplicationsVol.24,No.1Jan.,2004P无圈子图:一个子图它是P图且不含圈。

中性序列(Neutral Sequence):由点和边所组成的交替序列,且它的每个内部结点出度与入度正好等于1,且一个P图删去它后仍是一个P图。

并行路:(u,v)是G的一条边,P uv是不为(u,v)的从u 到v的一条路,则称P uv为(u,v)的并行路。

极大P子图:设st路生成的子图为G,若有从s到t的路且该路包含的S P路不在G上,则添加该S P路不在G上的所有边到G上,将所有这样的S P路添加到G上。

这样生成的图称G的极大P子图。

构型:若干st路生成G(V,E)的子图G i,则称以这些路为元素的集合为G i的一个构型。

asp无圈子图:不含特定路集合D中任一路的P无圈子图。

2.2　记号G(V,E):RCN网络,其结点集合为V,边集合为E。

G(V,E)是一个有向概率图,即具有源点S及汇点T有向图,每条弧至少在其一S P路上,且其每个结点正常工作概率已知且相互独立。

s,t:分别表示G的源点和汇点。

A+B(A・B):事件A与事件B的并(交)。

A:表示事件A的补。

m:表示G的最简路的数量。

K P:表示路P上的结点集合。

x i(x i):表示结点x的状态为运行(失效)。

p i:结点v i的工作概率或可靠性。

R(G):表示RCN的22终点可靠性。

3　求RCN22终点可靠性的拓扑公式考虑一RCN网络G(V,E),V=(1,2,……n)和E= (x1,x2,…,x e)为G的结点集合和边集合,n=|V|,e=|E |。

p i表示结点的运行概率,q i=1-p i表示结点失效概率。

网络RCN22终点可靠性的定义为[1]:R(G)=RCN中至少有一从s到t路每个结点均运行的概率=Pr(∑P i)(1)公式(1)中P i=1,2,…,n p,为图G的第i个st路,n p为路的数目,Pr(・)表示概率。

根据布尔代数公理Pr(x+xy)=Pr(x)可知,若P不是最简路,则P的结点集合K P有子集合设为K S P构成最简路S P,Pr(P+S P)=Pr(K S P∪K P)=Pr(K S P)=Pr(S P)。

因此有:定理1:R(G)=Pr(∑S P i)i=1,2,…,m,m为S P路数目。

定理2:S P为st最简路,则为其结点集合K S P所唯一确定。

证明:S P的路长|S P|=|K S P|-1=t,设S P= sw1w2…w t-1t,由于RCN中无并行边,若S P不唯一,设另一S P2路为:w i1,w i2,…,w it-1。

与S P相比在S P2中至少有一结点前移,设为w i,w i的父亲为w t,j<i-1,在G中w i与w j 相邻,那么sw1w2…w j w i w i+1…w t-1t是一P st路。

且其长度小于|Y|-1,这与S P是最简路相矛盾,因此S P为K S P所唯一确定。

定理3:网络G的所有路是都是S P路的充要条件是G的任意一条边都没有并行路。

证明:G若有一条边(u,v)并行路P uv,设P=s…(u, v)…t,则s…P uv…t是G的一条非S P路,因此网络G的所有路是都是S P路则G的任意一条边都没有并行路。

G若有非S P路P,则一定有一S P路,其结点是P的子集,设u是P和S P第一个分开的结点,v是S P上的u的接入点,由于v是P上的结点,因此P上的P uv路是边(u,v)的并行路,所以G的任意一条边都没有并行路则网络G的所有路是都是S P路。

根据容斥原理可知:R(G)=∑m i=1P(S P i)-∑i<j P(S P i)P(S P j)+…+ (-1)k+1P(S P i1)…P(S P ik)+…+(-1)m+1P(S P i1)…P(S P im)共计2m项,这里有许多重复的子图,由于边是永远正常工作的,所有子图只与点有关,所以添加边不影响结果,因此我们把所有子图均变成极大P子图,合并相同的极大P子图,得到如下公式:R(G)=∑d i Pr(G i)(2)引理1:网络G的可靠性为R(G)=∑d i Pr(G i),为G 的P子图,d i=(-1)n i+e i+1。

合集下载

通信原理公式

通信原理公式

通信原理公式
通信原理的数学公式如下：
1. 香农公式：
C = B * log2(1 + S/N)
其中，C是信道容量，B是信道带宽，S是信号的平均功率，N是噪声的功率。

2. 奈奎斯特准则：
最大传输速率 = 2B * log2(V)
其中，B是信道带宽，V是每个信号点所能表示的离散数。

3. 傅里叶变换：
X(f) = ∫ x(t)e^(-j2πft) dt
其中，X(f)表示信号在频域上的频谱，x(t)表示信号在时域上的波形。

4. 采样定理：
B >= 2fmax
其中，B是采样频率，fmax是信号的最高频率成分。

5. 时域与频域转换：
x(t) = ∑ X(f)e^(j2πft) df
其中，x(t)表示信号在时域上的波形，X(f)表示信号在频域上的频谱。

6. 误码率与信噪比关系：
P(e) ≈ Q(sqrt(2SNR))
其中，P(e)是误码率，SNR是信噪比。

这些公式在通信原理中起着重要的作用，在分析和设计通信系统时可以利用这些公式进行计算和评估。

无线通信网络中的快速频谱感知算法研究

无线通信网络中的快速频谱感知算法研究

无线通信网络中的快速频谱感知算法研究快速频谱感知算法在无线通信网络中的研究无线通信网络中的频谱感知是指通过对周围环境的频谱占用情况进行实时监测和分析，以确定可用频率资源的技术。

快速频谱感知算法则是为了解决实时性要求高、频谱资源稀缺的无线通信网络中频谱感知的问题而设计的一类算法。

无线通信网络的快速频谱感知算法的研究可分为以下几个方面：频谱感知的目标，频谱感知的原理与技术，频谱感知的算法设计与实现，频谱感知的性能评估与应用。

首先，针对频谱感知的目标，研究者们通常希望通过频谱感知算法能够实现高效的频谱利用，提高通信可靠性和容量。

在无线通信网络中，频谱资源是有限的，因此通过快速频谱感知算法，可以实时地监测和分析频谱占用情况，从而及时调整频率资源的分配，提高频谱利用效率。

其次，频谱感知的原理与技术也是研究的重点。

传统的频谱感知技术主要基于能量检测，即通过测量信号的能量水平来判断频谱是否被占用。

然而，能量检测存在固有的缺陷，比如对于弱信号的检测效果较差。

因此，研究者们提出了许多新的频谱感知技术，如循环谱感知、协方差感知、二阶泄露感知等，这些技术可以提高频谱感知的准确性和可靠性。

接下来，频谱感知的算法设计与实现是研究的关键。

快速频谱感知算法需要具备高效的计算能力和实时性，从而能够快速地对周围环境的频谱占用情况进行感知和分析。

在算法设计方面，研究者们通常借鉴了机器学习、卷积神经网络等技术，利用大数据实现高效的感知算法。

最后，频谱感知的性能评估与应用是研究的重点。

为了验证快速频谱感知算法的有效性和可行性，研究者通常通过实验和仿真进行性能评估。

在应用方面，快速频谱感知算法可以应用于无线通信网络中的频谱分配、干扰检测与管理等领域，从而提高通信系统的性能和可靠性。

综上所述，快速频谱感知算法在无线通信网络中的研究是为了解决频谱资源稀缺和实时性要求高的问题。

通过对周围环境的频谱占用情况进行实时监测和分析，可以提高频谱利用效率，提高通信系统的性能和可靠性。

无线通信距离计算

无线通信距离计算

无线通信距离计算无线传输距离计算Pr(dBm) = Pt(dBm) - Ct(dB) + Gt(dB) - FL(dB) + Gr(dB) - Cr(dB) Pr：接受端灵敏度Pt: 发送端功率Cr: 接收端接头和电缆损耗Ct: 发送端接头和电缆损耗Gr: 接受端天线增益Gt: 发送端天线增益FL: 自由空间损耗FL(dB)=20 lg R (km) +20 lg f (GHz) + 92.44R是两点之间的距离f是频率=2.4自由空间通信距离方程自由空间通信距离方程设发射功率为PT，发射天线增益为GT，工作频率为f . 接收功率为PR，接收天线增益为GR，收、发天线间距离为R，那么电波在无环境干扰时，传播途中的电波损耗 L0 有以下表达式：L0 (dB) = 10 Lg（ PT / PR ） = 32.45 + 20 Lg f ( MHz ) + 20 Lg R ( km ) - GT (dB) - GR (dB)[举例] 设：PT = 10 W = 40dBmw ；GR = GT = 7 (dBi) ； f = 1910MHz问：R = 500 m 时， PR = ？解答： (1) L0 (dB) 的计算 L0 (dB) = 32.45 + 20 Lg 1910( MHz ) + 20 Lg 0.5 ( km ) - GR (dB) - GT (dB)= 32.45 + 65.62 - 6 - 7 - 7 = 78.07 (dB))（2） PR 的计算PR = PT / ( 10 7.807 ) = 10 ( W ) / ( 10 7.807 ) = 1 ( μW ) / ( 10 0.807 ) = 1 ( μW ) / 6.412 = 0.156 ( μW )= 156 ( mμW ) # 顺便指出，1.9GHz电波在穿透一层砖墙时，大约损失 (10~15) dB 无线传输距离估算传输距离估算无线网络系统的传输距离或覆盖围受多种因素的影响，除了信号源的发射功率、天线的增益、接收设备的灵敏度、频率、自由空间衰减、噪声干扰外，还有现场环境的影响，例如建筑物、树木和墙壁的遮挡，人体、气候等对电磁波的衰减，纯粹自由空间的传输环境在实际应用中是不存在的。

无线网络中的信道估计与预测算法研究

无线网络中的信道估计与预测算法研究

无线网络中的信道估计与预测算法研究随着现代通信技术的不断发展，无线网络已经成为我们日常生活中不可或缺的一部分。

在无线通信中，信道估计和预测是非常重要的研究领域，它们可以提高信号的可靠性，从而改善无线通信的质量。

本文将探讨信道估计和预测算法在无线网络中的应用。

一、信道估计算法信道估计是指利用已知的信号特征、接收信号和传输信道特性，估计出传输信道的特性的过程。

在无线网络中，信道通常是时变的，因此需要不断地对信道进行估计和更新以保持良好的信号质量。

现在常用的信道估计算法有以下几种：1、最小二乘法最小二乘法是一种最基础的信道估计算法，它的原理是通过对接收信号与已知发送信号进行比较，获取信道的频率响应。

虽然最小二乘法简单易用，但是它的精度以及对抗多径干扰的能力较为有限。

2、Kalman滤波算法Kalman滤波算法可以根据系统的动态特性，对传输信道进行递归滤波，从而获得更优秀的估计结果。

该算法可对窄带和宽带信号均进行估计，并且对于多径干扰的处理效果也很好。

但是Kalman滤波算法需要占用较多的计算资源，对处理实时性的要求较高。

3、模型判别算法模型判别算法是一种常用的自适应算法，它通过对已知信号进行建模，将接收到的信号与模型进行比较，从而获取信道的特性。

该算法精度高，适用于多种信号类型，但对于高速移动的通信设备和多径干扰的抗干扰能力相对较弱。

二、信道预测算法信道预测是指利用已知的信号特征和信道特性，对未来的信道状况进行预估的过程。

在无线网络中，信道的时变性使得信道预测非常重要，因为只有及时预测未来的信道状况，才能及时采取相应的措施来保证通信的可靠性。

目前常用的信道预测算法有以下几种：1、神经网络算法神经网络算法可以对信道进行非线性预测，并且对噪音的干扰能力非常强。

该算法可以根据训练集对神经网络进行训练，并输出预测结果，但是需要较大的数据集才能获得较好的预测效果。

2、卡尔曼滤波算法卡尔曼滤波算法在信道预测中同样有良好的预测效果。