一种基于多步信道预约的虚拟分组冲突解决方法转让专利
申请号 : CN200810017368.3
文献号 : CN101232451B
文献日 : 2010-06-09
发明人 : 李波
申请人 : 西北工业大学
摘要 :
本发明公开了一种基于多步信道预约的虚拟分组冲突解决方法，当通信终端处于发送分组状态时，在将要预约的时隙前后加入若干空闲时隙；即当发送终端进行时隙预约时，该发送终端应保证所要预约的信道时隙是空闲的，并且该空闲时隙的前面p(＞0)个时隙和后面p(＞0)个时隙均为空闲时隙；当通信终端处于监听信道状态时，检测虚拟冲突并通过预约保护时隙的方法进行回避。从实现的复杂度以及运算量方面考虑，本发明提出的方法均具有明显的优势，具有更好的实用性。
权利要求 :
1.一种基于多步信道预约的虚拟分组冲突解决方法，其特征在于包括下述步骤：当通信终端处于发送分组状态时，在将要预约的时隙前后加入若干空闲时隙；即当发送终端进行时隙预约时，该发送终端应保证所要预约的信道时隙是空闲的，并且该空闲时隙的前面p＞0个时隙和后面p＞0个时隙均为空闲时隙；当通信终端处于监听信道状态时，检测虚拟冲突并通过预约保护时隙的方法进行回避；所述的检测虚拟冲突并通过预约保护时隙的方法包括下述步骤：(a)当某一通信终端检测到其他发送终端做出了和它一样的信道预约后，则表示检测到了虚拟分组冲突的发生；
(b)当检测到虚拟冲突发生时，该发送终端就检测其事先在该已预约时隙前后所预留的2p个保护时隙中是否有未被预约的空闲信道时隙；这样的检测过程按照距离该已被预约时隙由近到远的次序逐个进行，直到检测到一个离该已被预约时隙最近的空闲时隙为止，并将该空闲时隙作为新的预约时隙。
2.根据权利要求1所述的一种基于多步信道预约的虚拟分组冲突解决方法，其特征在于所述的加入若干空闲时隙包括下述步骤：(a)为在发送终端的队列中等待发送的数据分组，分别产生出相应的退避计数器初值；产生这些初值的时候，应保证其所对应的信道时隙及其前后2p个信道时隙均是空闲的；
(b)将产生好的退避计数器初值填写到相应的退避计数器中，并在其维护的信道预约窗中将新近预约的时隙标记为“已被预约”；
(c)将产生好的退避计数器初值填写到即将发送出去的数据分组的头信息域中，并将该数据分组发送出去。
3.根据权利要求1所述的一种基于多步信道预约的虚拟分组冲突解决方法，其特征在于：所述的保护时隙个数取p-2。
说明书 :
技术领域
本发明涉及通信技术领域，特别是一种无线局域网中的分组冲突解决方法。
背景技术
当前IEEE 802.11标准已经成为了无线局域网接入技术的公认国际标准。在IEEE802.11标准中主要定义了两种多址接入协议：其一是分布式协调功能(DCF)，另外一个是点协调功能(PCF)。DCF是被业界广泛采用的多址接入标准。DCF是基于载波侦听与冲突回避机制的一种多址随机接入策略。
随着技术的飞速发展，近年来基于IEEE 802.11的无线局域网技术得到了广泛的应用。一方面，随着越来越多的用户使用这一技术，IEEE 802.11无线局域网所工作频段的频谱资源变得越来越紧张。另一方面，IEEE 802.11标准所推荐使用的分组冲突解决方法在网络用户数多以及通信信道质量差的情况下不能有效的控制分组冲突的发生。频繁的分组冲突，将导致系统的信道利用率大幅度下降。
为了改进IEEE 802.11多址接入协议的性能，具备一个高效而可靠的分组冲突解决方法是至关重要的。然而在目前已有的大多数冲突解决方法中，通信终端均相互独立的产生各自的退避计数器初值，于是分组冲突便不可避免(尤其是在系统业务量较大的情况下)。在美国Baldwin R.博士和韩国Choi J.博士所分别提出的接入策略中，发送终端在发送当前数据分组的同时，把接下来的数据分组将要使用的退避计数器的初值预先广播出去。这样相应的时隙便被预约下来，从而避免了其他发送终端使用同一时隙进行数据发送。但他们提出的信道预约算法均只是一步预约(即通过发送当前数据分组，仅完成对接下来的一个数据分组所即将使用的时隙进行预约)。众所周知，传输差错在无线信道上是不可避免的。在有些情况下，这样的传输差错率还比较高。当无线信道传输特性较为恶劣时，一步预约算法便不能保证广播出去的信道预约信息被尽可能多的其他发送终端所获取。这样也就无法进一步避免分组冲突的发生。仿真实验表明，一步预约算法的性能对信道传输差错非常敏感(随着信道传输差错率的增加而显著下降)。
为解决IEEE 802.11无线局域网中分组冲突问题，我们在发明专利申请200710017816.5中提出了一种基于多步信道预约的分组冲突解决方法。采用该方法能有效提高网络频谱资源的利用率。
然而要实现专利申请200710017816.5提出的分组冲突解决方法，还需要一个简单而高效的虚拟分组冲突解决方法。所谓虚拟分组冲突就是指两个或更多的发送终端由于相互间未能接收到彼此的信道预约信息，从而做出了同样的信道预约，即预约了相同的信道时隙。如果不采取措施去解决这样的虚拟分组冲突，这些发送终端将在该信道时隙上同时发送数据，从而产生真正的分组冲突。因此一旦某发送终端检测到了虚拟分组冲突的发生(即其他发送终端预约了和他相同的信道时隙)，就必须采取措施解决虚拟分组冲突，从而避免真正的分组冲突的发生。在发明专利申请200710017816.5中，虚拟分组冲突解决方法沿用了韩国Choi J.博士等提出的方法。在韩国Choi J.博士等提出的虚拟分组冲突解决方法中，假设虚拟分组冲突发生在终端A和B之间(即A和B做出了同样的信道时隙预约)，且终端A检测到了该虚拟分组冲突的发生，那么A将放弃它预约的这个信道时隙，并寻找未被周边其他发送终端预约的空闲时隙。找到以后，A将其标记为新的预约信道时隙。同时，对于周边其他终端，如终端C，如果它也检测到该虚拟分组冲突的发生(即它检测到一个信道时隙先后被多个终端预约了多次)，为了与终端A在信道预约上保持同步，C也执行和A同样的虚拟分组冲突解决算法，从而也找到另外一个空闲信道时隙(该信道时隙和A找到的信道时隙位置应相同)，并将其标记为已被预约。该方法存在的一个问题是，每当虚拟分组冲突发生时，周边众多的发送终端只要检测到该虚拟分组冲突的发生，均须运行同样的虚拟分组冲突解决算法。显然，这给网络中每个发送终端均带来了沉重的运算负担。该方法存在的另外一个问题是，当系统业务量大且虚拟分组冲突发生时，发送终端另外寻找到空闲信道时隙将变得越来越困难。这是因为很多信道时隙均已被周边发送终端预约了。这样一来，虚拟分组冲突发生时，发送终端将花费更多的运算量去重新定位空闲信道时隙，从而带来了额外的运算开销。在有些情况下，甚至找不到合适的空闲信道时隙，从而造成信道利用率的下降，且分组冲突概率的加大。
随着技术的飞速发展，近年来基于IEEE 802.11的无线局域网技术得到了广泛的应用。一方面，随着越来越多的用户使用这一技术，IEEE 802.11无线局域网所工作频段的频谱资源变得越来越紧张。另一方面，IEEE 802.11标准所推荐使用的分组冲突解决方法在网络用户数多以及通信信道质量差的情况下不能有效的控制分组冲突的发生。频繁的分组冲突，将导致系统的信道利用率大幅度下降。
为了改进IEEE 802.11多址接入协议的性能，具备一个高效而可靠的分组冲突解决方法是至关重要的。然而在目前已有的大多数冲突解决方法中，通信终端均相互独立的产生各自的退避计数器初值，于是分组冲突便不可避免(尤其是在系统业务量较大的情况下)。在美国Baldwin R.博士和韩国Choi J.博士所分别提出的接入策略中，发送终端在发送当前数据分组的同时，把接下来的数据分组将要使用的退避计数器的初值预先广播出去。这样相应的时隙便被预约下来，从而避免了其他发送终端使用同一时隙进行数据发送。但他们提出的信道预约算法均只是一步预约(即通过发送当前数据分组，仅完成对接下来的一个数据分组所即将使用的时隙进行预约)。众所周知，传输差错在无线信道上是不可避免的。在有些情况下，这样的传输差错率还比较高。当无线信道传输特性较为恶劣时，一步预约算法便不能保证广播出去的信道预约信息被尽可能多的其他发送终端所获取。这样也就无法进一步避免分组冲突的发生。仿真实验表明，一步预约算法的性能对信道传输差错非常敏感(随着信道传输差错率的增加而显著下降)。
为解决IEEE 802.11无线局域网中分组冲突问题，我们在发明专利申请200710017816.5中提出了一种基于多步信道预约的分组冲突解决方法。采用该方法能有效提高网络频谱资源的利用率。
然而要实现专利申请200710017816.5提出的分组冲突解决方法，还需要一个简单而高效的虚拟分组冲突解决方法。所谓虚拟分组冲突就是指两个或更多的发送终端由于相互间未能接收到彼此的信道预约信息，从而做出了同样的信道预约，即预约了相同的信道时隙。如果不采取措施去解决这样的虚拟分组冲突，这些发送终端将在该信道时隙上同时发送数据，从而产生真正的分组冲突。因此一旦某发送终端检测到了虚拟分组冲突的发生(即其他发送终端预约了和他相同的信道时隙)，就必须采取措施解决虚拟分组冲突，从而避免真正的分组冲突的发生。在发明专利申请200710017816.5中，虚拟分组冲突解决方法沿用了韩国Choi J.博士等提出的方法。在韩国Choi J.博士等提出的虚拟分组冲突解决方法中，假设虚拟分组冲突发生在终端A和B之间(即A和B做出了同样的信道时隙预约)，且终端A检测到了该虚拟分组冲突的发生，那么A将放弃它预约的这个信道时隙，并寻找未被周边其他发送终端预约的空闲时隙。找到以后，A将其标记为新的预约信道时隙。同时，对于周边其他终端，如终端C，如果它也检测到该虚拟分组冲突的发生(即它检测到一个信道时隙先后被多个终端预约了多次)，为了与终端A在信道预约上保持同步，C也执行和A同样的虚拟分组冲突解决算法，从而也找到另外一个空闲信道时隙(该信道时隙和A找到的信道时隙位置应相同)，并将其标记为已被预约。该方法存在的一个问题是，每当虚拟分组冲突发生时，周边众多的发送终端只要检测到该虚拟分组冲突的发生，均须运行同样的虚拟分组冲突解决算法。显然，这给网络中每个发送终端均带来了沉重的运算负担。该方法存在的另外一个问题是，当系统业务量大且虚拟分组冲突发生时，发送终端另外寻找到空闲信道时隙将变得越来越困难。这是因为很多信道时隙均已被周边发送终端预约了。这样一来，虚拟分组冲突发生时，发送终端将花费更多的运算量去重新定位空闲信道时隙，从而带来了额外的运算开销。在有些情况下，甚至找不到合适的空闲信道时隙，从而造成信道利用率的下降，且分组冲突概率的加大。
发明内容
为了克服现有技术运算量大且性能较差的不足，本发明提出了一种适用于多步信道预约方法的虚拟分组冲突解决方法。该方法具有实现简单且性能更好等优点。
本发明解决其技术问题所采用的技术方案是：考虑一个单跳的无线局域网(如果信道通信质量良好，基本服务区“BBS(Basic Service Set)”内的所有通信终端均可以相互“听到”其他终端在信道上的传输活动)。设发送终端A正在向终端B发送数据分组An(角标“n”表示该数据分组的序号)。为了避免发生分组冲突，在发送An时，A将在其发送队列中等待发送的其他后续分组An+1，An+2，...，An+m将要使用的退避计数器初值xA_n+1，xA_n+2，...，xA_n+m插入到当前即将要发送的分组An的头部信息域中(具体预约的时隙位置可以通过这些退避计数器初值计算出来)。这样，在发送An的同时将其后续的m个分组所对应的m个退避计数器初值事先广播出去，从而起到了信道预约之目的。服务区中的其他发送终端在接收到An后，从其中提取出退避计数器初值xA_n+1，xA_n+2，...，xA_n+m，并计算出相应的预约时隙的绝对位置，从而避免在这些时隙上发送分组。通过这样的预约机制，可以保证广播的信道预约信息以很高的成功率被周边的其他发送终端所获取，进而避免分组冲突的发生。
然而，利用上述多步信道预约机制并不能避免虚拟分组冲突的发生。为了有效解决可能发生的虚拟分组冲突，针对通信终端可能处于发送分组状态或处于监听信道状态，在本发明中相应的提出了解决虚拟分组冲突的措施：当通信终端处于发送分组状态时，在将要预约的时隙前后加入若干空闲时隙；即当发送终端进行时隙预约时，该发送终端应保证所要预约的信道时隙是空闲的(即未被其他发送终端所预约)，并且该空闲时隙的前面p(＞0)个时隙和后面p(＞0)个时隙均为空闲时隙。这样，便在所预约的信道时隙前后引入了2p个保护时隙。当通信终端处于监听信道状态时，检测虚拟冲突并通过预约保护时隙的方法进行回避。
上述加入空闲时隙的方法具体包括如下步骤：
步骤1：产生退避计数器初值。为在发送终端的队列中等待发送的数据分组，分别产生出相应的退避计数器初值。产生这些初值的时候，应保证其所对应的信道时隙及其前后2p个信道时隙均是空闲的。
具体来说，考虑一个发送终端A，当其1号退避计数器的值递减至0时，根据IEEE802.11DCF的规定，这时A将发送队列中的第一个数据分组。A在将数据分组发送出去之前，需要完成对接下来的m个分组(不包括当前将要立刻发送的分组)的发送进行预约。这样的预约是通过计算出最多m个退避计数器的初值，并伴随着当前分组的发送广播出去而完成的。
为了叙述方便，设当前要发送分组为An。假设在发送其前面分组An-i(i≥1)时，已经完成了对后续分组An+j(1≤j≤mr)的预约(也就是说，这mr个分组已有退避计数器初值与之分别相对应)。又设发送完当前分组An后，A的发送队列中还剩下mw个分组等待发送(显然mw≥mr)，因此A还需计算出min(m，mw)-mr个退避计数器初值。也就是说，在发送当前分组的同时，A总共需广播出mA＝min(m，mw)个退避计数器初值。
产生每个退避计数器初值的方法是相同的，因此这里仅说明一个退避计数器初值的产生方法。设将要产生的与i号退避计数器所对应的退避计数器初值为xA_i。已知前一个退避计数器，即第i-1号退避计数器，所预约的时隙在信道预约窗中的位置为TA_i-1。初始计算时，令q＝1。首先，在1和min[q·(CWmin-1)，(CWmax-1)]间均匀产生出一个随机数x1作为退避计数器初值(CWmin表示最小竞争窗尺寸，CWmax表示退避计数器的最大值)，即x1＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。如果该值所对应的时隙以及其前后共计2p个时隙，即时隙(TA_i-1+x1+s)mod(1024×m)(-p≤s≤p)中的任何一个时隙已被其他终端所预约，就表明产生的x1所对应的时隙不符合我们的要求，于是就再次产生出第二个随机数x2＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。如果连续L次产生出的随机数x1，x2，...，xL所对应的时隙均不符合我们的要求，则将当前的q值加1。然后利用与上面同样的方法直至产生出符合要求的值作为最终产生出的退避计数器初值xA_i。这样，i号退避计数器所预约的时隙在A的信道预约窗中的位置为TA_i＝(TA_i-1+xA_i)mod(1024×m)。
步骤2：标记已预约时隙。将产生好的退避计数器初值填写到相应的退避计数器中，并在其维护的信道预约窗中将新近预约的时隙标记为“已被预约”。
具体来说，产生出mA个退避计数器初值后，A将它们填写到相应的退避计数器中(即从1号退避计数器到mA号退避计数器)，并在其维护的信道预约窗中将新近预约的时隙标记为“已被预约”。由于有mr个时隙在发送当前分组之前已经被预约(即已进行了标记)，因此这里只需对剩下的mA-mr个预约时隙进行标记。当前分组被发送出去后，A将以1号退避计数器的值作为新的退避初值，并依照IEEE 802.11DCF的规定完成其接下来的退避与发送操作。
步骤3：发送数据分组。将产生好的退避计数器初值填写到即将发送出去的数据分组的头信息域中，并将该数据分组发送出去。
上述检测虚拟冲突并通过预约保护时隙进行回避的方法具体包括以下步骤：
步骤1：虚拟冲突检测。
当某一通信终端检测到其他发送终端做出了和它一样的信道预约后(即均预约到了同一个信道时隙上)，则表示检测到了虚拟分组冲突的发生。
步骤2：虚拟冲突回避。
当检测到虚拟冲突发生时，该发送终端就检测其事先在该已预约时隙前后所预留的2p个保护时隙中是否有未被预约的空闲信道时隙。这样的检测过程按照距离该已被预约时隙由近到远的次序逐个进行，直到检测到一个离该已被预约时隙最近的空闲时隙为止，并将该空闲时隙作为新的预约时隙。
与上述加入空闲时隙的具体方法相对应的，设当前终端A接收到其他发送终端(如终端B)所发送的分组，并从中得到了mB个计数器初值设A所维护的当前时隙位置指针为TA，终端B所预约的时隙在A的信道预约窗中所对应的时隙位置分别为
以下用伪代码说明具体的虚拟分组冲突解决方法。其中，语句1到语句4，对应着虚拟冲突检测过程；语句5到语句8，对应着虚拟冲突回避过程。
语句1初始时，令j＝1；
语句2发送终端A取来计数器初值xB_j所对应的时隙位置TB_j，并执行px＝1；
语句3如果TB_j≠TA_i(1≤i≤mA)，则跳转至语句9；
语句4如果TB_j＝TA_i(1≤i≤mA)，表明发生了虚拟分组冲突，则进入虚拟分组冲突解决流程语句5；
语句5如果所对应的时隙为空闲时隙，A将所对应的时隙标记为其新的预约时隙，执行xA_t＝xA_t-px，并跳转至语句9；
语句6如果所对应的时隙为空闲时隙，A将所对应的时隙标记为其新的预约时隙，执行xA_t＝xA_t+px，并跳转至语句9；
语句7如果px＜p，则执行px＝px+1，并跳转至语句5；
语句8取消发送终端A在TA_i所对应时隙的分组发送。
语句9将TB_j所对应的时隙标记为已被预约状态。
语句10如果j＜mB，则执行j＝j+1，并跳转至语句2执行。
语句11结束该部分的处理。
注意，保护时隙个数2p(＞0)的选择应适中。过小的保护时隙数将降低虚拟冲突回避方法的效果。而过大的保护时隙数将降低信道的利用率。建议取p＝2为宜。
本发明的有益效果是：只有当某发送终端检测到虚拟分组冲突发生在它所预约的信道时隙上时，该发送终端才采取措施避免进一步的分组冲突的发生。对于其他发送终端来说，即便他们也检测到了虚拟分组冲突的发生(即检测到多个发送终端预约了相同的信道时隙)，如果该冲突时隙并不属于他们所预约的时隙，这些发送终端便不须采取进一步的虚拟分组冲突解决措施。这样便大幅度减小了各发送终端的运算量。如果不预留保护时隙，当系统业务量较大时，另外寻找空闲信道时隙将耗费较大的运算量，甚至有时还找不到合适的空闲信道时隙作为新的预约时隙。这样便影响了系统的性能。在本发明中，当发送终端预约一个空闲信道时隙时，需要同时保证该预约时隙的前后有一定数量的空闲时隙，即保护时隙。当发送终端检测到虚拟分组冲突发生在它所预约的信道时隙上时，该发送终端可以很快的从其预留的保护时隙中找到另一个空闲的信道时隙作为其新的预约时隙。从实现的复杂度以及运算量方面考虑，本发明提出的方法均具有明显的优势，具有更好的实用性。
下面结合附图和实施例对本发明进一步说明。
本发明解决其技术问题所采用的技术方案是：考虑一个单跳的无线局域网(如果信道通信质量良好，基本服务区“BBS(Basic Service Set)”内的所有通信终端均可以相互“听到”其他终端在信道上的传输活动)。设发送终端A正在向终端B发送数据分组An(角标“n”表示该数据分组的序号)。为了避免发生分组冲突，在发送An时，A将在其发送队列中等待发送的其他后续分组An+1，An+2，...，An+m将要使用的退避计数器初值xA_n+1，xA_n+2，...，xA_n+m插入到当前即将要发送的分组An的头部信息域中(具体预约的时隙位置可以通过这些退避计数器初值计算出来)。这样，在发送An的同时将其后续的m个分组所对应的m个退避计数器初值事先广播出去，从而起到了信道预约之目的。服务区中的其他发送终端在接收到An后，从其中提取出退避计数器初值xA_n+1，xA_n+2，...，xA_n+m，并计算出相应的预约时隙的绝对位置，从而避免在这些时隙上发送分组。通过这样的预约机制，可以保证广播的信道预约信息以很高的成功率被周边的其他发送终端所获取，进而避免分组冲突的发生。
然而，利用上述多步信道预约机制并不能避免虚拟分组冲突的发生。为了有效解决可能发生的虚拟分组冲突，针对通信终端可能处于发送分组状态或处于监听信道状态，在本发明中相应的提出了解决虚拟分组冲突的措施：当通信终端处于发送分组状态时，在将要预约的时隙前后加入若干空闲时隙；即当发送终端进行时隙预约时，该发送终端应保证所要预约的信道时隙是空闲的(即未被其他发送终端所预约)，并且该空闲时隙的前面p(＞0)个时隙和后面p(＞0)个时隙均为空闲时隙。这样，便在所预约的信道时隙前后引入了2p个保护时隙。当通信终端处于监听信道状态时，检测虚拟冲突并通过预约保护时隙的方法进行回避。
上述加入空闲时隙的方法具体包括如下步骤：
步骤1：产生退避计数器初值。为在发送终端的队列中等待发送的数据分组，分别产生出相应的退避计数器初值。产生这些初值的时候，应保证其所对应的信道时隙及其前后2p个信道时隙均是空闲的。
具体来说，考虑一个发送终端A，当其1号退避计数器的值递减至0时，根据IEEE802.11DCF的规定，这时A将发送队列中的第一个数据分组。A在将数据分组发送出去之前，需要完成对接下来的m个分组(不包括当前将要立刻发送的分组)的发送进行预约。这样的预约是通过计算出最多m个退避计数器的初值，并伴随着当前分组的发送广播出去而完成的。
为了叙述方便，设当前要发送分组为An。假设在发送其前面分组An-i(i≥1)时，已经完成了对后续分组An+j(1≤j≤mr)的预约(也就是说，这mr个分组已有退避计数器初值与之分别相对应)。又设发送完当前分组An后，A的发送队列中还剩下mw个分组等待发送(显然mw≥mr)，因此A还需计算出min(m，mw)-mr个退避计数器初值。也就是说，在发送当前分组的同时，A总共需广播出mA＝min(m，mw)个退避计数器初值。
产生每个退避计数器初值的方法是相同的，因此这里仅说明一个退避计数器初值的产生方法。设将要产生的与i号退避计数器所对应的退避计数器初值为xA_i。已知前一个退避计数器，即第i-1号退避计数器，所预约的时隙在信道预约窗中的位置为TA_i-1。初始计算时，令q＝1。首先，在1和min[q·(CWmin-1)，(CWmax-1)]间均匀产生出一个随机数x1作为退避计数器初值(CWmin表示最小竞争窗尺寸，CWmax表示退避计数器的最大值)，即x1＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。如果该值所对应的时隙以及其前后共计2p个时隙，即时隙(TA_i-1+x1+s)mod(1024×m)(-p≤s≤p)中的任何一个时隙已被其他终端所预约，就表明产生的x1所对应的时隙不符合我们的要求，于是就再次产生出第二个随机数x2＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。如果连续L次产生出的随机数x1，x2，...，xL所对应的时隙均不符合我们的要求，则将当前的q值加1。然后利用与上面同样的方法直至产生出符合要求的值作为最终产生出的退避计数器初值xA_i。这样，i号退避计数器所预约的时隙在A的信道预约窗中的位置为TA_i＝(TA_i-1+xA_i)mod(1024×m)。
步骤2：标记已预约时隙。将产生好的退避计数器初值填写到相应的退避计数器中，并在其维护的信道预约窗中将新近预约的时隙标记为“已被预约”。
具体来说，产生出mA个退避计数器初值后，A将它们填写到相应的退避计数器中(即从1号退避计数器到mA号退避计数器)，并在其维护的信道预约窗中将新近预约的时隙标记为“已被预约”。由于有mr个时隙在发送当前分组之前已经被预约(即已进行了标记)，因此这里只需对剩下的mA-mr个预约时隙进行标记。当前分组被发送出去后，A将以1号退避计数器的值作为新的退避初值，并依照IEEE 802.11DCF的规定完成其接下来的退避与发送操作。
步骤3：发送数据分组。将产生好的退避计数器初值填写到即将发送出去的数据分组的头信息域中，并将该数据分组发送出去。
上述检测虚拟冲突并通过预约保护时隙进行回避的方法具体包括以下步骤：
步骤1：虚拟冲突检测。
当某一通信终端检测到其他发送终端做出了和它一样的信道预约后(即均预约到了同一个信道时隙上)，则表示检测到了虚拟分组冲突的发生。
步骤2：虚拟冲突回避。
当检测到虚拟冲突发生时，该发送终端就检测其事先在该已预约时隙前后所预留的2p个保护时隙中是否有未被预约的空闲信道时隙。这样的检测过程按照距离该已被预约时隙由近到远的次序逐个进行，直到检测到一个离该已被预约时隙最近的空闲时隙为止，并将该空闲时隙作为新的预约时隙。
与上述加入空闲时隙的具体方法相对应的，设当前终端A接收到其他发送终端(如终端B)所发送的分组，并从中得到了mB个计数器初值设A所维护的当前时隙位置指针为TA，终端B所预约的时隙在A的信道预约窗中所对应的时隙位置分别为
以下用伪代码说明具体的虚拟分组冲突解决方法。其中，语句1到语句4，对应着虚拟冲突检测过程；语句5到语句8，对应着虚拟冲突回避过程。
语句1初始时，令j＝1；
语句2发送终端A取来计数器初值xB_j所对应的时隙位置TB_j，并执行px＝1；
语句3如果TB_j≠TA_i(1≤i≤mA)，则跳转至语句9；
语句4如果TB_j＝TA_i(1≤i≤mA)，表明发生了虚拟分组冲突，则进入虚拟分组冲突解决流程语句5；
语句5如果所对应的时隙为空闲时隙，A将所对应的时隙标记为其新的预约时隙，执行xA_t＝xA_t-px，并跳转至语句9；
语句6如果所对应的时隙为空闲时隙，A将所对应的时隙标记为其新的预约时隙，执行xA_t＝xA_t+px，并跳转至语句9；
语句7如果px＜p，则执行px＝px+1，并跳转至语句5；
语句8取消发送终端A在TA_i所对应时隙的分组发送。
语句9将TB_j所对应的时隙标记为已被预约状态。
语句10如果j＜mB，则执行j＝j+1，并跳转至语句2执行。
语句11结束该部分的处理。
注意，保护时隙个数2p(＞0)的选择应适中。过小的保护时隙数将降低虚拟冲突回避方法的效果。而过大的保护时隙数将降低信道的利用率。建议取p＝2为宜。
本发明的有益效果是：只有当某发送终端检测到虚拟分组冲突发生在它所预约的信道时隙上时，该发送终端才采取措施避免进一步的分组冲突的发生。对于其他发送终端来说，即便他们也检测到了虚拟分组冲突的发生(即检测到多个发送终端预约了相同的信道时隙)，如果该冲突时隙并不属于他们所预约的时隙，这些发送终端便不须采取进一步的虚拟分组冲突解决措施。这样便大幅度减小了各发送终端的运算量。如果不预留保护时隙，当系统业务量较大时，另外寻找空闲信道时隙将耗费较大的运算量，甚至有时还找不到合适的空闲信道时隙作为新的预约时隙。这样便影响了系统的性能。在本发明中，当发送终端预约一个空闲信道时隙时，需要同时保证该预约时隙的前后有一定数量的空闲时隙，即保护时隙。当发送终端检测到虚拟分组冲突发生在它所预约的信道时隙上时，该发送终端可以很快的从其预留的保护时隙中找到另一个空闲的信道时隙作为其新的预约时隙。从实现的复杂度以及运算量方面考虑，本发明提出的方法均具有明显的优势，具有更好的实用性。
下面结合附图和实施例对本发明进一步说明。
附图说明
图1是本发明实施例在k时刻发送终端A所维护的信道预约窗及退避计数器示意图；
图2是本发明实施例在k+1时刻发送终端A所维护的信道预约窗及退避计数器示意图；
图3是本发明实施例在k+2时刻发送终端A所维护的信道预约窗及退避计数器示意图；
图4是本发明实施例在k+3时刻发送终端A执行完虚拟分组冲突解决算法后其信道预约窗及退避计数器状态示意图。
图2是本发明实施例在k+1时刻发送终端A所维护的信道预约窗及退避计数器示意图；
图3是本发明实施例在k+2时刻发送终端A所维护的信道预约窗及退避计数器示意图；
图4是本发明实施例在k+3时刻发送终端A执行完虚拟分组冲突解决算法后其信道预约窗及退避计数器状态示意图。
具体实施方式
方法实施例：
当通信终端处于发送分组状态时：
假设采用两步信道预约的情况下，在时刻k发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图1所示。
步骤1：产生退避计数器初值。
设在时刻k，信道上没有任何发送终端发送分组。根据IEEE 802.11DCF的规定，20μs过后(即一个空闲时隙的时间过后)，系统进入新的时隙，也即相应的进入时刻k+1。时刻k+1下，发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图2所示。当前时隙位置指针指向了下一个时隙位置(即3号时隙位置)，同时1号退避计数器值减1。进一步假设在时刻k+1信道上没有任何发送终端发送分组。因此，一个空闲时隙的时间过后，系统将进入下一个时隙，即进入时刻k+2。
时刻k+2下，发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图3所示。当前时隙位置指针指向了下一个时隙位置(即4号时隙位置，该时隙位置正好是终端A所预约的时隙)，同时1号退避计数器值减至0。因此，终端A进入发送当前数据分组状态。发送当前分组之前，A已对10号时隙进行了预约，因此这里A只需再计算1个预约时隙的位置即可。初始计算时，令q＝1。首先，在1和min[q·(CWmin-1)，(CWmax-1)]间均匀产生出一个随机数x1作为退避计数器初值(令CWmin＝31，CWmax＝1024)，即x1＝uniform(1，min[q(CWmin-1)，(CWmax-1)])。设x1＝20，其所对应的时隙位置为(10+20)mod(1024×2)＝30，设该时隙已被其他终端所预约，于是就再次产生出x2＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。设x2＝3，其所对应的时隙位置为(10+3)mod(1024×2)＝13。设位置为13的时隙还未被其他发送终端所预约且其前后各拥有p＝2个空闲时隙(可以作为保护时隙)，因此x2＝3便是产生出的新的退避计数器初值。
步骤2：标记已预约时隙。
2号退避计数器的值复制到1号退避计数器中，而新近产生的退避计数器初值x2＝3写入2号计数器中(并将相应的13号时隙标记为已被预约状态)。当前分组被发送出去后(不论该发送过程是否成功)，A将以1号退避计数器的值作为新的退避初值，并依照IEEE 802.11DCF的规定完成其接下来的退避与发送操作。
步骤3：发送数据分组。
将产生好的退避计数器初值(分别为6和3)填写到即将发送到数据分组的头信息域中，并将该数据分组发送出去。
当通信终端处于监听信道状态时：
设在时刻k+3，终端A监听到终端B所发送的分组，并从中得到了2个计数器初值(分别为xB_1＝3和xB_2＝5)。A所维护的当前时隙位置指针目前指向的时隙位置为TA＝5，终端B所预约的时隙在A的信道预约窗中所对应的时隙位置分别为TB_1＝(5+3)mod(1024×2)＝8和TB_2＝(5+3+5)mod(1024×2)＝13。
步骤1：虚拟冲突检测。
首先，A终端检测TB_1＝8是否和其预约的时隙位置相同(即是否和TA_1＝10或TA_2＝13)。显然，TB_1不等于TA_1和TA_2，于是将TB_1＝8所对应的8号时隙标记为已被预约状态。
再次，A终端检测TB_2＝13是否和其预约的时隙位置相同(即是否和TA_1＝10或TA_2＝13)。因为，TB_2＝TA_2，表明在A和B间发生了虚拟分组冲突。
步骤2：虚拟冲突回避。
为了解决该虚拟分组冲突，A检测时隙TB_2，-1＝(TA_2-1)mod(1024×m)＝12是否为空闲时隙。由于第12号时隙为空闲，因此A将其标记为已被预约状态，并修正其第2号退避计数器xA_2＝xA_2-1＝2。之后，A将TB_2所对应的第13号时隙标记为已被预约状态。以上操作结束后，A的信道预约窗以及退避计数器的状态见图4所示。
仿真结果：
下面，通过仿真结果给出本方法所能达到的技术效果。在仿真中，系统主要参数设置参照了IEEE 802.11b的规定。在IEEE 802.11b中，MAC头信息+FCS(帧校验序列)＝224比特。在本方法中还需要附加10×m+3比特的数据域用来广播发送终端对信道时隙的预约信息(数据帧的格式定义参见发明专利申请200710017816.5相应部分的详细说明)；PHY头部开销＝192μs；ACK＝112bits+PHY头部开销；信道传输速率R＝11Mbps；信道传输延迟＝1μs；空闲时隙长度σ＝20μs；SIFS长度＝10μs；DIFS长度＝50μs。仿真中所有数据分组的有效数据载荷为2000字节，最小竞争窗尺寸为31，所有无线信道的分组传输差错率均设置为Perr＝30％。最大信道预约步数m取值为2。
表一和表二对比了Choi J.博士提出的虚拟分组冲突解决方法和本发明专利给出的方法(采用p＝2)的性能对比。表一给出了在不同发送终端数下两种方法所能达到的通过率性能对比。表二给出了在不同发送终端数下两种方法所对应的分组发送失败概率。可见本专利所提出的虚拟分组冲突解决方法可以达到更高的通过率和更低的分组冲突概率(特别是当网络用户数较多的情况下)。从实现的复杂度以及运算量方面考虑，本专利提出的方法均具有明显的优势。可见本虚拟分组冲突解决方法具有更好的实用性。
发送终端数 Choi J.的方法 本专利的方法 10 0.531401 0.522439 20 0.534601 0.531066 30 0.531894 0.531636 40 0.524856 0.534792 50 0.516308 0.532241 60 0.507133 0.532241 70 0.501124 0.533281 80 0.492789 0.533650 90 0.486299 0.535955
表1系统通过率对比
发送终端数 Choi J.的方法 本专利的方法 10 0.303065 0.302871 20 0.312973 0.302708 30 0.327990 0.306725 40 0.351629 0.304933 50 0.375617 0.310854 60 0.396254 0.313262 70 0.414970 0.312970 80 0.432011 0.313642 90 0.446874 0.311381
表2分组发送失败概率对比
当通信终端处于发送分组状态时：
假设采用两步信道预约的情况下，在时刻k发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图1所示。
步骤1：产生退避计数器初值。
设在时刻k，信道上没有任何发送终端发送分组。根据IEEE 802.11DCF的规定，20μs过后(即一个空闲时隙的时间过后)，系统进入新的时隙，也即相应的进入时刻k+1。时刻k+1下，发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图2所示。当前时隙位置指针指向了下一个时隙位置(即3号时隙位置)，同时1号退避计数器值减1。进一步假设在时刻k+1信道上没有任何发送终端发送分组。因此，一个空闲时隙的时间过后，系统将进入下一个时隙，即进入时刻k+2。
时刻k+2下，发送终端A的信道预约窗、当前时隙位置指针以及两个退避计数器的状态如图3所示。当前时隙位置指针指向了下一个时隙位置(即4号时隙位置，该时隙位置正好是终端A所预约的时隙)，同时1号退避计数器值减至0。因此，终端A进入发送当前数据分组状态。发送当前分组之前，A已对10号时隙进行了预约，因此这里A只需再计算1个预约时隙的位置即可。初始计算时，令q＝1。首先，在1和min[q·(CWmin-1)，(CWmax-1)]间均匀产生出一个随机数x1作为退避计数器初值(令CWmin＝31，CWmax＝1024)，即x1＝uniform(1，min[q(CWmin-1)，(CWmax-1)])。设x1＝20，其所对应的时隙位置为(10+20)mod(1024×2)＝30，设该时隙已被其他终端所预约，于是就再次产生出x2＝uniform(1，min[q·(CWmin-1)，(CWmax-1)])。设x2＝3，其所对应的时隙位置为(10+3)mod(1024×2)＝13。设位置为13的时隙还未被其他发送终端所预约且其前后各拥有p＝2个空闲时隙(可以作为保护时隙)，因此x2＝3便是产生出的新的退避计数器初值。
步骤2：标记已预约时隙。
2号退避计数器的值复制到1号退避计数器中，而新近产生的退避计数器初值x2＝3写入2号计数器中(并将相应的13号时隙标记为已被预约状态)。当前分组被发送出去后(不论该发送过程是否成功)，A将以1号退避计数器的值作为新的退避初值，并依照IEEE 802.11DCF的规定完成其接下来的退避与发送操作。
步骤3：发送数据分组。
将产生好的退避计数器初值(分别为6和3)填写到即将发送到数据分组的头信息域中，并将该数据分组发送出去。
当通信终端处于监听信道状态时：
设在时刻k+3，终端A监听到终端B所发送的分组，并从中得到了2个计数器初值(分别为xB_1＝3和xB_2＝5)。A所维护的当前时隙位置指针目前指向的时隙位置为TA＝5，终端B所预约的时隙在A的信道预约窗中所对应的时隙位置分别为TB_1＝(5+3)mod(1024×2)＝8和TB_2＝(5+3+5)mod(1024×2)＝13。
步骤1：虚拟冲突检测。
首先，A终端检测TB_1＝8是否和其预约的时隙位置相同(即是否和TA_1＝10或TA_2＝13)。显然，TB_1不等于TA_1和TA_2，于是将TB_1＝8所对应的8号时隙标记为已被预约状态。
再次，A终端检测TB_2＝13是否和其预约的时隙位置相同(即是否和TA_1＝10或TA_2＝13)。因为，TB_2＝TA_2，表明在A和B间发生了虚拟分组冲突。
步骤2：虚拟冲突回避。
为了解决该虚拟分组冲突，A检测时隙TB_2，-1＝(TA_2-1)mod(1024×m)＝12是否为空闲时隙。由于第12号时隙为空闲，因此A将其标记为已被预约状态，并修正其第2号退避计数器xA_2＝xA_2-1＝2。之后，A将TB_2所对应的第13号时隙标记为已被预约状态。以上操作结束后，A的信道预约窗以及退避计数器的状态见图4所示。
仿真结果：
下面，通过仿真结果给出本方法所能达到的技术效果。在仿真中，系统主要参数设置参照了IEEE 802.11b的规定。在IEEE 802.11b中，MAC头信息+FCS(帧校验序列)＝224比特。在本方法中还需要附加10×m+3比特的数据域用来广播发送终端对信道时隙的预约信息(数据帧的格式定义参见发明专利申请200710017816.5相应部分的详细说明)；PHY头部开销＝192μs；ACK＝112bits+PHY头部开销；信道传输速率R＝11Mbps；信道传输延迟＝1μs；空闲时隙长度σ＝20μs；SIFS长度＝10μs；DIFS长度＝50μs。仿真中所有数据分组的有效数据载荷为2000字节，最小竞争窗尺寸为31，所有无线信道的分组传输差错率均设置为Perr＝30％。最大信道预约步数m取值为2。
表一和表二对比了Choi J.博士提出的虚拟分组冲突解决方法和本发明专利给出的方法(采用p＝2)的性能对比。表一给出了在不同发送终端数下两种方法所能达到的通过率性能对比。表二给出了在不同发送终端数下两种方法所对应的分组发送失败概率。可见本专利所提出的虚拟分组冲突解决方法可以达到更高的通过率和更低的分组冲突概率(特别是当网络用户数较多的情况下)。从实现的复杂度以及运算量方面考虑，本专利提出的方法均具有明显的优势。可见本虚拟分组冲突解决方法具有更好的实用性。
发送终端数 Choi J.的方法 本专利的方法 10 0.531401 0.522439 20 0.534601 0.531066 30 0.531894 0.531636 40 0.524856 0.534792 50 0.516308 0.532241 60 0.507133 0.532241 70 0.501124 0.533281 80 0.492789 0.533650 90 0.486299 0.535955
表1系统通过率对比
发送终端数 Choi J.的方法 本专利的方法 10 0.303065 0.302871 20 0.312973 0.302708 30 0.327990 0.306725 40 0.351629 0.304933 50 0.375617 0.310854 60 0.396254 0.313262 70 0.414970 0.312970 80 0.432011 0.313642 90 0.446874 0.311381
表2分组发送失败概率对比