（信号与信息处理专业论文）uhf+rfid多标签防碰撞算法的研究与性能分析.pdf

山东大学博士学位论文 摘要 由于射频识别( 1 江i d ) 电子标签具有非接触、非可视读取、操作距离远、可 靠性高、安全性好、存储介质容量大、便于和企业管理信息系统( m i s ) 集成等优 点，使其被广泛应用于各种信息化系统中，并成为物联网( i o t ) 中用于标识物体， 实现物体身份识别的关键技术之一。 在标签密集的r f i d 应用系统中，常常存在过多的标签冲突。这些冲突的存在 严重影响了l 珂i d 阅读器的标签吞吐率以及整个l 讧i d 应用系统效率的提高。为完 成对标签信息的正确读取，阅读器必须使用防碰撞算法。阅读器所采用防碰撞算 法的性能将成为影响其标签吞吐能力的关键因素。故此，多标签防碰撞算法在标 签密集r f i d 系统中具有十分重要的地位。 多标签防碰撞算法的研究是i 江i d 关键技术研究领域中的一个研究热点，也是 未来i 心i d 技术和物联网应用中的一个重要研究课题。由于被动超高频l 玎i d 标签 具有被动和反向散射调制等特点，使其防碰撞算法受到更多的条件制约，从而使 超高频r f i d 防碰撞算法的研究成为l 讧i d 系统研究中的难点。 本论文对被动式超高频i 江m 系统的多标签防碰撞这一难题做了广泛而又深 入地研究。 本论文首先在查阅了大量国内外有关技术文献的基础上，对超高频r f i d 系统 多标签防碰撞问题的研究现状进行了系统综述。然后，本文对r f d 系统的通信模 型及链路预算以及有关标准情况做了简要介绍。从第三章开始，本论文对1 1 ) m a 类型防碰撞算法进行了集中分析，并提出了一些自己的改进算法。如：为克服当 前d f s a 算法中的标签估计算法存在的问题和缺陷，提出了前向预测后向校验自 适应标签数估计算法并形成了自己的前向预测后向校验d f s a ( f p b v d f s a ) 算 法。为减少碰撞，利用位隙方法对标签进行分组，提出了基于位隙分组的f s a ( b g f s a ) 算法。为克服当前的无记忆二进制树搜索算法( b t s ) 和有记忆回退 式索引二进制树形搜索算法( 砌b s ) 所存在的缺陷，提出了基于位隙分组的二进 制树搜索算法( b g b s ) 和基于位隙分组的回退式索引二进制树形搜索算法 ( b g b s ) 。为寻求更大的标签吞吐率突破，本文对多标签数据的盲源分离方法 山东大学博士学1 立论文 进行了详细研究，形成了一种新的基于动态位隙分组的盲分离多标签防碰撞算法 ( b s d b g ) 。 本文所做创新性工作主要包含以下四个方面： ( 1 ) 提出了一种前向预测后向校验的d f s a ( 即：f p b v d f s a ) 算法 标签数量估计是d f s a 算法的核心。传统d f s a 算法中的标签数量估计算法 存在不可预测性、非自适应性、估计偏差较大等缺点。为克服这些缺点，本文设 计了一种新的前向估计反向验证标签数估计算法，并据此提出了一种新的前向预 测后向校验d f s a ( 即：f p b v d f s a ) 算法。本论文从理论上分析，并从仿真实验 上验证了该算法的性能改进。结果表明该算法比传统的d f s a 算法具有更佳的算 法效率和更好的稳定性。当设定初始时隙数为1 6 ，标签数从1 到1 0 0 之间变化时， f p b v d f s a 算法的吞吐率比传统的d f s a 算法的吞吐率提高了1 0 1 6 到3 3 3 0 。 f p b v d f s a 算法的解冲突时间也比传统d f s a 算法的解冲突时间有所下降( 详见 第3 3 节) 。 ( 2 ) 提出了一种新的位隙分组帧时隙a l o h a ( b g f s a ) 算法 f s a 算法随着标签数量的大幅增加，其标签吞吐率将急剧下降。缩小应答标 签的范围，降低阅读器查询过程中引起的标签冲突量，必将能够提高f s a 算法的 标签吞吐率。本文利用位隙算法将标签分为几个更小的标签组，利用f s a 算法实 现每个组内的标签防碰撞，将位隙算法与f s a 算法结合起来提出了一种新的位隙 分组帧时隙砧o h a ( b g f s a ) 算法。本文从理论和实验上分析该算法的性能改善程 度，结果表明该算法比传统f s a 算法能够大幅度地提高算法效率( 详见第3 4 节) 。 ( 3 ) 提出了一种新的结合位隙标签分组的b t s ( b g b s ) 算法和一种基于位 隙分组的回退式索引二进制树形搜索( 即：b g 砌b s ) 算法 当一个阅读器操作区域内的标签数少于6 个的时候，无记忆的二进制树搜索 算法算法( b t s ) 的标签吞吐率可以达到0 3 8 7 ，该吞吐率大于时隙灿o l l a 算法( s f a ) 的吞吐率o 3 6 8 。而当标签数大于1 0 个时，标签吞吐率将急剧下降。将大的标签 组分解成若干较小的标签组，使得每个标签组内的标签数小于1 0 ，然后对小的标签 组逐个进行读取，必将使其标签吞吐率比直接对所有标签操作时得到大幅提高。为此， 本文提出了一种新的1 i ) m a 类型的多标签防碰撞算法一位隙标签分组的b t s ( b g b s ) 算法，该算法将位隙分组与二进制树搜索算法算法( b t s ) 结合在了一起。 2 山东大学博士学位论文 有记忆的回退式索引二进制树形搜索( b s ) 算法具有较高的标签吞吐率和 良好的稳定性，但是需要较大容量的堆栈来存放其历史数据。所需栈区空间的大 小与组内标签数量的大小成j 下比。降低组内标签数量，必将显著降低栈区空间要 求。因此，我们提出了另一种新的t d m a 类型的多标签防碰撞算法一位隙分组回 退式索引二进制树搜索( 即：b g 对b s ) 算法。 理论分析和仿真实验表明：b g b s 算法比b t s 算法的标签吞吐率有较大幅度 的提高，b g 对b s 算法比砌b s 算法有一定程度的提高，b g b s 算法的栈区空间 比对b s 算法的栈区空间有了大幅度的降低，这对降低l 强i d 阅读器的成本是特别 有价值的( 详见第4 3 节) 。 ( 4 ) 探索了多标签混合数据盲源分离的可行性并提出了一种基于位隙动态分 组的盲分离多标签防碰撞算法( b s d b g ) 利用现代信号处理技术，特别是多天线技术来实现多标签防碰撞是r f i d 防碰 撞算法新的发展趋势，也是突破传统算法性能不高的唯一途径。本文分析了多天 线呷r f i d 系统的数学模型，通过对该模型的分析，得出多天线唧r f i d 系 统多标签混合数据完全符合独立分量分析( i c a ) 算法的约束条件。为客观评价i c a 算法对多标签混合数据盲分离的效果及算法的噪声抑制能力，本文定义了一个新 的性能评价指标源和目标相似度指标( s s r ) 。以此为依据，通过软件仿真分析 了将i c a 算法用于多标签混合数据盲分离的分离效果，以及该算法对随机性噪声 的抑制能力( 详见第5 2 至5 4 节) 。为将源信号正确地分离出来，i c a 算法要求 观测信号的数目应大于或等于源信号的数目。为满足这一要求，本文利用位隙算 法对标签进行分组，使每组内的标签数小于阅读器天线数，然后在组内再使用i c a 算法进行标签数据分离。据此，提出一种新的位隙动态分组盲分离多标签防碰撞 算法( b s d b g ) 。本文从理论上分析和实验上验证了这种算法的吞吐率完全可以超 过l ，这在传统的t d m a 类型的防碰撞算法中是不可能实现的( 详见第5 5 和5 6 节) 。 关键词：射频识别、多标签防碰撞、盲源分离、独立分量分析、阵列信号处理 3 山东大学博士学位论文 a b s t r a c t w i t ha1 0 to fe x c e l l e n t 佗a 白鹏s ，s u c h 嬲c o n t a c t - l e s s ，n o ti i i l eo fs i g h t ，l o n g o p e 均t i i l gr 锄g e ，l l i 曲r e l i a b i l i 劬h i g hs e c 埘t y ，l a 略es t o r a g ec a p a c i 够a n de 嬲i l y i n t e 蓼a t e di r n 0m i sa n d o n ，i 疆i di s 谢d e i y 瑕e di nv a r i o u s 印p l i c a t i o ns y s t e m s ，a n d b e c o m e eo fm ek e yt i e c i l i l o l o 百e si l lt l l ei n t e m e to f1 1 l i n g ( i o df o rla _ b e l i i l ga n d i d e n t i 匆i i l gn 砷啪】0 b j e c t s h lt a g i n t e l l s i v er f i da p p l i c a t i 0 璐s y 妣m ，血e r ea r eal o to ft a g sc o l l i s i o 嬲n e s e c o l l i s i o i 坞h a 、，ee v i le 伍曲t so ni i l c r e 硒i n gt l l er e a d e r st a gt 1 1 r 0 咖u t 锄do ni 1 p r 0 v i i l g m e 脾f o 咖锄c co fm ew h o l er f i da p p l i c a t i o ns ) r s t c i n h lo r d e rt 0r e a di m n l l a t i o n p r o p e r l y 丘0 mt h e s et a g s ，t l l er e a d e rm u s ta d o p ta na n t i c 0 1 l i s i o na l g o r i t l n o n eo fm e c r i t i c a l i n 皿l l e i l c i i l gf k t o 璐o ft h er e a d e r st a gm m u g h p u ti sm ep e r f o m l a i l c eo f l e 觚t i - i c o l l i s i a 1 9 0 r i t h mi tl l s e d 1 k r e f o r e ，t l l em u l t i t a ga n t i c o l l i s i o na 1 9 0 r i m mp l a y sa v e 巧i i i l p o r t 锄tr o l ei i lt a g i n t e 璐h ei 强i da p p l i c a t i o ns y s t e m m u l t i - t a j g 锄t i c o l l i s i 衄a l g 埘n 衄i s i 1 1 9a 矗啷i 1 1m el 强i dk e yt e c h n o l o g ) ， r e s e a r c ha r e 如a n db e c o i i l i n go n eo ft 1 1 em o s ti m p o r t a i l tr e s e a r c ht o p i c si i lr f i d 觚d i n t e m 或o f g sa p p l i c a t i o n b e c a u s eo fm cp 懿s i v e 肌dt h eb a c k s c a n e rm 0 姒a t i o n 锄：t u r e so fu h fr f i dt a g ，舭孤t i c o l l i s i o na l g o r i 缸lo fu h fr f i ds y s t e mi sp u ti i l m a n yc o n s t r a i l l s ，觚db e c o m e sm em o s td i 伍c u l ts u b j e c tm r f i dr e a r c h 锄瓿 w r ei l l t e n dt 0m a k e 觚e x t e i l s i v er e a r c h 觚dd i gad e e p c ri i l t 0t l l e s o p l l i s 廿c a t i e d 哪i 强i dm u l t i 砌g 锄t i 啪l l i s i o na k o r i t l l i n s f i 硎y ，ac o m p r e h e i l s i v er e v i e wo f 舭蛐o f 砷o fu h fr f i dm u l t i t a g 锄t i c o l l i s i o na l g o r i 岫si s 西v 既o u t t l l eb a s i so fc o i l s u l t i n gp l e n 够o fd o m e s t i c 锄d f 0 r e i g nr e l a t e dl i t e 珀t u r e s t h e 玛t l l ec o m m u i i i c a t i o nm o d e l ，l i i l kh l d g e ta n ds t 锄d a r d so f u h fi 心i ds y s t e ma r ed e s c r i b c d s t a n 丘d mt h cc h a p t c r3 ，t d m a t ) ，p ea n t i c o l l i s i o n a 1 9 0 r i t l l i n sa r ei l l t e 璐i v e l y 锄m y z e d ，锄ds 0 m ei l i l p m 、司a l g o r i m m sa r ep r 0 】p o s e d ，s u c h 嬲：t h ef o ，a r dp r e d i c t i o nb 犹h v a r dv e r i f i c a t i o nd f s a ( f p b v d f s a ) a l g o r i m mf o r o v e r c o m i i 培廿l ed e f e c t so fc u r r e n t 由r i l a m i ct a g sn 啪b e re s t i m a t i o na l g o r i t h m si l ld f s a b y 印p l y i i l gaf o n ) 旧r dp r e d i c t i o nb a c k w a r dv e r i f i c a t i o n 敷畸p t i v ea l g o r i t l m lt 0 “；硼忙 b i t - s l o tg r o u pf s a ( b g f s a ) f o rr e d u c i i l gt l l ec o l l i s i o nb y 惦i n gb i t - s l o tg r o u pm e t h o d ； t kb i t - s l o tg r o u pb i n a d ，一n 优s e a r c h ( b g b s ) 锄db i t - s l o t 印u pr e g r e s s i v ci i l d e x b i n a 巧一骶es e a r c h ( b g m b s ) f o rr e m e d y i n g 枞a c l ( so fm e m o 巧一l e s sb i 彻巧n 4 山东大学博士掌位论文 s e a r c h ( b t s ) a l g o r i t h m 锄dm e m o 巧r e g r e s s i v ei n d e xb i n a 巧一t r e es e a r c l l i n g ( b s ) a l g o r i t 王l m i no r d e rt o g e tg r e a tb r e a l m u o u g h 证t a gt l l r o u 曲p u t o fm u l t i t a g 锄“一c o l l i s i o na j g o r i t l l | n ，t h ef e a s i b i l 时o fa p p l y i n gb l 砌s o u r c e p 删i o nt om u l t i 恤 h y b r i dd a t ai se x p l o r e d ，锄dan o v e lb “n ds e p a r a t i o nd y n 锄i cb i t s l o tg r o u p ( b s d b g ) m u l t i t a ga 埘c o l l i s i o na l l g o r i m mi sp “ p o s e d t h ei n n o v a t i o l l si i lt 址sm e s i sa l s u n u n a u r i z e da sf o u o w s ： 1 an o v e lf o r w a r dp 他d i c t i o nb a c k w a r dv e r i n c a “o nd y n a m i cf a m es l o t t e d a l o h a ( i i p d f s a ) a l g o t h mi sp m p o s e d n 啪b e re s t i i l l a t i o na j g o r i 吐皿i s 恤c o r eo fd f s a 删i t i o i l a lt a gn 啪b e r e s t i m a t i o nd l g o r i m m sh a v em 觚yd 胁b a c l 【ss u c h 嬲u i l p r e d i 嘞b l e ，肿n - a d a p t i v e ，l a r g e e s t i m a t i o nd e v i a t i o n 锄d o n f o ro v e 啪m i n gt l l e a c k s ，w ed e s i 盟e dan o v c l f o r w a 柑p r e d i c t i o n锄db a c 洲 v c r i f i c a t i o n d y 加i i l i c魄sn 啪b c re s t i m a t i o n a l g o r i t l l 】【n 锄db 筋e d彻n l i s a l g 谢t l l m ， an o v e lf i o 刑a r dp r e d i c t i o nb a c v e r i f i c a t i o nd y n 锄i c 仔锄es i o t t e da l o l l a ( f p d f s a ) a j g o r i t l l mi s p r o p o s e d 1 k e 伍c i e i l c yo ff p d f s ai s 锄a l y z c di i lt 1 1 e o r y 觚dv e r i f i e di i ls i m u l a t i o ne x p e 也e n t ，趾l da p e 疵c tr e 锄nt i l a tf p d f s ah a s al a 玛e rt a gt h r o u g l l p u ta n dab e 舵rs t a r b i l 时t h 狃 c l 弱s i c a ld f s aw 嬲o b t a i l l c d w 旮【ht l l es t a n i i l gs l o t si m m b c rl6 ，t h et a gn 啪b e rv a r y i n g 五r o m1t 0l o o ，m et a g st l l m u 曲p u to f f p d f s ai m p r o v e sl o 1 6 t 03 3 3 0 t i md f s a a n d ，此劬e 嘲u i r o d f o rr e s o l v i n gt a g sc o l l i s i o nu s i i l gf p d f s ai s 锄d l e rt l l 觚i l s i n g d f s a ( s e es e c t i o n3 3 ) 2 an o v e i b i t - s l o tg m u p e d 舨m es i o t 舢o h a ( b g f s a ) a l g o r i t h mi sp m p o s e d n e 切gt h r o u 曲p u to ff s aa l g o r i t l l i i l 淅l ld e c l 砘泖i d l y 删l e 舭魄舢n b e r 妇r e 弱e ss i 嘶f i c 锄t l y 1 1 1 et a gt 量d u g h p u to ff s ac 趾b ei l i l p r o v e dd e 觚t e l yb y 咖诚n g l es c o p eo fr e s p o n d 面唔t a g s 雒dr e d u c i n g 也e l l i s i o n 缸l u c e db y l e r e a d e r t si n v e n t o b yl l s i l l gt h eb i t s l o ta l g o r i t l l m ，a l lo f 1 et a g sa r es e p 鼬t e di n _ t 0 v e r a lg r o u p s u s i i l gn l ef s a ，a n t i c o l l i s i o no ft a g s 埘t l i ne a c h 伊o u pc a i lb ea c 如e v e d c o m b i l l i l 坞廿l eb i t s 1 0 ta l g o r i t h m 谢t l l 妇h cf s aa l g o r i t l u nt o g e t h e r ，an o v e lb i t - s 1 0 t g r o u p e d 舳m es l o t 舢o l l a ( b g f s a ) a l g o 枷蛐i sp r o p o s e di n “s 吐l e s i s n l ee m c i 明c y o fb g f s ai s 鲫甜y z e di i lp r i i l c i p l ea n de x p 甜m e n t nh 嬲b e e ns i 鲥f i c 锄u yi i i l p r o v e d 姗恤to f f s a ( s e cs e c t i o n3 4 ) 3 an o v e lb i t - s l o tg m u pb i n a i y t r e es e a r c h ( b g b s ) a n dan o v e lb i t s l o tg i - o u p r e g n s s i v ei n d e xb i n a r y - t r s e a k h ( b g r 噶s ) a i g o r i t h m sa mp 阳p o s e d 5 山东大学博士学位论文 w h e nt l l et a gn u m b e ri nar e a d c r so p e r a t i n ga r e ai sl e s st 1 1 a n6 ，t h et a gm r o u 曲p m o fm em e m o d ，1 e s sb i 彻r y 仃e es e 锄c h ( b t s ) c 觚眦h0 3 8 7 ，w l l i c hi sb 追g e rm 锄t h e t a gt l l r o u 曲p u to fs f ao 3 6 8 w h e i lt h et a gn 啪b c ri sb i g g c rt l 姗1o ，t l l et a gm r o u g h p u t 、航nd e c r e 嬲es i g l l i f i c a n t l y b r e a 姑n ga b i gt a g 孕- 0 u pd o w n i n t os e v e r a ls m a l lt a g 目- o u p s ， 锄dr e l d i i l gc v e 巧s m a l lg r o u ps 印被l t e l y ，t l l e 缸唱岫u 曲p u tc 觚b ei l i l p r o v e d 鲫，a t l y 姗l a to f r e a d i i l ga l lt a gi i lab 追毋- 0 u pd i r e c t l y s o ，w ep r o p o s e dan e wd e t e m “s t i c t d m am u l t i 乇喀a n t i c o l l i s i o 璐a l g o r i 廿l l nb i t - s l o t 舯u pb i 彻r y 一仃e e a r c h ( b g b s ) ， w l l i c hc o m b i n e db i t - s 1 0 tg r o u p 、) 1 7 i n lb i i l 乏町缸优s e a r c h ( b t s ) a l g o r i t l l m m e m o 巧r e g r e s s i v ei n d e xb i 彻r y m s e a r c i l i n ga i g o r i t h m ( b s ) h 弱al l i g h e rt a g 曲r o u 曲p m 锄dp 耐e c ts 协i l i 吼b l ni tn e e d sab i gm 锄。巧s t a c l 【t 0s t o r ei t sl l i s t o 巧 i i l v e n t o r y 协t h es i z eo fm e m o r ) rs t ；虬ki sp r o p o n i o r l a it o l et a gm 皿b e ri na 孕o u p d c c r e a s i n g 廿l et a gn 眦b e ri na 毋0 u pc a nm 血砌l yr e d l l c e 圮s t a c ks i z e s o ，w e p r o p o s e d 锄o l e rm wd 嗽腿l i i l i s t i ct d m am u l t i - t a ga n t i c o l l i s i o n sa 1 9 0 r i t h i nb i t - s 1 0 t g r o u pr e g 陀s s i v ei l l d e xb i l l 芒l 驴缸优s e a r c h ( b g 砌b s ) ，、；l 倾c hc o m b i n e db i t - s l o tg r o u p 诵lr e g r e s s i v ei i l d e xb i i l a 】叮仃e e a r c h ( b s ) 1 k o r e t i c a l 锄a l y s i sa n ds i m u l a t i o nr e s u l t ss h o w t 1 1 a t ：t l l et a g d u 曲p u to fb g b s a l g o r i 廿l r nh 嬲as i 鲥f i c a n ti i l l p r 0 v 锄e n t m 衄o f b t s a 1 9 0 r i t l l i n n et a gt l l r o u g h p u t o fb g 砒b sa l g o r i t 量吼h a sb e e ni m p r o v e dt 0s o m ee x t e n tm 锄t 1 1 a to f 砌b s 出g o r i t h r 璐 t h es t a c ks i z eo fb g b sa l g o r i t h mi sm u c hl e s st l l 锄t l 斌o f 融b sa l g o r i t l l m ，w l l i c hi s p a r t i c u l a r l yv a l u a b l et 0r e d u c e 吐l ec 0 s to fr f i dr e a d e r ( es e c t i o n4 3 ) 4 t h ef e a s i b m 够o fa p p l y i n gb l i n ds o u 心es e p a n t i o na l g o r i t h mt om u l 昏t a g h y b r i dd a t ai se x p i o r e da n dan o v e ib i i n ds e p a r a t i o nd y n a m i cb a s e do nb i t - s l o t g m u p ( b s d b g ) a l g o t h mi sp m p o s e d a p p l y i n gm o d e ms i g i l a lp r o c e s s i i l gt e c h n o l o g y ，e s p i e c i a l l ys m 砒锄t 朗n a 龇l da 1 1 r a y s i 印a lp r o c e s s i n gt e c l l i l o l o g yt om u l t i - t a g 锄t i - c o l l i s i o na l g o r i t l l mi sai 坞w 仃e n di l ln l e r f i d 锄t i - c o l l i s i o na l g o r i 1 n 1r e s e 砌a r e a 锄di ts e e i i l st ob e 位o i d yw a yf o rm a k j n g ag r e a tb r e a k t h r o u 曲i ne 衔c i 饥c yo f 跏i t i o 砌a l g o r i t l l i n t h e 咖l t i - 锄t e n 瑚u h f i 己f i ds 弘i t e mm o d e li sa n a l y z e di nt l l i sn l e s i s w 色h a ：v eg o tap e r f c c tc o n c l u s i o n l a = t m u l t i t a gh y b r i dd a l ao ft h eu 球r f i dm u l t i - a n t e n n as y s t e mc o m p l c t e l ym e e t 也e r e q u i r e i n e n t so f 坨砌e p e n d e n tc 0 m p o n e n t 锄a l y s i s ( i c a ) a l g o r i l i n f o ro b j e c t i v e l y e 、谢u a t i i 培也ee 伍c i c y 锄dn o i s es u p p 陀s s i o ne 氐c to fm u l t i t a gh 姗dd a 臆b l i n d 嗣捌瞰i o ni c aa l g o r i 廿蛐，an e wm e a s u 曲l ei i l d i c a o r 一l es i m i l 撕t yo fs o 瑚c e 锄d 6 山东大学博士学1 立论文 r e s u l t ( s s r ) i sd e f i n e d b yu s i n g 也t l l ee 伍c i e n c y 卸dn o i s es u p p r e s s i o ne 毹c to ft l l i s a j g o r i t h i ni s 锄a 1 ) 亿e di i ls i m u l a t i o ni i l “st l l e s i s ( s e es e c t i o n 5 2t 0s e c t i o n5 4 ) f o f s e p a m t i n gs o u r c es i 印a l sp r o p e r l y ，i c aa l g o r i 吼r e q u h sm eo b s e r v e ds i g i l mn u m b e r l l a v et 0b eg r e a t e rt h 觚t 1 1 a to ft l l es o u r c es i 印a l ，h lo r d e rt 0m e e tt h j sr e q u m e 咄 d y n 锄i cb i t s l o ta 1 9 0 r i m mi s 哪e dt o p a r a t ea l lt a g si n t 0 v e r a lg r o u pt 0e i l s u r em e t a g s 跏l i n b e ri i lag r o u pi ss m a l l e rt l l 孤t l l e 锄眙m m sm l m b e ri i lam u i t i 一锄t e m 阻r f i d s y s t e r i l ，a l ei c aa l g o 酬 l l l li su s e dt 0f h l f i l lm u l t i 一切喀锄t i c o l l i s i o ni nag r o u p b 嬲e d 叩 m e m 甜l o d s ，an o v e lb l i i l ds e p a r a t i o nb 蹦甜o nd y n 锄i cb i t s l o t 印u p ( b s d b g ) a l g o r i 廿l i ni sp r o p o s e d 1 ke 伍c i e n c yo f “sa i g o r i t h mw l l i c hi sv e r i f i e di i lp r i i l c i p l ea i l d e x p e 血1 e n ti sb i g g e rt l l 锄l ，b u ti ti si m p o s s i b l ef o r 伽i t i o l l a lt 【) m aa n t i c o l l i s i o n a l g o d t l l m ( s e es e c t i o n5 5 锄ds e c t i o n5 6 ) 1 畸w o r d s ： i 己a d i of r e q u e n c yi d e n t i f i c a t i o n ；m u l t i t a ga n t i - c o l l i s i o n ；b l i n ds o 硼c es 印硼l t i o n ； i n d e p e i l d e n tc o m p o n e n ta i 词y s i s ；a r r a ys i 孕l a lp r o c e s s i n g 7 山东大学博士学位论文 c o n t e n t s d e s c r i p t i o no f a b b r e v i a t i o 船锄ds 邺b o l s 一8 c 哦r1 1 1 1 们d l l c t i o n 1 4 1 1 b a c k 印u i l d 1 4 1 2 r e c e n t p 哪s so f l 强i d a m i c o l l i s i o n 舢9 0 r i l m s 1 9 1 2 1 f r e q u e n c yd i v i s i o nm u l t i p l ea c c e s 卜_ f d m a 1 9 1 2 2c o d ed i v i s i o nm u l t i p l ea c c e s “d m a 1 9 1 2 3t i m ed i v i s i o nm u l t i p l ea c c 鼯d m a 2 0 1 2 3 1 s t o c h 枷c 灿g o r i m m s 2 l 1 2 3 2 d e t e 册i n j s t i c g o r i t h m s 2 3 1 2 3 3 h y b r i d 灿g o r i m m s 2 7 1 2 4 s p a c cd i v i s i m u l t i p l ea c c e s 卜s d m a 2 7 1 3 s i 鲥f i c a i l c eo f m er e s e 撒h 锄d o l l ri i i l p v e dw b r k s 2 9 1 3 1 s i 嘶f i c 觚c eo fm er e a r c h 2 9 1 3 2o u ri m p r o v e dw o r k s 3 0 1 4m s i so 穆a i l i z a t i o n 3 l c h a p t e r2p r i n c i p l e sa n d 量时t e c l l n o l o g i e so f 哪i 心i ds y s t e m 3 3 2 1 c o m p o n e n t s 锄dc l 硒蚯c a t i o no fr f i ds y s t e m 3 3 2 1 1 c o m p o n e n t so f i 强i ds y s t e m 。3 3 2 1 2c l a s s f i c a t i o no f r f i ds y s t c 胍。3 4 2 2 s y s t e m1 h n s m i s s i o nm o d e la i l dl i i l l 【b u d g e to fu h fr f i d 3 5 2 2 1s v 咖lt r 哪血s s i o nm o d e lo f u h fr f i d 3 5 2 2 - 2 l i i l l 【b u d g c to f u 耶r f i d 3 6 2 3 u h fr f i ds t 觚d 矾s 觚dk e yt e c h n o l o 西e so fe p cg l o c 1 g 2 3 9 2 3 1 p h y s i c a lc 0 d i n gt e c l l l l o l o g ) ri ne p cg l o 砌c 1 g 2 4 1 2 3 2m e d i aa c c e s sc o n 们l i ne p cg l o b a lc l g 2 4 6 2 3 2 1m e d i aa c c e 豁c o n 仃0 l qp r o t o c o l 4 6 2 3 2 2 “n kt i m i l l g 4 7 山东大学博士学位论文 2 3 2 3 l i i l l ( s p e e d 4 8 c l 即t e r3 f o 刑a r dp r e d i c t i o nb