Please wait a minute...
ISSN 1000-1239 CN 11-1777/TP

当期目录

2014年 第51卷 第3期    出版日期:2014-03-15
网络技术
基于短基线传感器网络的远场声源TDoA定位组合算法
崔逊学 卢松升 陈云飞 高浩珉 易 廷
2014, 51(3):  465-478. 
摘要 ( 596 )   HTML ( 1)   PDF (5147KB) ( 558 )  
相关文章 | 计量指标
针对远场声源定位问题,提出到达时间差(TDoA)定位的短基线传感器网络方案.通常有一类定位算法无需估计初始点,而另一类算法则依赖初始估计值,提出将这2类方法相结合,设计出几种组合定位算法.主要思想是扬长避短,由第1类定位算法实现粗定位和输出初始估计位置,将其作为初始点输入给定位精度高和依赖初始值的第2类算法.提出利用蒙特卡洛法和简化的几何配置案例,计算定位算法的概率误差圆,论证了这种性能评估准则的可行性.通过对组合算法的概率误差圆进行数值分析,得出球形插值法与最小二乘方程差法的有机组合具有最优性能的结论,并分析了这种组合算法的盒图特性.根据不同的距离和声程差标准偏差进行模拟,以及采用野外真实场景下获得的声源数据进行试验,验证了结论.
完全竞争均衡的频谱双向拍卖机制研究
黄 河, 孙玉娥, 陈志立, 徐宏力, 邢 凯, 陈国良,
2014, 51(3):  479-490. 
摘要 ( 525 )   HTML ( 1)   PDF (3093KB) ( 735 )  
相关文章 | 计量指标
频谱拍卖可以通过市场竞争的方式实现资源的优化配置,从而缓解日益严重的频谱资源危机,已经受到了广泛关注.但现有的频谱拍卖研究重点考虑了如何在一般物品拍卖的基础上实现频谱的空间复用,以提高利用率,却忽视了频谱拍卖市场规模过小,存在盲目报价等问题,极易导致最终成交价与频谱实际价值相偏离.为了解决该问题,提出了完全竞争均衡的频谱双向拍卖机制(ComDSA).该机制首先将参与者之间的多人博弈抽象为参与者与市场间的双人博弈,随后引入市场类型概率,采用海萨尼转换将其转换为完全信息博弈.最后,引入了连续竞价模型,通过参与者的多轮反复竞价,最终使成交价达到完全竞争均衡水平.理论分析与仿真实验结果表明,设计的拍卖机制在实现完全竞争均衡的基础上,有效提高了频谱的空间复用率和拍卖成交率.
基于区间Mamdani模糊推理的认知无线网络频谱迁移方案
王振东 王慧强 冯光升 吕宏武 陈晓明
2014, 51(3):  491-501. 
摘要 ( 578 )   HTML ( 2)   PDF (3491KB) ( 439 )  
相关文章 | 计量指标
机会式频谱接入技术虽能够有效提升认知无线网络频谱利用率,但在保障认知用户服务质量(quality of service, QoS)以及频谱资源有效利用率方面存在不足.为了提高认知用户QoS,提升认知无线网络系统性能,提出一种基于区间Mamdani模糊推理的认知无线网络频谱迁移方案.通过引入预判决方法减少不必要的数据量和系统开销.综合考虑待迁移频谱的频谱占用率以及链路维持率,并利用模糊推理计算出频谱迁移度,指导认知用户迁移至最优的频谱空穴.为了缩短模糊推理时长,提出区间Mamdani模糊推理方法.仿真结果表明,该方案能够降低认知用户业务传输的强制中断率、重传率以及频谱迁移次数,在维持较高系统吞吐量的同时,提高认知无线网络频谱资源的有效利用率.
CM-MAC:一种基于分簇的多信道车载网MAC协议
何 鹏, 阎保平, 李 志, 孙利民,
2014, 51(3):  502-510. 
摘要 ( 850 )   HTML ( 0)   PDF (2576KB) ( 741 )  
相关文章 | 计量指标
车载网VANET是一种应用于智能交通系统的新型无线移动自组织网络(mobile ad hoc network, MANET).随着车辆以及移动ad hoc网络技术的发展,车载网已经成为一个新兴的研究领域.针对VANET中车辆行驶的特征,提出一种拓扑相对稳定的车辆分簇算法.在此算法基础上,根据专用短程通信(dedicated short range communication, DSRC)标准中控制信道(control channel, CCH)和服务信道(service channel, SCH)的分配,考虑车辆间的无线通信干扰和不同应用的QoS需求,提出一种基于分簇的多信道混合型MAC协议,簇内通信采用非竞争的TDMA机制,簇间通信采用基于竞争的CSMA/CA机制,相邻簇采用不同的服务信道.模拟实验表明,提出的MAC协议在同时满足实时应用的延迟需求和非实时应用的吞吐量方面,优于现有协议.
面向工厂自动化无线网络的时间同步方法
杨雨沱, 梁 炜, 张晓玲, 刘 帅,
2014, 51(3):  511-518. 
摘要 ( 796 )   HTML ( 0)   PDF (1964KB) ( 640 )  
相关文章 | 计量指标
时间同步技术是保障工厂自动化无线网络高实时性与高可靠性的支撑技术.工厂自动化无线网络技术指标要求时间同步的精度成为同步方法的重心,在商用的IEEE 802.11硬件平台上,设计并实现了基于时分多址(time division multiple access, TDMA)机制并由时钟偏差测量、时钟偏差预测和时钟漂移补偿3部分算法组成的高精度时间同步方法.实验证明由于该同步算法相对于传统的双向同步算法加入了时钟偏差预测与补偿机制,使其有精度高、可靠性高、自适应性强等优势,有助于实现工厂自动化无线网络微秒级的TDMA时隙调度.
人工智能
大样本多源域与小目标域的跨领域快速分类学习
顾 鑫, 王士同,
2014, 51(3):  519-535. 
摘要 ( 684 )   HTML ( 1)   PDF (5338KB) ( 507 )  
相关文章 | 计量指标
传统的跨领域分类学习一般考虑均衡的单一源域到单一目标域的学习,但在现实世界中数据往往是不平衡的.当用于解决不平衡分类问题时,由于分类器的偏向性,其分类精度、抗噪性能往往有不同程度的下降.为了克服域间不平衡性,提出了一种不平衡多源跨领域分类算法(imbalance multisource classfication on cross-domain learning, IMCCL),该算法依据被众多实验证明有效的“逻辑回归模型”与“后验概率最大法则”构建多个训练域分类器并综合指导目标域的数据分类.为了充分高效利用大样本的源域数据,满足大样本的快速运算,在结合CDdual算法的基础上,提出了IMCCL的快速算法(IMCCL-CDdual).将其应用到文本数据分类与图像识别分类的实验结果表明:该算法具有较高的识别率、快速的识别速度和抗干扰性和领域自适应性.
动态贝叶斯网络的灵敏性分析研究
姚宏亮 张一鸣 李俊照 王 浩
2014, 51(3):  536-547. 
摘要 ( 717 )   HTML ( 0)   PDF (2539KB) ( 631 )  
相关文章 | 计量指标
灵敏性分析是研究复杂系统特性的一种重要方法.现有动态灵敏性分析方法都是针对特定类型的动态贝叶斯网络且计算复杂度高.为了对一般动态贝叶斯网络的灵敏性进行有效分析,提出了一种基于联合树的动态灵敏性分析算法(DSA_JT),DSA_JT算法构建动态网络的联合树,通过消息传播建立参数与目标结点的条件概率分布在时间上的函数关系;DSA_JT将联合概率分布分解成局部概率因式形式,通过降低计算幂次提升计算效率,但计算复杂度仍然偏高.为了更有效地提高动态贝叶斯网络灵敏性分析的计算性能,在DSA_JT算法的框架上提出了DSA_BK算法,DSA_BK算法在灵敏性函数计算过程中,用子系统的概率乘积近似整个系统的联合概率,通过对接口结点局部性的边缘化操作更新模型的联合概率分布,进一步降低了计算幂次,并论证了DSA_BK算法误差的有界性.进而,通过对这两种算法过程的抽象,分别给出了动态灵敏度函数计算公式的证明,表明2种算法可以有效处理一般动态贝叶斯网络的灵敏性分析问题.最后,在上证股票网络上的实验结果显示这2种算法的有效性.
一种用于连续动作空间的最小二乘行动者-评论家方法
朱 斐, 刘 全, 傅启明, 伏玉琛,
2014, 51(3):  548-558. 
摘要 ( 699 )   HTML ( 0)   PDF (2063KB) ( 505 )  
相关文章 | 计量指标
解决具有连续动作空间的问题是当前强化学习领域的一个研究热点和难点.在处理这类问题时,传统的强化学习算法通常利用先验信息对连续动作空间进行离散化处理,然后再求解最优策略.然而,在很多实际应用中,由于缺乏用于离散化处理的先验信息,算法效果会变差甚至算法失效.针对这类问题,提出了一种最小二乘行动者-评论家方法(least square actor-critic algorithm, LSAC),使用函数逼近器近似表示值函数及策略,利用最小二乘法在线动态求解近似值函数参数及近似策略参数,以近似值函数作为评论家指导近似策略参数的求解.将LSAC算法用于解决经典的具有连续动作空间的小车平衡杆问题和mountain car问题,并与Cacla(continuous actor-critic learning automaton)算法和eNAC(episodic natural actor-critic)算法进行比较.结果表明,LSAC算法能有效地解决连续动作空间问题,并具有较优的执行性能.
基于话题综合因子分析的语义社会网络社区发现算法
杨 静, 辛 宇, 谢志强,
2014, 51(3):  559-569. 
摘要 ( 613 )   HTML ( 1)   PDF (3752KB) ( 656 )  
相关文章 | 计量指标
针对一般社会网络社区发现算法仅考虑各节点的邻接关系,所划分的社区仅为一元关系社区,不能代表社区成员的语义相似性且无法处理具有多元语义话题的语义社会网络社区发现问题,提出基于话题因子分析的语义社会网络社区发现算法.该算法将节点的多元信息抽象为话题,先以多元话题综合因子作为节点话题信息度量,以节点间的话题密度差异作为节点聚合方向,构建初始社区结构;再以最大化社区内部话题信息相似度和最小化社区外部话题信息相似度为目标建立语义社区发现的目标函数及节点变动的代价函数;再以初始社区结构和代价函数作为初始解和判断准则,以节点变动的代价函数值为参数,建立全局优化的模拟退火策略优化语义社区结构,实现语义社会网络的语义社区发现;最后通过实验分析验证了算法的有效性.
D3L(ccy)的属性及分布式Tableaux推理算法的研究
赵晓非, 田东平, 张文波, 史忠植,
2014, 51(3):  570-579. 
摘要 ( 626 )   HTML ( 1)   PDF (1659KB) ( 446 )  
相关文章 | 计量指标
分步式动态描述逻辑(distributed dynamic description logics, D3L)很好地实现了在多个自治本体之间导入和重用知识的思想.在多个动态描述逻辑(dynamic description logics, DDL)本体之间桥规则构成链的情况下,知识并不总是按预期的方式正确传播.借鉴了基于包的描述逻辑(P-DL)的思想,引入了组合一致性语义对D3L进行了扩展从而很好地解决了上述问题.系统地研究了扩展得到的描述逻辑D3L(ccy)的属性及分布式推理理论.证明了该描述逻辑的单调性(D3L(ccy)是一种单调逻辑)、有向性(桥规则的影响具有方向性)及冲突局部性(局部本体的冲突不会传播到整个分布式系统);通过对原有Tableaux推理算法的扩展,为D3L(ccy)提出了分布式Tableaux推理算法并研究了算法的性质,证明了该算法是可终止的、可靠的和完备的.与传统的D3L相比,扩展后的D3L可以为信息集成系统、语义Web等分布式、动态的系统提供更为合理的逻辑基础.
基于动态迁移的ε约束生物地理学优化算法
毕晓君, 王 珏, 李 博, 李吉成,
2014, 51(3):  580-589. 
摘要 ( 466 )   HTML ( 0)   PDF (1260KB) ( 586 )  
相关文章 | 计量指标
提出基于动态迁移的ε约束生物地理学优化算法(εBBO-dm).首先,利用ε约束方法来处理约束条件,并根据群体约束违反度的优劣程度对水平参数ε进行自适应调整,充分利用较优不可行个体的有效信息,有效提高对可行域的搜索效率.其次,采用新的ε约束排序机制确定迁入率和迁出率,较好地平衡可行个体与不可行个体之间的关系.再次,为了增强迁移机制的搜索能力,提出新的动态迁移策略.最后,采用分段logistic混沌映射改进物种变异机制,提高了算法的收敛精度.通过对13个标准测试函数的仿真实验表明,εBBO-dm较其他算法在收敛精度和收敛速度上具有明显优势,尤其适合于复杂单目标约束优化问题的求解.
局部保持对支持向量机
花小朋, 丁世飞,
2014, 51(3):  590-597. 
摘要 ( 610 )   HTML ( 0)   PDF (1655KB) ( 639 )  
相关文章 | 计量指标
多面支持向量机(multiple surface support vector machine, MSSVM)分类方法作为传统支持向量机(support vector machine, SVM)的拓展在模式识别领域成为新的研究热点之一,然而已有的MSSVM方法并没有充分考虑到训练样本之间的局部几何结构以及所蕴含的判别信息.因此将保局投影(locality preserving projections, LPP)的基本思想引入到MSSVM中,提出局部保持对支持向量机(locality preserving twin support vector machine, LPTSVM).LPTSVM方法不但继承了MSSVM方法具有的异或(XOR)问题处理能力,而且充分考虑样本间的局部几何结构,体现样本间所蕴含的局部判别信息,从而在一定程度上提高了分类精度.主成分分析(principal component analysis, PCA)方法克服了LPTSVM奇异性问题,保证了LPTSVM方法的有效性.非线性情况下,通过经验核映射方法构造了非线性LPTSVM.在人造数据集和真实数据集上的测试表明LPTSVM方法具有较好的泛化性能.
最坏情况下X2SAT问题的上界
周俊萍 姜蕴晖 殷明浩
2014, 51(3):  598-605. 
摘要 ( 457 )   HTML ( 0)   PDF (696KB) ( 514 )  
相关文章 | 计量指标
最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O(1.4511n)提高到O(1.4203n),其中n为X2SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L,并从公式长度的角度证明了X2SAT问题在O(1.3643l)时间上界内可解.
软件技术
基于MapReduce模型的范围查询分析优化技术研究
赵 辉 杨树强 陈志坤 尹 洪 金松昌
2014, 51(3):  606-617. 
摘要 ( 530 )   HTML ( 0)   PDF (2944KB) ( 520 )  
相关文章 | 计量指标
近年来,MapReduce并行计算模型受到工业界和学术界广泛关注.基于该模型的系统实现已在谷歌、雅虎、Facebook等大公司内部成功应用.然而,基于MapReduce的系统实现最初用于解决海量无结构、半结构化数据的批处理问题,例如生成倒排索引、计算网页的pagerank、日志分析等,在设计上缺乏针对海量结构化数据进行交互式分析处理的优化考虑,例如:它总是采用全数据集强力扫描的数据处理模式,这有悖于结构化数据管理中常用的操作模式——选择性查询分析处理.针对该问题,引入传统数据库管理领域中常用的全局索引技术,将其应用在基于MapReduce模型的开源项目Hadoop上,以block为粒度对Hadoop分布式文件系统上的结构化数据构建全局索引结构,并给出一种面向范围查询分析的作业编译与调度执行优化算法,主要目标是基于应用语义及辅助索引结构减少不必要的map任务数,进而优化作业的调度开销和执行开销.在实验验证阶段,给出了80%,50%,30%,10%四种数据选择率在3种集群规模下的优化效果,发现作业响应时间最高可提升5倍,I/O开销最高提升10倍,任务调度开销最高提升11倍.
基于节点能力的Hadoop集群任务自适应调度方法
郑晓薇 项 明 张大为 刘青昆
2014, 51(3):  618-626. 
摘要 ( 614 )   HTML ( 0)   PDF (2067KB) ( 560 )  
相关文章 | 计量指标
针对当前Hadoop集群固有的任务级调度分配方法在运行中存在的负载分布不均的现象,着重对集群节点的执行能力进行了分析与研究.提出了一种基于节点能力的任务自适应调度分配方法.该方法根据节点历史和当前的负载状态,以节点性能、任务特征、节点失效率等作为节点任务量调度分配的依据,并使各节点能自适应地对运行的任务量进行调整.实验结果表明集群的总任务完成时间明显地缩减,各节点的负载更加均衡,节点资源的利用更为合理.
度量空间中的Top-k反向Skyline查询算法
张 彬, 蒋 涛, 高云君, 乐光学,
2014, 51(3):  627-636. 
摘要 ( 650 )   HTML ( 2)   PDF (2494KB) ( 495 )  
相关文章 | 计量指标
不同于传统的度量空间Skyline查询,提出了一种新颖的度量空间中的Skyline查询MkRS(metric top-k reverse skyline).MkRS从反向角度执行度量空间中的Skyline.给定查询对象q和单调参考函数f,MkRS返回k个包含m个数据对象的子集,以至于每个子集G的度量Skyline包含q.评估这种查询,需要执行从输入数据集P中n个数据对象里选择m个对象的穷举搜索以及每个排列子集的度量Skyline.这些计算由于巨大的搜索空间而需要极高成本.提出了基于排序机理的算法STS(sort and threshold skyline),它可以提前终止计算,仅需要检查很少部分的子集.然后,利用信息重用技术给出了基于重用的STS算法rSTS(reuse STS),进一步减少了STS中80%以上的I/O访问.大量的实验表明提出的算法有效、快速.
异构平台上性能自适应FFT框架
李 焱, 张云泉,
2014, 51(3):  637-649. 
摘要 ( 891 )   HTML ( 1)   PDF (5185KB) ( 607 )  
相关文章 | 计量指标
快速傅里叶变换(fast Fourier transform, FFT)在科学和工程界中具有着广泛的应用,尤其是在信号处理、图像处理以及求解偏微分方程领域.基于图形处理器(graphic processing unit, GPU)和加速处理器(accelerated processing unit, APU)的异构平台,提出了自适应性能优化的大规模并行FFT(massively parallel FFT, MPFFT)框架.MPFFT框架采用了安装时和运行时2层自适应策略.安装时借助代码产生器可以生成被GPU程序内核(kernel)调用的任意长度的代码模板库(codelet);运行时根据自动调优技术使代码产生器生成高度优化的GPU计算代码.实验结果表明:MPFFT在APU平台上,一维、二维以及三维FFT相对于AMD clAmdFft 1.6取得的平均加速比分别为3.45,15.20以及4.47,在AMD HD7970 GPU上平均加速比分别为1.75,3.01和1.69.在NVIDIA Tesla C2050 GPU上取得的整体性能都达到了CUFFT 4.1的93%,最大加速比能够达到1.28.
网络中心化仿真任务共同体服务选择算法研究
孙黎阳, 李 阳, 林剑柠, 毛少杰, 刘 中,
2014, 51(3):  650-660. 
摘要 ( 397 )   HTML ( 0)   PDF (3846KB) ( 542 )  
相关文章 | 计量指标
网络中心化仿真的核心问题是如何动态地把散布在网络上的各种服务进行整合,以形成新的、满足不同用户需求的仿真任务共同体.提出了一种仿真任务共同体服务选择算法(simulation task community service selection algorithm, STCSSA),其主要思想是将仿真任务共同体的构建转换成带QoS全局约束多目标优化的服务查找问题.首先介绍了仿真任务共同体服务QoS模型,并对任务共同体服务组合流程进行了评价;接着详细介绍了STCSSA运行流程,对算法的惯性权重动态变化策略进行了设计,并提出了一种可选的变异操作方法;最后将STCSSA与其他粒子群优化算法进行了对比测试,不仅从算法性能角度验证了STCSSA在提高收敛速度及避免局部最优方面具有优势,还从算法应用角度验证了STCSSA适用于大规模仿真下的网络中心化仿真任务共同体构建.
动态翻译系统中的间接转移关联软件预测算法
贾 宁 杨 春 佟 冬 王克义
2014, 51(3):  661-671. 
摘要 ( 419 )   HTML ( 0)   PDF (3522KB) ( 405 )  
相关文章 | 计量指标
动态翻译系统每执行一次间接转移指令均需进行一次地址转换,该过程是翻译系统性能开销的主要来源之一.无特殊硬件支持的翻译系统常采用软件预测法来降低地址转换开销,而软件预测法的预测准确率较低,制约其对翻译系统整体性能的提升.低开销关联软件预测算法(low-overhead correlated software prediction, LOCSP)可利用代码副本区分待预测指令的不同转移场景,将到达该指令的多条动态执行路径分离为多个互不重合的代码缓存副本,并为各个副本提供独立的预测链.从而在不增加动态指令数的前提下实现关联预测,显著提升软件预测的预测准确率.同时,LOCSP算法基于动态剖析的结果,仅对部分难预测的热点间接转移指令进行关联软件预测,进一步降低预测开销.实验表明,相比软件预测法,LOCSP算法可将平均预测准确率从58.9%提升至82.2%,将翻译系统的整体性能开销平均降低19.3%,最高降低41.9%,而平均静态代码数量仅增加2.4%.
基于数据对象规模的Rank级内存分配方法
钟 祺, 王 晶, 管雪涛, 黄 涛, 王克义,
2014, 51(3):  672-680. 
摘要 ( 413 )   HTML ( 1)   PDF (3470KB) ( 417 )  
相关文章 | 计量指标
利用主存的多bank/rank/channel结构挖掘访存并行性和局部性,是提高系统性能的重要手段.相关研究工作通过sub-rank技术增加可并行工作的存储资源,或在并行程序之间对bank划分,以隔离访存冲突.但上述方法没有考虑在bank/rank资源共存的情况下,单个程序内部数据对象间的冲突问题.通过观察数据在主存中的分布,发现程序的数据倾向聚簇于单个rank中,并提出了一种基于数据对象规模的rank级内存分配方法(data object scale aware rank-level memory allocation, DSRA).DSRA将冲突开销较大的数据对象分散到不同的rank,利用增长的bank/rank资源提高访存性能.DSRA工作在操作系统层,基于编译器和操作系统提供的信息来分析数据对象间的冲突开销,既不用修改源码,也不依赖特殊的底层硬件.基于2款真实处理器对来自NAS Benchmark和SPEC CPU2000中的存储敏感型基准测试程序进行评测.结果表明,在不影响cache失效率的情况下,DSRA通过减少主存访问周期数,可以降低程序的执行时间.与已有的优化技术相比,性能平均提高6.8%,最高性能提升幅度为16%.
基于Cache锁和直接缓存访问的网络处理优化方法
苏 文, 章隆兵, 高 翔, 苏孟豪,
2014, 51(3):  681-690. 
摘要 ( 791 )   HTML ( 0)   PDF (2736KB) ( 437 )  
相关文章 | 计量指标
通过分析计算机系统网络数据处理相关程序的访存行为、局部性特点和系统交互等问题,指出在高速网络环境下传统处理器网络子系统设计存在很大缺陷,并进一步提出一种基于软硬件协同设计的优化方案.该方案具体包括改进的直接缓存访问技术、关键程序的cache锁策略和相应系统互连结构及一致性协议等.实验表明,与传统方案相比,基于该方案的网络TCP传输带宽提高约48%,极限情况下UDP丢包率下降40%,传输延时降低超过10%.网络测试程序在与SPEC2000测试程序并发执行情况下,网络数据带宽提高约44%.此外还讨论了该优化方案与其他网络优化技术共同使用的基本原则和相应策略.