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

当期目录

2009年 第46卷 第5期    出版日期:2009-05-15
论文
求解无线传感器网络定位问题的线性规划算法
王珊珊, 殷建平, 张国敏, 蔡志平,
2009, 46(5):  705-712. 
摘要 ( 575 )   HTML ( 3)   PDF (1501KB) ( 784 )  
相关文章 | 计量指标
传感器节点的定位问题是无线传感器网络中的基础性问题之一.提出了一种线性规划算法用于求解无线传感器网络定位问题.该算法利用RSSI值和经验的无线信号传播模型推导出所有可通信节点间距离的相对关系,利用节点的通信半径估算出可通信节点间的距离,并以此为约束条件利用矩形近似圆形,将二次约束的规划问题转化为线性规划问题;求解该线性规划问题便可得未知节点坐标.通过仿真实验,证明了当锚节点分布在网络边缘时该算法能得到较好的定位效果,分析了锚节点分布、锚节点个数、网络连通度等实验参数对定位结果的影响.相比凸规划定位算法,该算法大大降低了求解规划问题的次数,且在相同的实验条件下定位误差更小.
一种实时可靠的移动无线传感器网络贪婪地理路由协议
张衡阳 樊玮虹 王 玲 周东翔
2009, 46(5):  713-722. 
摘要 ( 459 )   HTML ( 0)   PDF (2011KB) ( 544 )  
相关文章 | 计量指标
随着定位装置和定位算法的成熟,基于地理位置信息的贪婪地理路由协议受到广泛的关注与研究.但是,在移动无线传感器网络贪婪地理路由协议中,周期性信标交换条件下采用贪婪转发策略会引起通信暂盲现象,造成数据的丢失.基于右手法则的面遍历算法,对路由空洞的形状不能进行感知,数据转发具有很大的盲目性,转发路径有时比最优路径长很多,造成数据传输时延的增加.针对上述问题提出一种实时可靠的QoS贪婪地理路由协议,该协议通过自适应信标交换算法、基于过渡带思想的贪婪转发策略和基于路标迭代提取和剔除的自适应空洞处理算法,使得数据分组能够实时可靠地传输.NS-2仿真结果表明该协议在不增加控制开销的情况下,能够有效减缓通信暂盲现象,高效地处理路由空洞问题,大大提高协议的实时性和可靠性,可应用于对实时性和可靠性有一定要求的大规模移动无线传感网络.
BPEC:无线传感器网络中一种能量感知的分布式分簇算法
周新莲, 吴 敏, 徐建波,
2009, 46(5):  723-730. 
摘要 ( 701 )   HTML ( 0)   PDF (999KB) ( 583 )  
相关文章 | 计量指标
无线传感器网络的大面积铺设以及数据融合的需求,促使必须有效地组织网络的拓扑结构,以达到均衡负载、延长网络的生命周期的目标.分簇已被证实是将网络组织成层次相连结构的有效方式.提出了一种新的以邻居节点的平均剩余能量与节点本身的剩余能量的比值作为竞争簇头的主要参数,以节点的“度”作为节点竞争簇头辅助参数的节能分布式分簇算法BPEC.如果执行BPEC算法,整个网络的广播消息量复杂度为O(n),整个网络的时间复杂度为O(1).证明了由BPEC算法产生的簇头集合是一个最大独立集,簇头集合能覆盖网络的所有节点.当节点足够多时,仿真实验结果表明,簇头集合的尺寸大小与理论推导值十分接近.
基于复杂系统理论的域间路由系统演化模型CMV-HOT
赵金晶, 黄敏桓, 朱培栋,
2009, 46(5):  731-737. 
摘要 ( 394 )   HTML ( 2)   PDF (819KB) ( 543 )  
相关文章 | 计量指标
对域间路由系统的基本问题能否找到有效而又彻底的解决方法,在很大程度上取决于对域间路由系统行为模型的准确刻画.随着Internet网络规模的扩展和应用的多样化,域间路由系统体现出复杂巨系统的特征.从复杂系统理论出发,研究了Internet域间路由系统中各个自治系统在其成长消亡过程中需要考虑的各种影响因素,基于HOT理论建立了域间路由系统的动态演化模型——CMV-HOT模型.CMV-HOT模型将自治系统分为核心层AS、传输层AS以及边缘层AS三类,通过对域间路由系统的内部规律和外在表现的分析,从复杂系统的角度对域间路由系统的演化过程进行模拟.通过与真实BGP路由表数据的比较,CMV-HOT模型在节点度分布、网络的平均路径长度以及聚集系数等关键参数上有很好的一致性.因此模型能同时满足幂率特性和小世界特性,在网络研究中具有极高的准确性和实用价值.
多跳无线与有线混合网络中TCP性能改进研究综述
颜国风 王建新
2009, 46(5):  738-746. 
摘要 ( 442 )   HTML ( 2)   PDF (854KB) ( 526 )  
相关文章 | 计量指标
多跳无线与有线混合网络中,数据流通过的传输媒体各不相同,这些差异会严重影响TCP性能.为了提高有线与无线混合网络中TCP协议的性能,研究者对混合网络TCP协议进行了大量的研究,主要是通过修改标准TCP协议,使之适合于混合网络环境,设计方法主要有分层设计与跨层设计两种.分析了多跳无线与有线混合网络的特点;探讨了多跳无线与有线混合网络中影响TCP性能的主要因素、TCP所要解决的主要问题,以及改进TCP性能面临的难点;对当前改进混合网络中TCP效率、公平性等方面的研究成果进行了分析和总结,并指出了多跳无线与有线混合网络中TCP进一步研究的重点.
面向指令Cache周期预取的代码排布方法
扈 啸 陈书明
2009, 46(5):  747-755. 
摘要 ( 652 )   HTML ( 0)   PDF (1076KB) ( 497 )  
相关文章 | 计量指标
在含Cache的处理器中,代码排布和指令预取是减少取指延迟的常用技术.代码排布侧重研究代码执行的空间相对位置,指令预取则关注于代码执行的时间相对关系.片上Trace技术非入侵地获得程序的执行路径及时间信息,将代码执行的时空关系联系起来,因此为排布技术和预取技术的结合使用提供了基础.基于YHFT-DSP平台,利用程序运行的周期行为特性设置预取,利用VLIW结构处理器的空闲单元执行预取指令,提出以增加预取容限为目标的函数级代码排布方法.实验结果表明,该方法能有效预取并减少指令Cache失效.
一种面向大规模副本存储系统的可靠性模型
穆 飞 薛 巍 舒继武 郑纬民
2009, 46(5):  756-761. 
摘要 ( 379 )   HTML ( 1)   PDF (665KB) ( 543 )  
相关文章 | 计量指标
可靠性对大规模存储系统至关重要,在大规模存储系统中设备失效日趋频繁,副本技术成为提高系统可靠性的主流技术之一.基于Markov模型,针对多副本存储系统建立了度量系统可靠性的理论模型.该模型能够反应失效检测延迟对系统可靠性的影响.通过该模型还可以度量存储系统关键参数如系统规模、副本阶数、单节点容量、单节点平均失效时间、数据对象平均大小、平均修复带宽等对系统可靠性的影响,从而为存储系统的设计提供理论基础.
一种改进的块级连续数据保护机制
李 旭, 谢长生, 杨 靖, 曹 强, 魏沁祺,
2009, 46(5):  762-769. 
摘要 ( 511 )   HTML ( 3)   PDF (1181KB) ( 546 )  
相关文章 | 计量指标
随着存储技术的快速发展,连续数据保护 (CDP) 功能已成为现代存储系统重要的数据保护和恢复手段.根据当前不同CDP实现机制的优缺点,提出了一种基于TRAP-4的改进机制——ST-CDP.在保留TRAP-4原有数据记录方式的基础上,按一定间隔值d在恢复链条中插入对应时间点的快照数据,有效地解决了TRAP-4的链条易失效和恢复时间过长问题.借助量化分析模型分析了该机制的性能并确定最优的d值.原型系统在Linux内核块设备层的RAID5上实现了该机制,并通过实验对3种不同CDP机制进行对比测试.实验结果表明ST-CDP既具有与TRAP-4类似比快照机制存储开销低、系统性能影响小的优点,还具有比TRAP-4更快的恢复效率及更高的可靠性.因此ST-CDP是一种高效并且恢复成本较低的连续数据保护机制.
RQIC: 一种高效时序相似搜索算法
蒋 涛 冯玉才 朱 虹 李国徽
2009, 46(5):  770-778. 
摘要 ( 3139 )   HTML ( 0)   PDF (1284KB) ( 507 )  
相关文章 | 计量指标
索引大规模时序数据库是高效时序搜索中的关键问题.提出了一种新颖的索引方案RQI, 它包括3种过滤策略: 即first-k过滤、索引低边界和上边界以及三角不等式修剪.基本的思想为首先运用Haar小波变换计算每个时序的小波系数,利用前面的k个小波系数形成一个最小边界矩阵,以利用点过滤方法; 然后将预先计算每个时序的低边界特征和上边界特征存放到索引当中; 最后采用三角不等式来修剪不相似的序列并确保没有漏报.同时提出了一种新的低边界距离函数SLBS和聚类算法CSA.通过CSA可保持索引良好的聚类特征以提高点过滤方法的效率,从而引入了一种更好的算法RQIC.在合成数据集和实时数据集的大量对比实验表明,RQIC是有效的且具备较高的查询效率.
CBC-DS: 基于频繁闭模式的数据流分类算法
敖富江, 王 涛, 刘宝宏, 黄柯棣,
2009, 46(5):  779-786. 
摘要 ( 516 )   HTML ( 0)   PDF (901KB) ( 580 )  
相关文章 | 计量指标
基于关联规则的分类算法通常根据频繁模式生成类关联规则,但频繁模式挖掘易遭受组合爆炸问题,影响算法效率.并且数据流的出现也对分类算法提出了新的挑战.相对于频繁模式,频繁闭模式的数目较少,挖掘频繁闭模式的算法通常具有较高的效率.为此,提出了一种高效的基于频繁闭模式的数据流分类算法—CBC-DS.主要贡献在于:1)提出了一种基于逆文法顺序FP-Tree的频繁闭项集单遍挖掘过程,用于挖掘类关联规则,该过程采用了一种混合项顺序搜索策略以满足数据流挖掘的单遍性需求,并采用位图技术提高效率;2)提出了“自支持度”概念,用于筛选规则以提高算法分类精度.实验表明,位图技术能够提高算法速度2倍以上,利用自支持度能够提高算法平均精度0.5%左右;最终CBC-DS算法的平均分类精度比经典算法CMAR高1%左右,并且CBC-DS算法的规则挖掘速度远快于CMAR算法.
小数据集贝叶斯网络多父节点参数的修复
王双成, 冷翠平, 曹 锋,
2009, 46(5):  787-793. 
摘要 ( 649 )   HTML ( 0)   PDF (652KB) ( 508 )  
相关文章 | 计量指标
具有已知结构的小数据集贝叶斯网络多父节点参数学习是一个重要而困难的研究课题,由于信息不充分,使得无法直接对多父节点参数进行有效的估计,如何修复这些参数便是问题的核心.针对问题提出了一种有效的小数据集多父节点参数修复方法,该方法首先使用Bootstrap抽样扩展小数据集,然后分别将Gibbs抽样与最大似然树和贝叶斯网络相结合,通过依次对扩展数据按一定比例的迭代修正来实现对多父节点参数的修复.实验结果表明,这种方法能够有效地使大部分多父节点参数得到修复.
微阵列数据癌症分类问题中的基因选择
张丽娟, 李舟军,
2009, 46(5):  794-802. 
摘要 ( 468 )   HTML ( 3)   PDF (833KB) ( 603 )  
相关文章 | 计量指标
微阵列数据广泛而成功地应用于生物医学的癌症分类研究.一个典型的微阵列数据集包含大量(通常成千上万,甚至数十万)的基因、相对少量(往往不足一百)的样本.在这成千上万的基因中,仅仅一少部分基因对癌症分类有贡献.因而,对于癌症分类来说,最重要的一个问题就是识别出对癌症分类最有贡献的基因.这一识别过程称为基因选择.基因选择在统计模式识别、机器学习和数据挖掘领域已得到广泛研究.介绍基因选择问题所涉及到的相关背景知识和基本概念;全面地回顾统计学、机器学习和数据挖掘领域对基因选择问题的解决方法;通过实验展示了几种典型算法在微阵列数据上的性能;指出当前存在的问题和未来的研究方向.
一种基于最小生成树的多目标进化算法
李密青 郑金华 罗 彪
2009, 46(5):  803-813. 
摘要 ( 532 )   HTML ( 2)   PDF (1767KB) ( 607 )  
相关文章 | 计量指标
怎样保证朝Pareto最优解的方向搜索和如何获得均匀分布且范围广泛的非支配解是多目标进化算法(MOEA)设计时的两个关键问题,它们很大程度上取决于适应度赋值和外部种群维护这两个重要部分.提出了一种基于最小生成树的多目标进化算法(MST_MOEA).在考虑了个体间支配关系的基础上,利用个体与非支配集的距离和不同等级个体的树聚集密度来对适应度赋值;在外部种群的非支配解个数超过规定的种群规模时,用树的度数和树聚集密度对其进行修剪.将其应用于不同维数下9个测试函数,并与NSGA-II,SPEA2进行对比,结果证实了算法良好的收敛性和分布性.
改进模糊划分的FCM聚类算法的一般化研究
朱 林, 王士同, 邓赵红,
2009, 46(5):  814-822. 
摘要 ( 688 )   HTML ( 0)   PDF (936KB) ( 603 )  
相关文章 | 计量指标
聚类分析是无监督模式识别中的一种重要方法,已广泛应用于数据挖掘、图像处理、计算机视觉、生物信息和文本分析中.在聚类算法中,模糊指数m对聚类结果有十分重要的影响.针对IFP-FCM算法模糊指数m被限定为2的问题,提出了一般化的改进模糊划分的FCM聚类算法GIFP-FCM.通过引入新的隶属度约束,解决了IFP-FCM算法模糊指数m的一般化问题;同时GIFP-FCM算法从Voronoi距离和竞争学习的角度对其鲁棒性和快速收敛性进行了合理解释;其次,通过引入模糊程度系数α,使得FCM算法和IFP-FCM算法分别表示为GIFP-FCM算法在α等于0和α趋于1时的特例.实验结果表明,GIFP-FCM算法较之于IFP-FCM和FCM算法具有更好的鲁棒性和参数适应性;在纹理图像分割中,GIFP-FCM也明显优于IFP-FCM和FCM算法.
基于Vague集的含洞不规则Vague区域关系
李 松, 郝忠孝,
2009, 46(5):  823-831. 
摘要 ( 434 )   HTML ( 0)   PDF (562KB) ( 523 )  
相关文章 | 计量指标
模糊区域的空间信息表示和区域关系处理在空间数据库、地理信息系统和人工智能等领域具有重要的意义.引入Vague集的概念和理论对含洞不规则Vague区域关系进行了系统的研究.基于Vague集给出了Vague区域、Vague洞和原子域等概念;将含洞不规则Vague区域分成原子域,研究了原子域间的空间关系;联合原子域关系,给出了含洞不规则Vague区域关系.研究成果可较好地处理含洞不规则Vague区域内的模糊点不确定的隶属信息和复杂的含洞不规则Vague区域的空间关系的表示和分析等问题.
基于价格进程代数的Web服务组合描述和成本分析
肖芳雄 黄志球 曹子宁 袁 敏 张君华
2009, 46(5):  832-840. 
摘要 ( 585 )   HTML ( 0)   PDF (938KB) ( 543 )  
相关文章 | 计量指标
进程代数可有效地用于Web服务组合的描述和验证,然而缺乏对服务组合成本建模和分析的能力.提出一种扩展了价格信息的进程代数PPA, 在CCS基础上为进程动作和状态扩展价格函数, 给进程动作的执行标记价格,给进程的迁移状态标记成本.给出了PPA的语法和语义,定义了PPA成本弱互模拟并分析了其与CCS弱互模拟的关系,证明了PPA在CCS基础上扩展了成本建模能力,给出了成本状态空间构造算法,该算法支持选择成本优化的组合服务.实验分析了PPA用于Web服务组合成本建模和分析的可行性.
一种基于不确定性因素叠加的Web服务质量度量方法
岳 昆, 刘惟一, 王晓玲, 李 劲,
2009, 46(5):  841-849. 
摘要 ( 450 )   HTML ( 0)   PDF (829KB) ( 482 )  
相关文章 | 计量指标
以克服现有服务质量度量方法的主观性、反映服务调用中存在的不确定性和各影响因素之间存在的内在关系为出发点,定义了原子服务调用率、成功率和效率3个因素,通过对原子服务调用的历史信息进行统计计算得到各因素的量值,提出一种基于不确定性因素叠加的原子服务质量度量方法,以及基于各原子服务质量平均值的高粒度Web服务的质量度量标准,并给出服务优先级的判断方法.性能分析验证了所提出方法的高效性、可扩展性和可行性.
基于模糊提取的远程双向生物认证
张 凡 冯登国
2009, 46(5):  850-856. 
摘要 ( 519 )   HTML ( 1)   PDF (705KB) ( 550 )  
相关文章 | 计量指标
传统的远程生物认证采用安全信道或者生物认证过程本地化的方法,具有较多的局限性.模糊提取可从生物特征输入中以容错的方式可靠地提取出均匀分布的随机密钥,当输入发生变化且变化很小时,该密钥保持不变.基于这一重要工具,给出了一个零存储的非安全信道双向生物认证方案.该方案无需存储和传输用户的生物特征,有效保护了用户隐私,并能够抵抗假冒攻击和多服务器合谋攻击.此外,所给方案还具有良好的可扩展性,集成口令和智能卡可产生多因素认证方案,并支持用户注册更新.
基于身份的高效签密密钥封装方案
赖 欣, 黄晓芳, 何大可,
2009, 46(5):  857-863. 
摘要 ( 714 )   HTML ( 0)   PDF (701KB) ( 498 )  
相关文章 | 计量指标
KEM-DEM 结构的混合密码体制是获得IND-CCA安全最实际有效的方法,传统的KEM由公钥加密方案实现,仅提供DEM使用的会话密钥的保密性安全.2005年Alexander等人将签密的概念与KEM-DEM结构的混合密码体制相结合,提出了Signcryption KEM-DEM结构的混合签密.其中Signcryption KEM是利用发送者私钥和接收者公钥共同生成会话密钥及其密钥封装.该方法可以使密钥封装同时具有保密安全性和不可伪造安全性.在基于身份密码体制上扩展了签密密钥封装的定义,结合Sakai-Kasahara私钥提取结构以及椭圆曲线上相关的困难问题给出了一个基于身份的签密密钥封装的实例方案,并在随机预言机模型下对该实例方案的安全性进行了证明.该方案具有ID-IND-CCA保密性安全和ID-UF-CMA不可伪造性安全.提出的实例方案在会话密钥封装阶段不需要进行对计算以及映射到点的Hash函数计算.通过有效的对优化计算和点压缩技术,本实例方案在具有高安全性的同时也具有执行性能上的优势.
使用基于多例学习的启发式SVM算法的图像自动标注
路 晶 马少平
2009, 46(5):  864-871. 
摘要 ( 748 )   HTML ( 1)   PDF (926KB) ( 601 )  
相关文章 | 计量指标
在基于内容的图像检索中,按照图像的语义内容进行自动标注是一个具有挑战性的难题.将解释语义内容的关键词当做图像类别标签可使自动标注问题转化为图像分类问题.对于多数训练数据,关键词仅仅是针对整幅图像来标注的,并不是针对图像中的具体区域.为了克服这个问题,提出了多例学习(MIL)框架下基于支持向量机(SVM)的启发式算法HSVM-MIL.使用迭代的启发式最优化算法来解决多例学习中复杂的整型规划问题,以使分类风险最小化.每次迭代试图改变一个样例的类别以最大化普通SVM的分类间隔.在图像数据库和多例学习的经典数据集MUSK上的实验表明,HSVM-MIL算法具有优良的分类性能.由于该算法针对个体样例的正负分类进行判断,因而能够确定图像区域与关键词之间的对应关系,克服了大多数多例学习算法的缺点.
一种基于MAP的超分辨率图像重建的快速算法
肖创柏, 禹 晶, 薛 毅,
2009, 46(5):  872-880. 
摘要 ( 666 )   HTML ( 1)   PDF (1269KB) ( 566 )  
相关文章 | 计量指标
超分辨率图像重建技术就是通过融合多幅变形、模糊、有噪、频谱混叠的低分辨率降质图像(或视频序列)来重建一幅高质量高分辨率图像.MAP估计算法是一种广泛使用的统计重建方法.针对标准MAP估计算法运算量大的问题提出了两点改进.第1点是当计算梯度时直接计算目标函数的增量,避免了函数值的冗余计算;第2点是采用非精确一维搜索确定步长,避免了运算量庞大的海塞矩阵的计算.实验结果表明,提出的改进在保持重建效果基本不变的前提下,在很大程度上提高了MAP超分辨率图像重建方法的速率,与此同时保证了算法的收敛性.
AVS熵编码器的VLSI设计
徐 龙, 邓 磊, 彭小明, 季向阳, 高 文,
2009, 46(5):  881-888. 
摘要 ( 494 )   HTML ( 1)   PDF (834KB) ( 452 )  
相关文章 | 计量指标
针对AVS实时高清编码器的设计要求,提出了一种高效的AVS熵编码器的VLSI设计方案.首先,基于硬件的流水线操作和计算的并行性,修改原有的针对软件设计的串行算法为具有一定并行度的并行算法;其次,考虑硬件实现的代价,简化了熵编码器在模式决策阶段预编码的VLSI设计,因为预编码只计算编码系数所用比特数,而无需知道编码码字;而且,对于简化的预编码,熵编码所涉及的查表运算都可以改为只使用逻辑判断来实现,大大节约了硬件的存储空间;同时,数据流使用8像素并行的流水线设计,每个时钟处理8个系数,更进一步提高了硬件处理速度.AVS熵编码器包括Zig-Zag扫描得到每个系数的Run和Level,查询当前码表得到每个(Run,Level)的CodeNumber和得到每个CodeNumber的比特串,此流程与其他编码器的VLC类似,所以该VLSI设计同样适用于其他编码器,如H.264/AVC和MPEG2/4.软件测试和RTL仿真的结果都符合AVS编码标准和满足硬件加速的要求.