论文研究-基于二维导频和降噪滤波的信道估计方法.pdf

所需积分/C币:9 2019-09-11 13:10:53 790KB .PDF
收藏 收藏
举报

为了降低分布式数据流上的连续Skyline计算过程中的通信开销,提出了基于远程过滤的思想并对相关理论基础进行了证明,描述了系统的体系结构并提出了两个过滤模型v_Max和Distance。理论分析和实验结果证明了所提方法在某些数据分布情况下降低通信开销的有效性。
王爱冬,张涛,阳国贵:分布式数据流上的 Skyline计算 2008,44(1)153 于每个新到达的数据e,远程节点nol(i)需要判断 Dormino 满足过滤条件 则丢弃该数据 (O,e)是否成立。由于支配的判断可以通过逐个比较属性大小 不满足过 的方法来完成,因此处理每个新到点的额外计算开销为O(d) 滤条件过滤模块局部数 处理完全部N个节点需要的额外时间复杂度为O(dN)。对于 用户查询小集中节点c Node(1)据流 集中节点c来说,由于降低了数据规模,因此计算 Skyline的效 全局 Skin 计算模块|调整信息 率会有明显提高 满足过滤条件 则丢弃该数据 类似的, Distance算法需要在集中节点c和每个远程节点 node(i)增加存储开销以保存阈值T,因此存储开销为O(k+1); 不满足过过滤模块 滤条件 局部数 对于每个新到数据e,远程节点需要计算f(e)并比较其与T Node(h) 据流 的大小。由于比较操作可以在常数时间内完成,因此算法额 图2系统体系结构 外开销取决于距离函数的定义。假设f为欧氏距离,即fe)= (3)节点c根据已有数据流上的 Skyline算法跟踪最新的 Skyline集合,当Skyi集合发生变化时,计算虚拟数据点OV∑(x),则 Distance算法处理完全部N个节点需要的额 是否发生变化; 外时间复杂度为0(d+1)N)。而对于集中节点c来说,由于降 (4)若O发生变化,则将变化广播至所有node(i),更新本低了数据规模因此计算 Skyline的效率会有明显提高。 地O的属性。远程节点用新的虚拟数据点继续进行后续过滤 最后对算法在降低通信开销方面的有效性进行分析。网络 丢弃操作 通信开销的降低主要取决于两个因素:数据过滤丢弃的比例 定理3采用VMax算法,可以在集中节点c上得到正确和参数调整时额外通信开销。设数据平均丢弃率为p,处理 的 Skyline集合。 全部N个数据过程中参数调整次数为m,则两种算法实际通 证明对任意被丢弃的点e,由算法步骤2知, Dominate (O,e)成立。由支配定义知,i,O.x≤e.x都成立,且习j满足 信开销占无过滤丢弃时通信开销的百分比分别为:gh(p,m)= 0.xcx(1≤i≤d)。又由虚拟数据点O的定义知,对任意的(1-p)N·d+mkd×100%,gmp,m)(1-2)Nm:米 Skyline点p,px≤O,x,因此 Dominate(p,e),所以e不可能为 100% 全局 Skyline点。 4.2 Distance算法 5实验 假设函数f为一单调的距离函数(如欧氏距离)f(e)表示 数据点e与原点的距离。 Distance算法采用基于距离的过滤思 选择VC6.0实现了一个模拟仿真系统,在3台配置为 PⅣ2.8G、1G内存、 Windows xp的PC机上验证本文算法的 想,具体思路如下 (1)定义一个阈值距离T={max(f(p)SK(N)},为所有 有效性,其中一台作为集中节点,另两台作为远程节点。实验在 当前 Skyline点与原点距离的最大值。 广泛使用的三种遵循不同分布规律的模拟数据5.1上进行 (2)对node(i)监测到的新数据e,若fe)小于T则将e丢描述如下 弃,否则将e传递给集中节点c。 独立数据 indep:对象各属性值的大小相互独立。 (3)集中节点c根据已有数据流上的 Skyline算法跟踪最 正相关数据cor:若对象某属性值大(小),则其它属性值 新的 Skyline集合,当 Skyline集合发生变化时,计算T的值是也很可能大(小) 否发生变化; 反相关数据anti:若对象某属性值大(小),则其它属性值 (4)若T发生变化,则将变化广播至所有nmh()。远程节很可能小(大) 点用新的值继续后续过滤操作 三种分布数据的示意如图3所示, Skyline集合大小情况 类似的,对 Distance算法正确性进行证明。 如表1所示。实验过程中取N=100000,以数据流形式不断产 引理3对于两个数据点P1和p2,若 Dominate(p1,p2),则生数据,模拟以下三种场景:(1)直接将全部数据传递给集中节 fp1)<f(p2) 点ε;(2)选择Ⅴ_Max算法过滤丢弃;(3)选择 Distance算法过 证明已知 Dominate(p1,p2),由支配的定义,Vi,p1x≤p2x1滤丢弃。通过统计通信开销和系统处理完N个数据点的平均 都成立,且)满足p1s2x(1≤i≤d)因为f为单调的距离值信息并进行比较获得本文方法在降低网络开销.提高运算 函数,因此必有f(p1)<fp2)。 效率方面的有效性。 定理4采用 Distance算法,可以在集中节点c上得到正 ant 确的 Skyline集合。 证明引理1的逆否命题说明,若f(p1)≥f(p2),则Domi nae(p1,p2)一定不成立。由于T是当前所有 Skyline点与原点 距离的最大值,因此对被丢弃的点c和任意 Skyline点p,由算 法步骤2知,fe)>fp)成立。所以e不可能为全局 Skyline点。 (a)正相关数据(b)独立数据(c)反相关数据 43算法分析 图3实验所用三种数据分布示意 对ⅴ_Max算法来说,集中节点c和每个远程节点node(i) 实验结果如图4所示。可见,一般说来 Distance方法在降 需要增加存储开销以保存虚拟数据点O。由于属性个数为d,低通信开销方面的效果要优于νMax方法。同时可以看出,降 因此需要O(d(k+1))的额外开销,其中k为远程节点数目;对低通信开销的效果与数据分布关系非常紧密:正相关数据中的 1542008,44(1) Computer Engineering and Applications计算机工程与应用 -All 暑-All 1100000 1300000 AmAx 1200000 -distance -distance 81000000 1000000 900000 000 9800000 800000 600000 三500000 900000 400000 -vMax 8200004· -distance 800000 4 (a)正相关数据 (b)独立数据 (c)反相关数据 图4降低通信开销结果 表1实验数据集 Skyline集合平均大小 (8):1172-1181 d正相关数据独立数据反相关数据 [2] Cormo de G, Garofalakis M Sketching streams through the net: dis tributed approximate query tracking[ C]//Proceedings of the 31th 2345 447 VLDB Conference.Trondheim, Norway, 2005: 13-24 289 3 Borzsonyi S, Kossmann D, Stocker KThe skyline operator J/OL]: 38 964 17849 ICDE,2001:421-430 效果最好,独立数据中其次,而在反相关数据中几乎没有降低41mnk,EgP,OoiB. Efficient progressive skyline computation(C 通信开销,有时甚至增大了开销(图4(d)。这是因为反相关数 Proceedings of the 27th VLDB Conference. Roma, Italy, 2001: 301-310. 据情况下数据集的 Skyline点数目很多,而且数据分布的特性 5 Kossmann D, Ramsak F, Rost SShooting stars in the sky: an online algorithm for skyline queries(Cy/proceedings of the 28th VLDB Con- 决定了vMax和 Distance方法儿乎无法过滤数据,而每当 ference. Hong Kong, China, 2002: 275-286 Skyline集合发生变化引起过滤参数变化时,集中式节点还需 16 Papadias D, Tao Y, Fu G, et al. Progressive skyline computation in 要将这种变化广播到各个远程节点,从而导致额外的通信开销 database system[J.ACM Transactions on Database Systems, 2005, 30 大于过滤降低的通信开销,从而引起总的通信量变大。 (1):41-82 [7] Tao Y, Papadias D Maintaining sliding window skylines on data 结论 streams[J.IEEE Transactions on Knowledge and Data Engineerin 分布式环境中通信开销是一个非常重要的因素。考虑了分 206,18(3):377-391. 布式数据流上的连续 skyline计算问题,并提出了一个通用的SLmx,Yumy.Wagw, el al.Slabbing thie sky: ellicienl skyline 基于远程过滤的系统框架。通过两个简单的过滤模型验证了该 computation over sliding windows(J/OL].ICDE, 2005: 502-513 系统框架的有效性。 19 Balke W, Untzer U, Zheg J Efficient distributed skylining for V_Max和 Distance方法受数据分布影响比较大,在降低反 web information systems[C]International Conference on Extending Database Technology. Heraklion-Crete, Greece, 2004: 256-273 相关数据的通信开销方面效果很差。今后可以考虑更多高效的 [10 Wu P Parallelizing skyline queries for scalable distribution paral- 过滤模型算法,使其能够适应更多满足不同分布的数据。 lelizing skyline queries for scalable distribution[C]/International (收稿日期:2007年7月) Conference on Extending Database Technology. Munich, Germany 2006:112-130 参考文献: [11] Hose K Processing skyline queries in P2P systems [C)/LDB 「]金澈清,钱卫宁,周傲英流数据分析与管理综J.软件学报,2004,15 2005 Phd Workshop Trondheim, norway, 2005: 36-40 (上接150页) OFDM mobile communication systems based on pilot signals and [3 Rinne J, Renfors M Channel estimation in OFDM systems utilizing transform-domain processing[ C/Vehicular Technology Conference pilots [J]. Proc IEEE Nordic Signal Processing Symposium, 1996: IEE,1997,3:2089-2093 187-190 「8]吴伟凌,牛凯移动通信原理[M].北京:电子工业出版社,2005:259 [4 Li Ye, Seshadri N, Ariyavisitakul S Channel estimation for OFDM systems with transmitter diversity in mobile wireless channels[JI 19Coleri S, Ergen M, Puri A Channel estimation techniques based on IEEE J on Selected Areas in Communications, 1999, 17(3):461-471 ilot arrangement in OFDM systems[J. IEEE Transactions on Broad casting,2002,8(3):223-229 5 Jeon WG, Paik K H, Cho Y STwo-dimensional Mmse channel [10] Hoeher P, Kaiser S, Robertson P Two-dimensional pilot-symbol estimation for OFDM systems with transmitter diversity [Cp/The ided channel estimation by wiener filtering C/IEEE Interna- 54th IEEE Vehicular Technology Conference(VTC 2001), 2001: tional Conference on Acoustics, Speech and Signal Pr 1682-1685 Munich,1997:1845-1848 [6] Vineet S, Chin K H, Patrick H W ERobust MMSE channel esti- [11] Ekstrom M P Realizable Wiener filtering in two dimensions J] mation in OFDM systems with practical timing synchronization[C]/ IEEE Trans Acoust, Speech Signal Proc, 1982, ASSP-30(2): 31-40 IEEE, WCNC 2004, Atlanta, Georgia, USA, 2004: 711-716 12]周鹏,赵春明,杨宜进,等SFBC-OFDM系统中联合迭代信道估计 [7 Zhao Yuping, Huang Aiping. A novel channel estimation method for 与空频解码算法J通信学报,2007,28(2

...展开详情
试读 4P 论文研究-基于二维导频和降噪滤波的信道估计方法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744375 你的留言是对我莫大的支持
    2019-09-11
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于二维导频和降噪滤波的信道估计方法.pdf 9积分/C币 立即下载
    1/4
    论文研究-基于二维导频和降噪滤波的信道估计方法.pdf第1页
    论文研究-基于二维导频和降噪滤波的信道估计方法.pdf第2页

    试读已结束,剩余2页未读...

    9积分/C币 立即下载 >