二进神经网络（共7篇）
二进神经网络 篇1
0 引言
网络编码的概念于2000年首次提出[1],它能显著提高无线组播/广播网的吞吐量和传输效率[2,3,4]。然而,S.EL ROUAYHEB等已经证明,要达到网络编码的最优和k近似容量是一个NP-hard问题[5,6]。因此,人们提出了几种启发式的方法来将网络编码应用到无线网络的数据包重传中,以提高传输效率。DONG NGUYEN和Tran等提出了机会式网络编码重传(ONCR)方案[7,8],另一种方案是是随机网络编码重传(RNCR)或全网络编码重传(FNCR)[9,10]。KUMAR S J等提出了一种新的ONCR方案[11],它使用自由度而不是原始数据包来表示接收机的状态信息。FRAGOULI C等证明了在广播系统中使用网络编码能在能量效率上获得很大的收益[12]。LU等提出在无线网络的视频广播中使用基于网络编码的HARQ算法[13]。WU等提出了CoRET方案[14],肖潇等给出了NCWBR方案[15,16]。WANG等提出了一种基于图论的最大团算法来选择编码包,使传输次数极大趋近于理论值[17]。
以上方法极大提高了无线广播重传的传输性能,但很难同时达到高效传输及低复杂度计算。本文以减小传输次数,同时兼顾计算复杂度为目标,提出了一种新WBRBNC方案,并对这一方案进行了分析和仿真评估,验证了方案的有效性。
1 网络模型
考虑一种通用的无线广播模型,它能广泛应用于无线Mesh网络,无线传感器网络和卫星广播网等系统中。该模型包含一个发送节点S和N个接收机节点{R1,R2,…,RN},如图1所示。在传统的重传方法中,发送节点只是简单地对丢包逐个进行重传。将二进制网络编码应用到广播重传中以后,发送机就不仅仅是简单地重传原始数据包,而是先对多个原始数据包进行二进制编码,也就是XOR编码,然后再进行广播重传。那么,这种广播重传过程分为2个阶段:原始数据包传输的初始阶段和基于二进制网络编码的重传阶段。在初始阶段,发送节点发送M个原始数据{P1,P2,…,PM}包给N个接受节点,接收机接收到原始数据包后,将每个包的状态信息(成功接收或丢失)反馈给发送节点S。在重传阶段,发送节点S根据状态信息选择丢包进行XOR编码,再将编码包广播重传给各接收机节点。当某个接收机接收到该编码包,它就有可能使用XOR解码方法从该编码包中解出一个原始丢包,然后该接收机将新的状态信息反馈给发送机。这一重传过程将持续到所有接收机都正确接收到所有的原始数据包。
对基于二进制网络编码的组播和广播重传问题,如何选取进行二进制编码的原始数据包依赖于每个接收机的数据包状态信息。将这种状态信息用数据包分布矩阵(Packet Distribution Matrix,PDM)表示,它将每个接收机拥有或丢失数据包的情况表示在矩阵中,每行表示对应接收机存储器中所有原始数据包的状态,而每列表示对应数据包在所有接收机中的状态,其行系数和列系数分布表示接收机和原始数据包。PDM是一个(0,1)矩阵,也就是一个二进制矩阵,其元素为0或者1。如果元素值为1,表示相应的接收机丢失了对应的数据包;如果元素值为0,表示相应的接收机已成功接收对应的数据包。表1给出了一个含有6个接收机节点和8个数据包的PDM示例。为了更新PDM,在每次传输以后,每个接收机都将其ID和各数据包的状态信息反馈给发送机节点。在后面的仿真中,为了评估的方便,假设发送机到所有接收机的数据包错误概率(Packet Error Ratio,PER)相同。
选择不同的原始数据包进行编码形成不同的编码包,可以使不同数目的接收机在一次重传中受益,有的选择能在一次编码包重传后使更多的接收机受益。如果每次重传的编码包都能使更多的接收机受益,显然重传的次数会更少,带宽效率就会更高。因此,所描述问题的核心就是如何选择原始数据包进行编码,使每次重传都能让最多的接收机受益。
2 WBRBNC方案
WBRBNC方案的基本思想是直接通过PDM选取编码原始数据包,这种方法更加直观,效率也更高。直观地看,当选取一个数据包或多个数据包编码后进行重传,其最大可能收益就是PDM矩阵中相应这些数据包的列相加后形成的矢量中‘1’的个数。例如,给定数据包分布矩阵如表1所示,选择P1、P2、P3形成编码包P1⊕P2⊕P3,那么相应的PDM的第1、 2、3列的矢量和为(0,0,1,1,1,1)T,其最大可能受益为4。也就是说,如果所有接收机都成功接收到编码包,接收机R3、R4、R5和R6就能够分别从这次重传中译出一个它们丢失的原始数据包。
基于上述观察,将WBRBNC方案的实施分5个阶段:开始、初始化、编码包选取、重传和结束。第3个阶段包括一个数据包选取算法,各阶段描述如下。
开始:即初始传输阶段,发送机将所有的原始数据包广播给所有的接收机。
初始化:在开始阶段之后,或是在某次重传之后,发送节点首先通过无线信道从每个接收节点接收相应的数据包分布矢量(PDVs),PDV是一个1×M矢量,由各接收机根据各自存储器中接收或译出的原始数据包状态生成,其表示方法与PDM一样。发送节点根据接收到的PDVs生成PDM。在开始阶段之前,PDM是一个全‘0’矩阵,在重传过程中是一个(0,1)矩阵,并且PDM在每次传输之后都要进行更新。
选取:在初始化过程之后,发送机开始选取编码数据包,选取过程由一个数码包调度算法具体实现。
数据包调度算法如算法1所示,该算法分为3个步骤:
步骤1:找出PDM所有列中‘1’的数目最多的列,将该列记作矢量Vmax,该列中‘1’的数目记作max,并将该列的系数加入到空的数组S中。
步骤2:选取2个数据包,使这2个数据包对应于PDM中的两列相加以后形成的矢量和中‘1’的数目最多。如果该矢量和中‘1’数目超过max,则用该矢量和更新Vmax,用该矢量和中‘1’的数目更新max,并用这2个数据包的系数更新数组S。
步骤3:从余下的数据包中挑选一个,使其对应于PDM中的列与Vmax矢量相加后得到的新的矢量和中‘1’的数目最多,如果该数目大于max,则用该矢量和更新Vmax,并将这个包的系数加入到数组S中。然后重复步骤3,直到Vmax中‘1’的数目为N或者不再增加为止。
重传:根据选取过程中存储在数组S中的列系数,发送机将选取的数据包使用XOR操作进行编码再广播发送给所有接收机。然后,根据各接收机反馈的状态信息生成新的PDM矩阵,如果PDM矩阵不是全0矩阵,则从初始化步骤开始新一轮的选取、编码和重传操作。
结束:当所有接收机获取所有它们需要的数据包后,整个传输过程就完成了。如果发送机有更多信息需要广播,那么系统将从开始步骤继续执行整个广播过程。
3 仿真结果
为了验证WBRBNC方案的效能,对其性能进行了仿真。首先为每个接收接预先设置相同的数据包错误概率PER,以便于观察评估指标在不同数据包数目M,接收机数目N和数据包错误概率PER条件下的变化趋势。仿真了在不同条件下WBRBNC方案的平均传输次数,并同其他3种方案和理论值进行比较。然后,对计算复杂度进行了仿真比较。
3.1 平均传输次数
图2(a)给出了各方案的平均传输次数随数据包数据变化比较的情况,仿真设置参数为N=10,p=0.3,M从10～100变化。从仿真结果可以看出,WBRBNC和最大团方案的平均传输次数远小于未编码方案,而NCWBR方案性能则介于两者之间。随着数据包数目的增加,未编码方案和NCWBR方案的平均传输次数几乎不变,而WBRBNC和最大团方案则随着数据包数目的增加而逐步减少,并越来越趋近于理论值,这是因为数据包越多,编码机会就越多。各方案平均传输次数同接收机数目变化比较的情况如图2(b)所示,仿真设置参数为M=100,p=0.3,N从6～16变化。
同样,WBRBNC方案和最大团方案的性能要远好于未编码和NCWBR方案,4个方案的平均传输次数均随接收机数目的增加而增大,这是因为接收机数目越多,平均到每个数据包的丢包率就越大,丢的包就越多,从而需要进行更多的重传。
WBRBNC方案和最大团方案的平均传输次数随接收机数目的增加而增大,但其增大幅度很小,未编码方案增加较多但曲线斜率逐步减小,而NCWBR方案则是线性增大,当接收机数目超过18时其性能反而不如未编码情况,这是由于NCWBR在选取数据包时未对可解性进行判断,从而导致很多的无效重传。
3.2 计算复杂度
对WBRBNC、NCWBR和最大团3种方案的计算开销进行了仿真验证。图3给出了3种方案计算开销随数据包数目变化比较的曲线,仿真参数设置如图3所示。从仿真曲线可以看出,3种方案的计算开销均随数据包数目的增多而增大,但最大团方案的计算时间远大于WBRBNC和NCWBR方案,随着数据包数目的增加其比值甚至超过100倍。最大团方案的时间效率太低,因此在数据包很多的情况下使用最大团方案是不可取的。另一方面,NCWBR方案的计算开销又小于WBRBNC方案,但即使在M=100时,WBRBNC方案的计算开销仍然保持在0.4 s以下。
3种方案在不同接收机数目情况下计算开销的仿真曲线如图4所示。最大团方案基本趋势同图4很相似,计算时间随着接收机数目的增多而急剧增大,在接收机数目为16时达到150 s,至少比WBRBNC和NCWBR方案长50～150倍。而WBRBNC和NCWBR方案则是线性增加,且曲线斜率不大,这是一种很理想的情况。从计算开销的角度来看,这2种方案更适合于节点多、规模大的网络。
4 结束语
对基于二进制网络编码的无线广播重传性能进行了分析,提出了使用数据包分布矩阵进行编码数据包调度的方案WBRBNC。WBRBNC方案能有效解决传输调度问题,仿真结果表明,该方案使基于二进制网络编码的无线广播重传性能得到很大提升,且其计算复杂度也很低,是一种有效的广播重传方法,能广泛应用到卫星广播网、无线传感器网和未来的行星际互联网等系统中,具有很高的应用价值。
摘要：为了提高无线广播网络中数据包的传输效率,提出了一种新的基于二进制网络编码的高效无线广播重传方法(WBRBNC)。法基于数据包分布矩阵(PDM),在广播重传过程中使用一种新的数据包算法选取编码包,对这些丢包采用二进制网络编码方法进行编码,然后再进行广播,使一次广播重传可以使多个具有不同丢包的接收机受益。分析和仿真表明,该方法能有效保证接收节点的编码可解性,使重传次数显著减少,更接近于理论值,从而大大提高了传输效率。另外,该方法计算开销小,很适合应用在卫星广播网和无线传感器网等资源受限的系统中。
关键词：无线广播重传,网络编码,重传,传输次数,计算复杂度
二进神经网络 篇2
LEACH协议[1]是无线传感器网络 (Wireless Sensor Network, WSN) 经典的分层路由协议, 能有效地延长网络生存时间。但是由于LEACH协议采用由节点生成随机数的方法选择簇头并成簇, 使得每次成簇的数目相差较大, 簇头在簇中的位置未必最优, 且对簇头的剩余能量也未加考虑, 因此LEACH协议还有可改进之处。
文献[2]在簇头选举时考虑了节点的能量因素, 选择剩余能量大的节点作簇头, 但未对簇的数目和簇头位置进行优化。文献[3]在选择簇头时, 考虑了候选簇头及簇内节点的能量和距离因素, 但对簇的数目和簇的大小未进行控制。文献[4]引入了簇门限数和合并极小簇的方法, 对簇的规模和个数进行了优化, 但对簇头在簇中的位置未作考虑。
针对LEACH协议的不足, 本文基于LEACH提出了一种新的BPSO-LEACH (Binary Particle Swarm Optimization LEACH) 算法。BPSO-LEACH首先在分簇过程中控制簇的数量, 使簇的个数最优以减小全网的能量消耗, 然后对网络中的每一个簇应用二进制粒子群算法重新选择簇头, 使簇内能量消耗之和最小且节点间能耗均衡。
1 LEACH协议的不足
由文献[1-4]可知, LEACH协议存在以下不足:
(1) 每一轮分簇时, 簇的数目可能差别较大。如果簇数太多, 会有较多的簇头向基站传输数据, 使全网的能耗过大;如果簇数太少, 节点可能会离簇头较远, 向簇头传输数据时会因消耗过多能量而导致较早死亡。
(2) 选举簇头时, 由随机数和阈值来决定一个节点是否成为簇头, 没有考虑节点的剩余能量, 使剩余能量较小的节点有可能成为簇头, 导致簇头过早死亡。
(3) 每一个簇中, 簇头位置未必最优, 使簇内节点能耗不均衡。
2 二进制粒子群优化算法
设粒子在D维空间中寻优, 每个粒子有一个位置矢量Xik= (Xki1, Xki2, …, XkiD) , 一个速度矢量Vik= (Vki1, Vki2, …, VkiD) [5]。位置矢量Xik和速度矢量Vik的迭代可用式 (1) 和式 (2) 表示:
式中, w是惯性因子, c1是个体学习因子, c2是全局学习因子, r1和r2是区间[0, 1]上的随机数, PB是粒子的个体最优值, GB是粒子群最优值。
二进制粒子群优化算法BPSO[6] (Binary Particle Swarm Optimization) 的位置矢量是二进制空间, 粒子在每一维上的取值只能是0或1, 速度矢量仍然位于实数空间。BPSO速度矢量的更新公式仍用式 (2) , 位置矢量改用式 (3) 描述:
3 BPSO-LEACH算法
针对LEACH协议的不足, 提出了以下改进方案。
(1) 针对簇的个数不确定, 根据WSN的能量消耗模型, 计算出使整个网络能耗最小的簇数, 在分簇过程中控制簇的数量, 使簇的个数最优。
(2) 针对能量较小的节点可能成为簇头和簇头位置不是最优, 在每个簇中遵循簇头节点能量较大、簇内成员节点能耗均衡的思想, 应用BPSO算法重新选择簇头。
3.1 网络模型
(1) 基站位于WSN外部, 能量不受限制, 计算能力不受限制。
(2) 节点随机部署在一个正方形区域中, 节点初始能量相等, 部署后不再移动。
(3) 基站知道WSN内节点的地理位置和初始能量, 基站能根据节点发送的数据量估算节点的剩余能量。
(4) 成员节点可以根据到簇头的距离, 调整自己的发射功率。
3.2 分簇数目的控制
设WSN中有N个节点, 随机分布在L×L的区域, 共分成K个簇, dHB是簇头到基站的欧氏距离, εfs和εmp是节点的无线通信能量消耗系数。由文献[7]可知:当网络分成个簇时, 总的能量消耗最小, 此时的K称为KBest。
在簇的形成阶段, 每一个成为簇头的节点首先把自己成为簇头的信息报告给基站而不是向全网广播, 此时的簇头称为候选簇头。如果向基站报告的候选簇头的个数超过KBest, 则基站从中随机挑选KBest个作为候选簇头, 其余的作为普通节点;如果候选簇头个数不足KBest个, 则基站线性增大阈值T (n) 并告知全网节点, 重新启动簇头选举, 直到产生KBest个候选簇头。候选簇头确定之后, 按照LEACH中的成簇方法把整个网络分成KBest个簇。
3.3 应用BPSO算法确定最终簇头
从所有节点中选出KBest个候选簇头并成簇后, 候选簇头在簇中的位置很可能不是最优。下面应用BPSO-LEACH算法选择每个簇最优的簇头。
3.3.1 粒子的编码
设簇中有M个节点, 则粒子的搜索空间就是M维二进制空间。粒子i在进化的第k代的位置矢量是Xik= (Xki1, Xki2, …, XkiM) , 粒子每一维矢量的取值只能是0或1。若Xkij=1, 则表示第k次迭代时第k个粒子对应的分簇方案中把第j个节点作为簇头;若Xkij=0, 则第j个节点作为簇中的成员。
3.3.2 适应值函数的设计
应用BPSO-LEACH算法选择簇头时, 优化目标是使簇中所有节点的能耗之和最小且均衡。定义适应值函数如式 (4) 所示:
式中:d2iH是簇中第i个节点到候选簇头距离的平方, var (diH) 是簇中第i个节点到候选簇头距离的方差, eH是候选簇头的能量, α>0, β>0, γ>0, α+β+γ=1。在WSN生命期的不同轮中, 调整α、β和γ的值, 可以使簇头的选举倾向于能耗最小或是能耗最为均衡。
3.3.3 BPSO-LEACH的步骤
对每一个簇分别应用BPSO-LEACH算法选择簇头。
(1) 初始化一个规模为Q的粒子群, 每个粒子的维数是M (簇中节点个数) , 确定参数c1、c2、w和迭代次数k。
(2) 初始化粒子的位置和速度。粒子的位置矢量由式 (5) 给出:
r (0, 1) 是区间[0, 1]上的随机数, R是一个常数。粒子的速度矢量由式 (6) 给出:
其中:VMin和VMax分别是粒子速度的最小值和最大值。
(3) 计算粒子的适应值。对于每一个粒子, 如果Xkij=1, 表示第k次迭代时第i个粒子表示的分簇方案中第j个节点作为簇头, 其他节点作为成员, 利用式 (4) 计算粒子的适应值。
(4) 计算每个粒子的个体最优值和整个种群的全局最优值。迭代过程中, 使适应值函数取得最小值的粒子的位置矢量是个体最优值, 在所有的个体最优值中求出全局最优值。
(5) 根据式 (2) 和式 (3) 更新粒子的速度和位置矢量。
(6) 重复步骤 (3) ~ (5) , 直到完成规定的迭代次数。
(7) 对于最终全局最优值所对应的粒子, 因其对应了若干种簇头选择方案 (簇头选择方案总数等于值是1的矢量的维数之和) 。对每一个候选簇头, 应用式 (4) 求其适应值, 取适应值最小的候选簇头作为最后的正式簇头。
4 仿真实验
应用MATLAB软件对LEACH和BPSO-LEACH进行仿真, 各运行100次, 取平均值进行比较。评价指标是: (1) 网络生存时间, 从仿真开始到网络中70%的节点还存活所经历的轮数。 (2) 网络生存时间内节点的总能量消耗。
4.1 仿真环境和算法参数
仿真参数如表1所示。
4.2 仿真结果
图1是LEACH和BPSO-LEACH的网络生存时间仿真结果。图中的横坐标表示分簇轮数, 纵坐标表示存活节点数。从图1可以看出, LEACH在620轮左右即出现第一个死亡节点, 而BPSO-LEACH在870轮左右出现第一个死亡节点。LEACH的存活节点还剩下70%时的轮数约为1 300轮, BPSO-LEACH约为1 930轮。LEACH分簇的节点在大约2 900轮后全部死亡, 而BPSO-LEACH约为4 500轮。
图2是LEACH和BPSO-LEACH总的能量消耗仿真结果。图中的横坐标表示分簇轮数, 纵坐标表示网络中所有节点的剩余能量之和。由图2可以看出, 在网络分簇的开始150轮, 两种算法的能量消耗相差不大, 随着分簇轮数的增加, BPSO-LEACH的能量消耗要明显小于LEACH。
5 结束语
本文首先在分簇过程中按最优簇数控制了簇的数量。初步分簇过程按照LEACH协议的簇头选举方法选出候选簇头, 成簇后再应用二进制粒子群方法重新选择最终簇头。粒子的编码采用了簇头为1、节点为0的二进制编码方案, 适应值函数的设计目标是簇中节点的能耗之和最小且能耗均衡。迭代结束后取最优粒子中适应值最小的候选簇头作为最终的簇头。仿真结果表明, BPSO-LEACH比LEACH可以节约30%的能量, 延长约50%的网络生存期。
摘要：针对无线传感器网络LEACH协议分簇时, 能量较低的节点可能会成为簇头, 簇头在簇中的位置未必最优的问题, 提出了一种基于二进制粒子群的LEACH协议优化算法。首先在成簇过程中使簇的个数最优, 然后应用二进制粒子群算法在每个簇中选择最优簇头。仿真证明, 二进制粒子群优化的LEACH协议较原始LEACH协议有效降低了总的能量消耗, 延长了网络的生命期。
关键词：无线传感器网络,分簇,LEACH协议,二进制粒子群算法,粒子编码
参考文献
[1]HEINZELMAN W, CHANDRAKASAN A, BALAKRISHAM H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd Annual Hawaii International Conf.on System Sciences.[S.l.]:IEEE Computer Society, 2000:3005-3014.
[2]Chen Xuhui, Yang Zhiming, Cheng Huiyan.Unequal clustering mechanism of LEACH protocol for wireless sensor networks[C].2009 World Congress on Computer Science and Information Engineering (CSIE 2009) , Los Angeles, USA, March 2009
[3]HANDY M J, HAASE M, TIMMERMANN D.Low energy adaptive clustering hierachy with deterministic cluster-head selection[C].Proc.of the 4th IEEE Conf.on Mobile and Wireless Communication Networks.Stockolm:IEEE Communications Society, 2002:368-372.
[4]吕涛, 朱清新, 张路桥.一种基于LEACH协议的算法[J].电子学报, 2011, 39 (6) :1405-1409.
[5]KENNEDY J, EBERHART R C.Particle swarm optimization[C].IEEE International Conference on Neural Networks, IV.Piscataway, NJ, USA:IEEE Service Center, 1995:1942-1948.
[6]KENNEDY J, EBERHART R C.A discrete binary version of the particle swarm algorithm[C].The 1997 Conference on System, Cybernetics and Informatics.Piscataway, NJ USA:IEEE Press, 1997:4104-4109.
二进制代码内联库函数识别 篇3
随着计算机软件业的不断发展,计算机软件安全日益引起人们关注。二进制代码分析是计算机软件安全领域的一个重要手段。在分析某些无法获取源代码的软件时,分析其二进制代码几乎是唯一手段。人们很少直接分析二进制代码,因此一般都是先将机器代码反汇编成汇编代码。库函数识别的作用在于可以直接将反汇编代码中的大段代码替换成可理解的符号( 函数名) ,便于分析人员理解整个程序的反汇编代码。在编译优化的作用下,内联库函数在内联到目标代码后,形态可能发生变化。因此,内联库函数识别存在两个难点要解决。首先,为了对齐指令地址,或指令流水优化, 编译器可能会调整一个函数的某些指令顺序,造成内联库函数字节不连续。其次,编译器寄存器分配策略也会影响内联后的指令,使其发生变化。针对这两个问题,本文基于执行流图来识别内联库函数。
1库函数识别
1. 1执行流图
执行流图EFG ( Execution Flow Graph) G = ( V,E) ,V代表指令集合,代表指令之间执行依赖关系。边( vi, vj) 表明vi早于vj的执行。使用R/W表示指令读/写的变量集合,D表示指令的地址。
一个EFG中的边有两类。第一类边在基本块( 单进单出的指令序列) 内。对于基本块内的两个点a,b,如果满足( Ra∩ Wb) ∪( Wa∩ Rb) ∪( Wa∩ Wb) ≠Ø,Da≤Db,或者b为控制流转移指令,则存在a到b的边。另一类在基本块间。 边( a,b) 满足:
( 1) a和b分别在不同的基本块B1和B2内;
( 2) a可以在基本块B1中最后执行,b可以在基本块B2中第一个执行;
( 3) 在控制流图中,B2是B1的后继。
EFG的构造分为两步。首先,划分函数的基本块,构造控制流图。然后,在基本块内进行数据依赖分析,得到局部EFG。最后,对于每对在控制流图中直接相连的基本块,连接其所对应局部EFG中的出口点和入口点。对于局部EFG中的任意三点A,B,C,如果存在三条边( A,B) ,( B,C) , ( A,C) ,则删除边( A,C) ,因为这条边是冗余的。
1. 2指令编码
指令编码用来将一个指令转换到一个标准形式。首先, 一条指令通过下列步骤规范化来消除指令差别:
( 1) 指令规范化。使用reg1来表示指令操作数中的第一个寄存器,reg2表示第二个寄存器,以此类推。如“mov eax, ecx”“mov reg1,reg2”,“xor eax,eax”“xor reg1,reg1”。
( 2) 内存规范化。使用M表示访存操作数,如“mov eax, [ebx]”“mov reg1,M”。
其次,用二元组SR = ( m,r) 表示消除差异后的指令,其中m表示指令助记符,r为操作数特征值。r中的数字,从高到低,表示操作数的类型。如r = 1表示“op reg1”,r = 11表示“op reg1,reg1”,r = 21表示“op reg1,reg2”。表1给出了指令的所有可能特征值。
最后,SR = ( m,r) 通过调用函数ID( SR) = Hash( m) | ( r < < 16) 转换为一个32位数字,称为此指令的ID。Hash ( ) 是一个字符串函数,将不同的指令助记符映射到不同的16位整数。在同构测试时,指令只要有相同的ID,即认为这些指令是相等的。
1. 3识别
在库函数集合F中目标函数fT的过程如下:
( 1) 反汇编fT;
( 2) 构造fT的CFG;
( 3) 对于F每个内联库函数fL:
1构造fT的EFG;
2检测GT中所有与fL的EFG同构的子图;
3检测每个检测到的子图是否可以外联( 参见本文之前的工作［1］) ;
4报告每个检测到的可以外联的子图为一个库函数。
2实验
2. 1设置
实验所用开源程序列表如表2所示。相应地,分别使用Microsoft Visual C + + 10 ( MSVC ) 和Intel Compiler XE 14 ( ICC) 编译,并生成调试信息。
由于源代码和二进制代码间存在巨大差异,二进制代码中的内联函数的真实信息几乎不可能获知。内联函数和其余代码之间没有明显分界。任何代码片段都可以视为某个内联函数的实例。但由于实验对象是开源软件,因此在一个内联函数之后可以插入一些特殊代码,就可以定位到内联函数的真实信息且不会影响内联函数的EFG。
从源代码编译得到的二进制文件称为原始文件集。从修改后的源代码编译得到的可执行文件称为修改的文件集。 在修改的源代码中,一些函数的随机位置被插入宏“LIBV ( P) ”。P是一个指针或者一个变量的地址。在宏里,输出库函数的结果到屏幕,使得插入代码不会被当成死代码。然后修改宏的定义来生成修改的二进制文件集。strlen( ) 的定义为“#define LIBV( P) printf( " libvcode % d" ,strlen( ( char* ) ( P) ) ) ”。其他函数类似。printf的特殊格式有助于在汇编代码中识别插入的代码。比如在识别strlen( ) 中,代码
其中,位于loc_40B600和push eax之间的代码是strlen ( ) 的一个实例。
实验中的内联库函数有strlen( ) 、strcpy( ) 、strcmp( ) 、 memcmp( ) 。这些函数经常被MSVC内联。相应的源代码来自“Microsoft Visual Studio 10. 0 VC crt src”。汇编代码来自Visual C + + 10,使用参数/FAcs编译( 输出汇编代码,机器代码和源代码) 。编译使用这些库函数的样本代码并提取内联的代码。
对于原始文件集,如果识别出的内联函数在源代码中能找到,则认为识别结果是正确的。原型工具在原始二进制文件集中识别所有4个内联函数。函数strlen( ) 、strcpy( ) 、strc- mp( ) 在C / C + + 程序中常见。在C + + 中标准字符串类的操作包含了这些C字符串函数。在原始二进制文件集的实验中,这些识别结果也会被认为是正确的,即使识别出的函数没有在源代码中显式使用。对于修改的文件集,只统计以 “libvcode% d”为格式化字符串的printf结尾的识别结果。内联函数的真实情况由IDA的一个插件来统计,通过扫描以 “libvcode% d”为格式化字符串的printf得到。
由表3中可见,除了Win Merge,其余程序的每种内联函数数量都不相同。因为一种内联函数的文件集是通过改变插入宏的定义来生成的,这就使得理论上不同内联函数的数量应该一致。但是,一个内联函数实例的数量在没有检查二进制代码前是不确定的,因为某些被插入宏的短的目标函数可能会被编译器内联。另一方面,源代码中插入的宏在编译预处理阶段被展开,增加了一个目标函数的大小。因此,一些目标函数在宏定义为一种内联函数时会被内联,而在宏定义为另一种内联库函数时则不会被内联。
2. 2实验结果
表4和表5分别给出了MSVC和ICC在原始文件集上查准率。表中的'- ' 表示无法计算值。原始文件集里的内联库函数的真实情况未知。因此在表4和表5中查全率无法给出。表6给出了MSVC编译的修改的文件集的查全率和查准率。Win Merge中的strcmp的查准率是空的,因为strcmp在Win Merge中没有被内联。ICC编译的修改的文件集的实验结果没有列出,因为没有发现任何结果。
2. 3讨论
2. 3. 1查准率
表4表明原型工具可以准确地识别内联函数。在原始文件集中仅有少数误报。误报是因为工具无法区分字符串函数的宽字节版本和非宽字节版本。类似wscmp( ) 被误认为strcmp( ) 。两者之间代码的差别就在于操作数的大小( 宽字节版本16位,非字节版本8位) 不同。而在指令编码中, 不考虑操作数的大小,因此导致了上述误报。
2. 3. 2查全率
如表6所示,在修改的文件集中,除了memcmp( ) ,查准率都很高。这是因为memcmp( ) 的指令发生了改变。代码如下所示。
通常,有三个原因造成漏报。首先,函数的反汇编代码可能是不完整的。在反汇编中,工具在遇到间接跳转时停止反汇编。在修改的文件集中,有些代码是插入到了一个case语句中。因为switch/case语句常被编译器翻译为间接跳转, 因此这些内联函数没有被工具识别。
其次,在编译器优化后,一个内联函数可能有不同的指令序列。大多数的漏报都是由于这个原因。比如,编译器可能将一条指令替换为语义等价的指令。如test eax,eax可以替换为cmp eax,ebx,当ebx值为0时。内联函数的参数可以通过寄存器或内存来传递。传递方式也会影响一个内联函数的指令。memcmp( ) 参数count保存到了局部变量var_ 268中,而在库函数中则是一个寄存器中。其他优化,如循环判断外提和循环展开也会影响识别结果。
特别地,一个内联函数可能消失在二进制代码中。一个表达式的结果可能会在编译时被编译器计算出。如strlen( ) 的参数是一个固定字符串,编译器会直接计算出字符串的长度,而不会生成调用strlen( ) 的代码。因此,一些内联函数可能在修改后的文件集中没有出现在期望的位置,也就没被工具发现。
最后,一个内联函数在不同的编译器编译后可能有不同的指令序列。在实验中,因为内联函数的代码是从MSVC中提取,这些代码可能会和其他编译器编译的完全不同。在ICC编译的代码里,由于某些未知原因,strlen( ) 和strcpy( ) 不总是内联。memcmp( ) 和strcmp( ) 被ICC内联,但是对其编译后的二进制代码却与MSVC编译的有所不同。因此,和MSVC编译的原始文件集的实验结果对比,ICC编译的原始文件集中却只有很少的内联函数获得识别,如表5所示。
3相关工作
最负盛名的库函数识别技术是IDA FLIRT［2］。使用字节模式匹配算法来判断一个目标函数是否与IDA已知的签名匹配。DCC［3］类似于FLIRT。Hancock［4］扩展了FLIRT技术,提出一个库函数引用启发规则,认为一个函数如果在一个库函数中被静态调用,那么该函数也是库函数。这些方法的主要缺陷在于一个函数只有头n个字节作为匹配模式。 尽管通过增大n的大小,精度可以很容易获得提高。但是不能保证导入所有库函数。UNSTRIP［5］通过系统调用接口即可识别在二进制代码中的包裹函数( Wrapper Function) 。尽管如此,这个方法却只是局限于识别包裹函数,因为一个库函数可能没有call指令。
最近,文献[6]提出了一个二进制代码搜索的技术。为了计算函数间的相似性,即将函数分解为连续,且简短的代码序列。本文方法和该文献中的方法都需要和编译器优化。 而且,文献[6]中的方法的最大限制是可能产生差的结果,当匹配拥有低于100基本块的函数。
Saed等人提出了一个通过匹配语义整合图的短路径( 轨迹) 识别二进制代码中复用函数的新技术［7］。一个语义整合图整合了控制流图,寄存器流图,函数调用图。尽管这一方法和本文方法相同之处都是基于图,但是其中的匹配过程和本文却完全不同。另外,该法在图上定义了不同类型的轨迹,并且是使用图编辑距离来衡量两个图的相似度。
4结束语
识别不连续字节或有多个变种的库函数是困难的。本文介绍了一个识别内联库函数的新方法。方法的新颖性在于将库函数识别问题转化为EFG子图同构问题。在一些流行软件上设计了一定仿真,从而验证了本文方法的有效性。 如何加速子图同构测试将是本文下一步的重点研究工作。
摘要：内联库函数识别是二进制代码分析的难点问题之一。主要的挑战来自在编译优化的作用下,内联库函数在目标函数中存在多态性和不连续性。本文构建函数的执行流图,将内联库函数识别问题转化为执行流图子图同构测试问题。实验中,对四个常被编译器内联的字符串操作函数,使用MSVC10和ICC14这两个编译器在5个开源软件中进行内联库函数识别测试。实验结果表明,本文方法可以有效识别二进制代码中的内联库函数。
信息编码“二进制系统”教学案例 篇4
本节课选自浙教版《信息技术基础》第一章, 主要任务是使学生掌握二进制系统, 学会二进制的信息编码, 熟悉十进制与二进制之间的相互转化。在教学中尽量使用生活中的案例帮助学生理解, 从而使学生对信息的数字化有所认识。
二、教学目标
知识与技能:认识二进制的特点, 掌握二进制数字系统。
过程与方法:通过教师演示、讲授, 创设情境, 培养学生观察能力、探究能力及合作能力。
情感、态度与价值观:培养学生积极探索世界的兴趣, 增强相互合作的能力, 提高学生动手操作的愿望和意识。
三、学情分析
高一新生对信息技术的实践操作学习兴趣浓厚, 对信息技术的理论学习兴趣不高, 针对这样一种现象, 教师必须将理论学习的课时安排得更加丰富多彩。二进制是计算机系统极其重要的一个概念, 但一些高一学生认为这个知识的学习与否根本不会影响自己的计算机操作能力, 因此教师要更加努力地寻求解决问题的办法, 让学生在积极主动的探索环境中学习二进制, 掌握十进制与二进制间的相互转换。同时, 教材中的这部分内容表述的相对简单且抽象, 仅凭高一学生的认知结构还很难理解这个概念。在设计教学时, 教师要特别注重学生对数制转化问题的理解, 设计学生感兴趣的游戏, 改变教学过程中枯燥无味的运算过程, 让学生在学习过程中积极主动地探索问题, 找寻答案。
四、教学重点、难点
重点:二进制数字系统。
难点:十进制与二进制互换。
五、教学过程
1. 智慧魔眼, 游戏导入
师:大街小巷中, 我们经常会遇到算命先生。前几天, 老师就遇到过一位算命先生, 他的面前摆了一大堆牛皮纸, 纸上写着许多姓氏, 路过的很多行人都围着他看热闹, 我也停下来看个究竟。原来这个算命先生有个神通, 那就是他可以百分百地“测算”出你的姓。于是, 我在一旁静静观察, 经过了几个过路人的测试, 算命先生赢得了人们的默默赞赏。天底之下果真还有这等神人?我百思不得其解。回到家, 我苦思冥想, 终于解开了其中的秘密, 千万别小看了算命先生, 要想设计出这样的方法, 没有科学知识是不行的。
教师展示5张卡片 (如图1) , 让学生暗自记住心里想的那个字母究竟在哪几张卡片上, 确认完毕后学生之间不能交流, 让教师来猜猜结果。
师:我们请孙同学来告诉大家, 你心里想的字母在哪几张卡片上呢?
生:2和4。
师:还有其他的吗?
生:没有了。
师 (故作沉思状) :哦, 我看透了你的心, 你心里想的那个字母是“J”!
生 (抑制不住内心的喜悦, 脱口而出) :太神奇了!
此时, 教室里的气氛更加活跃了, 学生开始相互讨论, 还有的学生主动举手让教师来猜他心里想的那个字母。
师:我知道很多同学也很想试试。我们再请一位同学吧!
生:我的字母在1、2、3上。
师 (故弄玄虚) :哦, 这个字母我好像看不清了!睁大眼睛看看, 知道了, 知道了, 原来是个“G”!
生:嗯, 又对了!
师:大家一定觉得这是个魔术。莫非老师也像魔术师那样可以看透你的心思, 还是你在怀疑那两个同学是我的“托儿”?
学生都摇了摇头。
师:下面是揭晓秘密的时刻了……
设计意图:游戏的设计使教师能够在心里迅速根据学生说出的字母对应的卡片序号, 按照一定的规律推算出学生心里想的那个字母, 从而牢牢地抓住学生的好奇心, 激发学生学习和探究的热情。
2. 从零开始, 设计游戏
教师下发学习任务单 (如图2) 。游戏的所有秘密都藏在这张小小的任务单里。
师:在设计游戏的时候, 我们最好把每个字母数字化, 即每个字母用若干个数字来代替, 这样就便于管理。表格首列的数据是2 6个字母, 第二列数据是十进制编码。某个字母和一张卡片的关系是怎么样的呢?
生 (讨论并汇总) :字母出现在卡片中, 或者该字母不出现在该卡片中。
师:很好!在设计这个游戏的时候, 我也是这么想的, 把不同的字母和不同的卡片进行有规则的配对。如果某个字母出现在某个卡片中被认为是数字1, 某个字母不出现在该卡片中被认为是数字0, 这时候就出现了由0和1组成的数字系统, 即二进制系统。
学生观察表格并讨论:1.二进制数字系统有什么特点?2.如何更好、更快、更准确地填写第三列表格?
设计意图:问题1旨在促进学生快速找到二进制的两个基本数字:0, 1;问题2的目的是引导学生主动提出要将十进制的数字转化成二进制数字, 从而进入二进制编码转化的环节。
师:经过观察, 大家发现目前的任务是将2 6个字母和若干个卡片对应起来, 换句话说, 就是将2 6个字母对应的2 6个十进制数字转化成二进制数。在数的系统内, 有一个规律——十进制转化成N进制可以采用除N取余数的方法, 那么就让我们来试试他们之间的转换吧!
教师在黑板上板书十进制“6”转化成二进制的短除式子, 一边除一边总结规律, 使学生一目了然地看清楚整个短除过程 (如图3) :除数写在商数的右侧, 一直除到0, 从下向上取余数。
教师在表格中填入十进制数字“1”对应的二进制数字“1”, 十进制数字“6”对应的二进制数字“1 1 0”。学生分组合作完成2 6个数字的转换 (将全体学生分成8组, 每组学生分配3个数字从十进制到二进制的转换) , 转换结束后将答案填入对应的表内。
设计意图: (1) 快速完成表格内剩余数字的转换。 (2) 增强学生的合作意识, 加强组内的监督, 使每个学生都参与活动。
师:同学们, 为了接下来方便设计游戏, 我们需要对现有的二进制数做一些等价的调整。大家有没有注意到从二进制数字1到1 1 0 1 0, 他们的数位是不同的, 有没有什么方法可以把不足5位的二进制数变成等价的二进制呢?
生:建议在数字的左侧加“0”。
师:经过调整, 我们的表格变成了如图4所示的形式。我们把二进制数字最低位出现1的字母全部放进1号卡片;把二进制次高位是1的字母放进2号卡片;3号卡片中存放的是从右侧起第三位数字是1的字母;同理, 4号卡片中放入第四位是数字1的字母;5号卡片中放入第五位是数字1的字母。
3. 深入研究, 水落石出
师:游戏的道具已经准备好了, 接下来的任务是如何从测试者的口中“看”到心里想的那个字母。当测试者告诉魔术师字母在2和4号卡片上时, 魔术师马上就产生了一段代码“0 1 0 1 0”, 通过查表我们迅速找到了正确答案。当然了, 其实最好的方法是魔术师将“0 1 0 1 0”二进制转换成十进制, 最后推算出十进制的数字对应的那个字母。
学生阅读与练习:快速阅读书本, 得到二进制数位的权值, 完成二进制向十进制的转换。
师 (板书) :B代表二进制、D代表十进制
以此类推
师 (演示) :
4. 云开雾散, 尝试成功
学生每两人一组进行分组, 每组分到5张卡片, 组员配合把2 6个字母分配到5张卡片中。两位学生角色分配, 分别扮演魔术师和群众, 看看哪个小组的魔术师反应最快。
学生摩拳擦掌, 跃跃欲试, 整个课堂气氛极其活跃。
师:经过今天的小魔术, 我们发现只要大家肯动脑筋, 不可思议的事情都能实现。在生活中, 我们接触电脑时, 输入的是十进制, 到了电脑内部运算却变成了二进制, 当我们通过Q Q聊天的时候, 输入中文、英文, 到了电脑内部却变成了二进制数字, 那么计算机为什么要采用二进制系统, 我们平时接触最多的英文、符号、汉字又是怎样进行二进制编码呢?敬请大家期待下节课的解答吧!
六、教学反思
二进神经网络 篇5
1 一般情况
一般情况下,HttpSendRequest API函数可以上传字符的字节数据到服务器端的缓冲区,再由服务器端程序的接收程序从缓冲区取出数据来使用。
将API函数在模块级中定义(仅定义HttpSendRequest函数,其它用到的API函数读者可参照定义):
以上代码解释如下:
(1)通过InternetOpen、InternetConnect、HttpOpenRequest、HttpAddRequestHeaders API函数和IIS服务器建立连接,具体体现在sUrl参数上。通过ASP文档调用dll自编程序库实现和服务器连接,服务器接收数据的程序就是放在自编的dll程序库中。
(2)用HttpSendRequest API函数上传数据:lpszPostData表示要上传的数据;lPostDataLen表示要上传数据的字节长度;h HttpOpenRequest是连接服务器的句柄。
(3)最后用InternetCloseHandle API函数一级一级的关闭Internet连接和URL句柄。如果上传成功返回真,否则返回假。
2 问题分析与解决
通过上面代码可以了解到数据上传的过程。但是,在实际应用过程中经常会出现上传文件不成功的情况。主要存在两个问题:
2.1 postdat参数传来的不是字符串
在上载文件时,无论文件大小,如果是二进制数据,都不能正确的把数据上载上去。虽然postdat参数可以给二进制数组,但经过lpszPostData=poststr$&"&FileStart="&postdata语句已自动将其转化为字符。而HttpSendRequest API函数将其上传时自动进行了编码转换即将字符串由Unicode转换为系统的缺省码,相当于使用StrConv(lpszPostData,vbFromU-nicode)函数,所以求上传字节长度的时候要用l PostDataLen=LenB(StrConv(lpszPostData,vbFromUnicode))语句,则传上去的字节数完全正确。
但是若上传的全部是有效字符,服务器端经过StrConv(Vs_DataBuffer,vbUnicode)转换就可提取出所有字符并全部是正确的。
若上传有二进制非有效字符数据时,如上例中:lpszPostData=poststr$&"&FileStart="&postdata,其中poststr$是有效字符,作用是给服务器怎样操作的信号数据,postdata是二进制数据经过转换的字符串数据(实际是转换成乱码),这些字符串数据也可以上传上去,但是再经过服务器端的StrConv(Vs_DataBuffer,vbUnicode)转换后就不是原来的二进制数据了,虽然字节数目完全相同,内容却已完全不同,若不经StrConv函数转换实际也不是源文件内容了,这是因为StrConv函数是不能对非有效字符进行转换的。
通过以上分析,可以看出HttpSendRequest API函数上传二进制数是有限制的,为了能实现上传二进制数据,避免单双字节编码转换对程序带来的影响,将HttpSendRequest API函数进行别名重定义如下:
不知道读者注意没有,上述代码中的HttpSendRequestByte API函数的声明已经改变了。第4个参数的声明由一个String字符串变成了一个Any的参数,这样就可以给第4个参数Byte数组了。
只是为了表单做温度计时控制温度计的运行速度和上载无关,可以不去理会。
而HttpSendRequest API语句的调用改为:
经过这样的改进即可达到上传二进制的目的。服务器端的接收程序也无需用StrConv(Vs_DataBuffer,vbUnicode)转换。这样我们就解决了第一个问题。
2.2 postdat的字节数不能大于50MB
上传大文件时由于数组的大小是长整型。传送、接收都要用到数组,所以超出长整型范围就会溢出。
若是大文件可以在调用时用循环的办法每次取出不超过50MB字节的数据调用之。调用程序如下:
此方法对2G的文件进行测试已可以准确无误的将文件上载存入服务器磁盘。
为读者更好理解,给出服务器端接收数据对应程序:
自编函数GetBinaryData的功能是防止传上来的二进制数据从缓冲区取出时由于过大出现错误。
在服务器端程序创建一个类模块编写下列代码:
注意:HttpSendRequest函数上传数据的参数是字符类型,接收数据时必须进行StrConv(Vs_DataBuffer,vbUnicode)转换。如果上传数据的参数是二进制数组则无需进行转换。
3 结语
二进神经网络 篇6
1.1 问题描述
用C语言解决如下问题:有一个用火柴棒拼成的等式,如图1所示移动2根以内的火柴棒使等式成立。输入一个现有的等式,输出所有成立的等式,并在每个等式后面注明是移动几根火柴棒使等式成立的。
1.2 题目要求
(1)等号不许移动,运算符只能是“+”或者“-”。
(2)这里暂时只讨论两位数的情况(所有数字在0-99之间)。变换后不能出现最高位是0的二位数(例:08),但是数字0是可以出现的。
(3)数字之间的变换必须是最少移动次数。
(4)不能在原来的数后面添加火柴棒(例:8→81),也不能把原来数后面的一位去掉使变成一个一位数(例:81→8)。
(5)可以在原来的数前面添加火柴棒(例:8→18),或者把原来数的最高位去掉(例:18→8)。
2 算法原理及可行性
2.1 程序的总体算法分析和对时间复杂度的分析
最简单的思路就是分别循环等式中的所有可以变换的状态,一个个的分析排除,即用枚举策略。因为数字范围是0-99,一共只有3个数字和一个可以变换的符号,又因为最后一个数字有可能是前两个数的和或者是差并且与符号的变换是相对应的,用枚举策略的话需最多100*2*100=2*10^4次运算,显然是可行的。
2.2 程序数据结构分析和对空间复杂度的分析
为了便于对等式中火柴棒根数的控制设定一个100的一位数组记录组成数字i所需要的火柴棒根数。再设定一个10*10的二维数组记录数字i变换到数字j所需要的最少步骤数(为了避开小数运算,我们把移动一根火柴棒的步骤数记为10,即移入和移出一个火柴棒分别记为5。在下面的文段中会详细介绍二维表的生成过程)。[1]
3 程序的算法思路
3.1 程序流程图,如图 2 所示。
3.2 用火柴棒表示的各个数字在计算机中的表示
对于每一位数字都是在8个位置中放几个适当的火柴棒来表示一位数字的。也就是一共8个位置,每个位置上要么有火柴要么没有,对于这2种状态,我们分别记为0和1,把这一串0和1组成的二进制数字就可以表示出用火柴棒表示的数字的具体情况。例:数字5用火柴棒排列如图3所示。在计算机中我们对每一根火柴棒的位置从1开始进行的编号,如图4所示。
我们把用火柴棒的地方记1,没有的记作0,按照顺序可以写出1101011的二进制数字,然后转换成十进制的数字就是107。同理0-9对应的十进制数字分别为119,36,94,110,45,107,123,38,127,111。[2]
3.3 二维表代码详解
以下是二维表代码详解:
int build ()// 建立数字i变到数字j所需要的步骤数的二维表
4 思考和体会
二进神经网络 篇7
无线局域网协议是以IEEE 802.11[1]标准为基础的。该标准定义了一个信道接入控制 (MAC) 子层和3个物理 (PHY) 层。IEEE 802.11协议的目标是构建一个能够提供与有线网络类似服务的无线网络。但因带宽的有限性, 提高信道利用率就成为关键。
网络仿真技术[2], 即网络行为的模拟, 通过数学和统计方法建立模型 (包括网络设备、协议和链路) , 模拟网络中传输的数据, 获得网络优化设计时其性能数据的一种新技术。通过该技术可发现网络行为中出现的异常情况, 并对网络优化的可行性等进行验证。
相对于有线网络, WLAN中较高的误码率和“隐藏终端“ (Hidden Terminal) 等问题[7]是WLAN中常见的问题。此外, 一个站点为了能检测到冲突而不能够监听到它自己的传输, 在无限网络中, 难以进行载波监听[3]。本文在OPNET模拟仿真的基础上深入分析得出:利用RTS/CTS访问方式来解决“隐藏终端”问题;在活动节点数多且误码率高的情况下启用拆分门限功能。由于在在二进制退避算法 (binary backoff algorithm) 中, 竞争窗口在初始化时为一固定值。本文对二进制退避算法进行改进, 即计算时隙利用率来评估共享信道的竞争状况来动态调整竞争窗口的大小。通过仿真实验, 结果表明, 该算法能够有效降低网络负载和冲突, 并提高网络接入率。
1 DCF模式简介
DCF是IEEE 802.11M AC层协议中最重要与最基本的接入模式, 它采用CSMA/CA与二进指数退避机制来支持用户终端的异步数据通信。它试图让各个终端通过竞争来公平和高效的利用无线信道资源。RTS/CTS访问方式和基本访问方式是DCF的两种接入方式。
1.1 DCF的基本访问方式
在DCF方式中, 发送节点侦听到无线信道连续空闲时间达到DIFS后, 发送数据帧, 为了增强对异步业务传输的可靠性, DCF使用MAC层确认机制, 接收节点检验所收到的数据帧的循环冗余校验码 (CRC, Cyclic Redundancy Code) , 如果正确, 则在等待SIFS间隔后向发送节点发送一个ACK帧, 以表明已经成功的接收到该数据帧。如果在一定的时间内, 没有收到返回ACK帧, 发送节点就认为本次传输失败, 需要重传该数据帧。
1.2 DCF的RTS/CTS访问方式
“隐藏终端“ (Hidden Terminal) 在WLAN中经常出现, 为了解决这个问题, DCF利用RTS和CTS两个控制帧进行信道预留。RTS/CTS访问模式的具体过程可描述如下:
1) 在等待了DIFS (再加上随机退避时间) 后, 发送节点首先发送RTS控制帧。收到RTS的每个节点都根据持续时间域 (Duration Field) 来设置它的NAV (Network Allocation Vector) 。NAV制定了节点可以试图访问介质的最早时间点。
2) 如果传输数据的接收节点收到RTS, 在等待SIFS后, 需要进行应答, 通过CTS帧来实现。CTS帧也包括持续时间域, 而且所有接到这个CTS的节点必须再次调整他们的NAV。
3) 最后, 在SIFS间隔后, 发送节点可发送数据帧。接收节点在接收到数据帧后再等待SIFS间隔, 用ACK确认。
1.3 二进制退避算法
在MAC层协议中, 将重点考虑退避算法, 该算法在以下几方面具有重要作用:节点数据发送冲突分解效果较好;节点公平的接入到网络以及信道利用率的提高等等。网络中任一节点在发送数据过程中发生冲突, 将等待一定的时延后继续发送, 其中时延通常是指数增长, 一直增加到退避时间间隔的最大值CWmax;相反, 若节点数据顺利发送, 未发生冲突, 退避时间间隔将达到最小CWmin。二进制退避算法描述如下:
Step 1网络中节点先要确定信道的状态 (忙或闲) , 在进行发送数据, 通过调用载波监听机制进行判断, 在信道状态闲时, 发送数据;若为忙状态, 将继续监听, 直到闲状态才继续发送数据。
Step 2信道为闲状态时, 同时满足以下条件, 即连续空闲时间为DIFS长度, 进行向目的节点发生数据。节点数据发送过程中, 并不马上发生, 而是增加一个退避过程, 起到避免冲突发生的作用。
退避时间 (Backoff Time) 随机产生, 在退避计数器中存入产生得随机Backoff Time。Backoff Time由下面的公式1计算得到。Backoff Time产生的过程与计数器中是否有值相关, 若存在一个非零值, 将不会产生随机退避时间。
其中, Random () 是随机整数, 均匀分布在
[0, CW]范围内, CW (Contention Window) 竞争窗口为一整数值, 满足条件CWmin<=CW<=CWmax, CWmin为最小竞争窗口, CWmax最大竞争窗口, aSlotTime[3]表示一个时隙的实际长度。
Step 3网络中一个节点执行退避过程时, 如果侦听到信道空闲时间达到一个时隙, 则将Backoff Time计数器减1;若信道处于忙状态, Backoff Time计数器将处于冻结状态, 退避过程因而将会停止, 等到侦听信道状态再次为空闲, 进行进行退避过程, 计数器继续-1。该节点在计数器值递减到零时, 进行数据发送。标准IEEE802.11协议的实现详见4.3节的进程模型。
2 自适应二进制退避算法[4,5]
由上面的分析可以得出:
1) 网络中的节点发送数据产生冲突的概率随着节点数的增加而增加, 随之也会影响CW, 也会增大。在DCF的协议中, CW一般都是从由物理层决定的CWmin, 并且增加方式按照指数形式增加。当网络节点数多的情况下发送数据帧时, 冲突次数增加, 将会在一定程度上浪费无线信道, 造成节点所在网络性能的降低。因此, 需要对上述提到的指数增长方式进行适当修改。
2) 同时, 根据标准DCF协议, 网络节点数据重发次数达到上限或成功后, 设置CW=CWmin。因为网络节点数据的成功发送并不能认为网络节点间的冲突概率已经最小, 或者冲突概率减小, CW重置为最小的机制将不在适用。鉴于此, 提出了CW的慢递减机制, 即网络节点数据发送成功后修改CW的重置机制。此外, 还可以通过对不同等级的业务, CW按不同的算法增长或递减, 从而能够实现提供不同优先级的服务, 将会提高网络运行的性能。
3) CW介于CWmin和CWmax之间, 节点发送数据发生冲突时, CW将一直朝着CWmax以指数形式增加。标准DCF中是CW固定的, 跳频方式CWmin为15, 直接序列扩频方式为31。
网络中节点少, 需要进行长时间的等待过程, 而当节点数增加时, 节点发送数据产生传统的概率也随着增多, 进而影响WLAN的性能。可以得出CW与网络中的节点数存在一定的关系。因而, 为了使WLAN的性能达到最优, 初始化CW值的设置需要针对网络中的节点数的多少进行适当调整。
基于上述分析, 本文提出了自适应退避机制, 其核心思想是:利用计算时隙利用率来评估共享信道的竞争状况, 从而解决上面提到的问题。当检测到竞争水平高时, 这表明如果一个站点发送一个数据包就会产生碰撞。此时, 该算法就会触发一个虚拟碰撞过程并且扮演着退避角色, 以此来代替发送一个数据包。这样, 碰撞就有可能避免, 可以提高无线信道的利用率、网络的吞吐率以及网络的公平性。在标准IEEE802.11协议的基础上, 增加PT_BACKOFF和PT_TEST状态, 改进算法如下:
有限状态机PT_BACKOFF状态:
有限状态机PT_TEST状态:
有限状态机BKOFF_NEEDED状态:
3 自适应退避算法仿真
OPNET[6,7]提供了良好的开发接口, 能够根据网络环境和协议的需要建造不同的仿真模型, 其仿真模型分三层来实现, 从上到下分别为:网络层、节点层和进程模型。网络层, 反映网络拓扑结构;由相应的协议模型构成的节点层, 反映设备特性;进程模型以有限状态机来描述。仿真模型和实际的网络、设备、协议一一对应, 网络相关特性也被全面反映。
3.1 建立网络模型
本文建立了图1的独立基本服务子集[7]的网络模型, 用于比较二进制退避算法和自适应退避算法。
3.2 建立节点模型
Wlan_wkstn节点由source、sink、wlan_mak_intf及wireless_lan_mac四个处理器组成。引用的进程模型分别为bursty_source、sink、wlan_mac_interface、wlan_mac。其中wlan_mac进程对应的源文件是wlan_mac_pr.c。该模块结构简单, 仅包含3层, 顶层的source和sink概括了OSI的网络层以上的部分, 这为单独研究MAC层提供了极大的方便。
3.3 建立进程模型
根据IEEE802.11协议的二进制退避机制, 共设计了9个有限状态机以完成网络架构、DCF模式下的CSMA/CA信道竞争机制以及RTS/CTS的协调功能等, 有限状态机如图2所示。
3.4 自适应退避算法仿真结果及分析
修改wlan_mac.pr.c文件后, 构建自组织网络架构, 站点分别为10、22、60个, 其他参数设置如表1所示。
仿真结果如图3所示。
仿真结果表明:随着活动节点数由10、22到60个的增加, 发送数据的冲突概率在增大, 这时需要较大的初始化活动窗口, 自适应改进算法中CCW=CWmin*2+1, 这是根据信道的利用率来一次调整就可以完成数据的发送, 而DCF规定竞争窗口只能从最小值以指数形式增大, 节点需要几次冲突后才能发送数据, 这样明显的降低了网络负载;标准DCF协议规定, 发送成功或达到重传次数限制后, 将CW重置为CWmin, 然而一次成功传送并不能断定网络中的冲突概率已经减小, 所以不应该将重置为最小, 而自适应改进算法是根据信道利用率以及CCW的大小来判断是否重置CW, 这样可以降低接入延时。
图3 (a) 表明, 自适应退避算法较标准的二进制退避算法在网络负载降低大约20%;活动节点数的增加至22个, 见图3 (b) , 负载降低大约30%;活动节点数的增加至60个, 见图3 (c) , 负载降低大约50%。由此可见自适应退避算法较标准二进制退避算法降低了网络负载。
4 结束语
通过对IEEE802.11协议在OPNET上的仿真实现, 分析对比各种参数对网络性能的影响, 可以得出以下结论:1) 采用自适应退避算法, 能够有效的降低冲突, 具有一定的应用价值;2) OPNET在网络优化、协议验证、设备优化升级等方面为我们提供方便, 当前针对OPNET的研究还较少, 对网络仿真的方法有一定的探索和实践意义。
参考文献
[1]IEEE Standard forW irelessLANMedium Access Control (MAC) and Physical Layer (PHY) Specifications[Z].ANSI/IEEE STD802.11, 1999Edition, New York, 1999.
[2]王文博.OPNETModeler与网络仿真[M].北京:人民邮电出版社, 2003.
[3]L.Bononi, M.Conti, and L.Donatiello, “Design and performance evaluation of a distributed contention control (DCC) mechanism for IEEE802.11wireless local area networks, ”in Proceedings of First ACM International Workshop on Wireless Mobile Multimedia, 1998, 10:59-67.
[4]OPNET Technologies, Inc., “Wireless LAN model deccription, ”http://www.opnet.com/products/library/WLAN_Model_Guide1.pdf.
[5]F.Cali, M.Conti, and E.Gregori, “Dynamic tuning of the IEEE802.11protocol to achieve a theoretical throughput limit, ”IEEE/ACM Transactions on Networking, 2000, 8 (6) :785-799.
[6]陈敏.OPNET网络仿真[M].北京:清华大学出版社, 2004.