基于移動通信數(shù)據(jù)的用戶移動軌跡預(yù)測方法

1、第 30 卷第 2 期2013 年 2 月vol. 30 no 2feb 2013計算機應(yīng)用與軟件computer applications and software基于移動通信數(shù)據(jù)的用戶移動軌跡預(yù)測方法震1付俊輝1楠2劉趙1 ( 河南科技學(xué)院網(wǎng)絡(luò)信息中心 河南 新鄉(xiāng) 453003)2 ( 北京大學(xué)信息科學(xué)與技術(shù)學(xué)院 北京 100871)隨著無線移動通信設(shè)備的發(fā)展，獲取用戶位置的手段更加多樣，如何對軌跡進行建模并預(yù)測人類行為成為研究熱點?，F(xiàn)摘 要有方法主要針對 gps 軌跡等連續(xù)軌跡進行建模預(yù)測，而對移動通信場景中人行為軌跡預(yù)測方法尚未研究。針對移動話單數(shù)據(jù)這種離散程度極大的軌跡數(shù)據(jù)建模，提出

2、 match 算法對人類軌跡進行預(yù)測。實驗證明，85% 的人類軌跡可以利用該算法正確預(yù)測。在此 基礎(chǔ)上，提出軌跡合并的方法，進一步提高了預(yù)測的準確率，并發(fā)現(xiàn)人類在以天為單位的尺度上，有 30% 的行為是自相似的。關(guān)鍵詞移動數(shù)據(jù) 軌跡預(yù)測 行為分析中圖分類號 tp311文獻標識碼 adoi: 10 3969 / j issn 1000-386x 2013 02 003users mobile track prediction method based on mobilecommunication dataliu zhen1fu junhui1zhao nan21 ( network inform

3、ation center，henan institute of science and technology，xinxiang 453003，henan，china)2 ( school of electronic engineering and computer science，peking university，beijing 100871，china)with the development of wireless mobile communication devices，there are diverse means to obtain userslocation，and theabs

4、tractways to model the track as well as to predict the human behaviours become the focus of the research existing means are mainly aiming at con-tinuous trajectory like gps track to model and predict，but for predicting human behaviour tracks in the scene of mobile communication，it istill the blank y

5、et in this paper，aiming at modelling the mobile calling list data，which is a kind of track data with very large discrete degree，we propose match algorithm to predict human tracks experiment proves that 85% human tracks can be correctly predicted with thisalgorithm on this basis，we then propose a met

6、hod of tracks merging，which further improves the accuracy of prediction moreover，it is found that 30% of the human behaviours are self-similar taking the day as the scale of human beingskeywordsmobile data trajectory predicting behaviour analysis效的預(yù)測模型。所以，移動通信場景下的移動軌跡預(yù)測成為一個尚未解決的難題。本文提出了一個新的對離散軌跡進行建模

7、預(yù)測的方法。首 先，將話單數(shù)據(jù)所反映的離散軌跡轉(zhuǎn)換為連續(xù)軌跡得到用戶行 為模式，基于該行為模式提出了軌跡預(yù)測算法 match，實驗證 明，使用該算法有 85% 的人類行為可以預(yù)測。通過對歷史相似 軌跡進行合并，更加準確地刻畫了用戶的真實軌跡，進一步提高 了預(yù)測準確率。并得出結(jié)論: 在以天為單位的尺度上，人類的行 為有 30% 是自相似的。0引言隨著移動電話的普及以及 3g 網(wǎng)絡(luò)的部署，移動網(wǎng)絡(luò)中基于位置 信 息 的 服 務(wù) ( lbs ) 越 來 越 成 為 熱 點。 如 日 本 的 ntt docomo 推出個人用戶定位和導(dǎo)航服務(wù)，美國的 verizon 主推 family locator

8、服務(wù)以及歐洲的 vodafone 等推出了團隊位置跟 蹤服務(wù)等; 還如 mit 的 mobile landscapes 項目使用移動通話數(shù) 據(jù)得到靜態(tài)城市人群時空分布，real time rome 項目的實時監(jiān) 測人群密度動態(tài)分布等。基于移動位置信息的研究和應(yīng)用正成 為全球?qū)W術(shù)界和產(chǎn)業(yè)界共同關(guān)注的焦點問題。當前，與移動位置相關(guān)的行為研究的熱點問題之一是對移 動用戶未來的位置信息進行實時、準確的預(yù)測1 6。然而，當前 對用戶未來位置的預(yù)測研究主要集中在對連續(xù)軌跡( 典型代表 是 gps 軌跡) 建模的基礎(chǔ)上，如文獻1 3。然而，此類研究難 以預(yù)測移動通信場景下的用戶軌跡。因為在該場景下，用戶軌

9、跡十分離散，一天平均只能獲得十幾個用戶軌跡點，現(xiàn)有模型難相關(guān)工作1由于使用的定位手段不同，對人類軌跡的建模方式以及預(yù)測方法也有不同。gps 定位精度最高，通過內(nèi)置的客戶端，可以 獲得用戶的連續(xù)軌跡，基于此種數(shù)據(jù)的研究也最多。從預(yù)測方收稿日期: 2012 05 17。國家自然科學(xué)基金項目( 60703066 ) 。劉震，實驗師，主研領(lǐng)域: 網(wǎng)絡(luò)通信與管理。付俊輝，講師。趙楠，碩士生。以根據(jù)如此離散的軌跡反演得到用戶的歷史行為，并建立起有式上，主要有兩種方式: 基于 dynamic bayesian network 等網(wǎng)絡(luò)學(xué)習(xí)模型對軌跡建模并預(yù)測，如文獻1 3等; 另外，基于歷史 軌跡頻繁項的軌跡

10、預(yù)測研究也比較多，其中以文獻4為代表。 作者假設(shè)，由于城市中公共交通發(fā)達，多數(shù)人的出行方式應(yīng)該相 同。將多數(shù)人運動的軌跡重合部分，作為對軌跡預(yù)測的依據(jù)。 但是，個人 gps 軌跡數(shù)據(jù)難以得到，一般由志愿者提供，樣本數(shù) 量很少，難以大規(guī)模開展實驗以驗證算法可靠性以及研究人類 的行為規(guī)律。利用 wifi 可將用戶定位到 wifi 基站，基站覆蓋范圍較小， 使得定位精度較高。由于 wifi 網(wǎng)絡(luò)并不普及，研究大多局限在 一個校園或一個社區(qū)之內(nèi)5，6，代表性并不強，這里不再贅述。利用移動基站定位用戶精度最低，城市中基站的覆蓋范圍 為 0 5km 5km 不等，其定位精度也在這個范圍。然而，由于手 機的

11、普及特性，因此研究基于該數(shù)據(jù)特性的軌跡預(yù)測將為大量 基于位置信息的應(yīng)用提供支持。實際中得到的用戶話單數(shù)據(jù)， 記錄了一個用戶在一段時間的通話行為，用戶位置通過話單數(shù) 據(jù)中通訊時所聯(lián)絡(luò)的基站反映出來。但用戶通話行為極其離 散，形成了離散的軌跡，如何對其建模成為難題。另外，由于涉 及用戶隱私，此種研究往往難以開展。所以在這個領(lǐng)域，開展的 研究還較少。文獻8通過在手機安裝客戶端，記錄下用戶附 近的基站信息，得到連續(xù)的軌跡。利用 dbn，對用戶的軌跡進 行預(yù)測。該研究使用了志愿者提供的信息，實際上是低精度類 似 gps 定位數(shù)據(jù)的連續(xù)軌跡預(yù)測，有著與 gps 定位進行軌跡預(yù) 測相同的缺陷。barabas

12、i 等在 nature9 上報到了他們開創(chuàng)性的研究工作。 通過與移動公司合作，作者得到了三個月 10，000，000 用戶的話 單數(shù)據(jù)。通過系統(tǒng)的分析論證，得到了任何對于人類行為進行 預(yù)測的準確率不會超過 93% 的結(jié)論，但準確率也不會低于 70%( 在后文中稱該算法為 most frequent 算法) 。但是，作者并未在 文中提出其他具體的軌跡預(yù)測方法，僅僅對在移動通信環(huán)境下 人類行為的可預(yù)測性做出上下界的定義。本文是在該文的基礎(chǔ) 上開展工作的。錯誤。定義 4 軌跡預(yù)測策略 已知序列 t1 ，r1 ， t2 ，r2 ， tn rn ( t1 t2 tn ) 以及待預(yù)測時刻 t，滿k( t

13、tk ) ，ti setti ，那么預(yù)測序列 t1 ，r1 ，t tit2 ，r2 ， ti 1 ri 1 在 ti 的位置，若使用某種預(yù)測算法到的 r = ri ，則稱預(yù)測正確; 若 r ri ，則稱預(yù)測錯誤。軌跡預(yù)測方法3手機在進行通訊時，有一定概率發(fā)生基站轉(zhuǎn)換，使得話單錄的基站位置并不能很好地反映用戶的真實位置。首先對話 數(shù)據(jù)進行修正，去除通話中發(fā)生的基站轉(zhuǎn)換。然后在區(qū)域劃 的基礎(chǔ)上得到用戶行為模式，將用戶離散的軌跡轉(zhuǎn)換為連續(xù)行為模式。基于該模式，使用 match 算法對用戶軌跡進行預(yù)測在 3 5 節(jié)還提出了軌跡合并算法，軌跡合并集較之行為模式加準確地反映了用戶歷史真實軌跡，利用軌跡合并

14、集，進一步 高軌跡預(yù)測的準確率?；巨D(zhuǎn)換手機在進行通信時，由于信號、基站容量等客觀問題，并 總是選擇距離最近的基站，使得話單記錄的基站位置并不能3 1確地反映用戶的位置，因而有必要去除通話時發(fā)生的基站轉(zhuǎn)換用戶兩次通話為 ti ，toweri ( xi ，yi ) ， tj ，towerj ( xj ，yj )( towerj towerj ，ti tj ) ，在這兩個基站間最小的移動速度為:槡( xi xj ) + ( yi yj )22vi，j=tj ti設(shè)人類移動速度的上限是 vth = 120km / h，任何基站間最移動速度高過該上限的都視作發(fā)生了基站轉(zhuǎn)換，找出話單數(shù) 中發(fā)生基站轉(zhuǎn)換的

15、記錄進行修正。3 2區(qū)域劃分用戶的一個活動區(qū)域往往包括幾個基站，將該活動區(qū)域的基站合并就可以得到用戶的一個區(qū)域。由于基站的特殊性，我們并沒有選擇常規(guī)的聚類方法。兩個活動基站的信號范圍發(fā)生重疊時( 這里使用基站距離小1 5km 作為標準) ，這兩個基站屬于同一個區(qū)域( 算法 1) 。2問題定義假設(shè) setti，j 表示移動用戶 i 在第 j 天所有開始通話時刻的集合。settoweri 是用戶 i 歷史通話中出現(xiàn)的全體基站。用戶 i 的 一次通話記作 tp ，towerp ( xp ，yp ) ，其中 tp 是通話開始時刻，tp setti，j ，( xp ，yp ) 是通話時通信基站經(jīng)緯度，t

16、owerp settoweri 。用戶 i 在第 j 天的通話行為記為話單數(shù)據(jù)集 calli，j ，表示為:calli，j = t1 ，tower1 ， t2 ，tower2 ， tn ，towern 。calli，j 是一個有序集，t1 t2 tn 。算法 1input: towerioutput: rregion division1)2)3)4)5)6)for each i，jif distance( toweri ，towerj ) 1 5kmtoweri rkrk = rk towerjend end定義 1 軌跡 設(shè) r 是集合 ti 的一個劃分，rk = towerk1 ，towe

17、rk2 ， ，那么 calli，j 可重寫為 trajectoryi，j = t1 ，r1 ， t2 ，r2 ， tn ，rm ，稱作用戶 i 在第 j 天的軌跡。3 3用戶行為模式由話單數(shù)據(jù)得到的用戶歷史軌跡十分離散，難以通過其定義 2 行為模式定義點對 tk ，tk + 1 ，rk 表示用戶 i在時間段tk ，tk + 1處于 ri 區(qū)域，有序集 patterni，j = t1 ，t2 ，r1 ， t3 ，t4 ，r2 ， t2n 1 ，t2n ，rn 稱作用戶 i 在第 j 天的 行為模式。軌跡進行預(yù)測。本文假設(shè)，如果用戶連續(xù)的兩個通話區(qū)域相同那么用戶在這個時間段內(nèi)并未移動。根據(jù)此假設(shè)，

18、離散的用軌跡可以轉(zhuǎn)換成連續(xù)的行為模式。給定軌跡 trajectoryi，j ，用戶 i 在第 j 天的行為模式按照算2 得到。算法 2 pattern extractioninput: trajectoryi，j定義 3軌跡預(yù)測 已知序列 t1 ，r1 ， t2 ，r2 ，tn 1 ，rn 1 ( t1 t2 tn 1 ) ，待預(yù)測時刻 tn ( tn 1 tn ) 以及用戶在 tn 時刻的真實位置 rn 。使用某種預(yù)測算法得到用戶在 tn所處區(qū)域為 r，若 r= rn ，則稱預(yù)測正確; 若 r rn ，則稱預(yù)測122013 年計算機應(yīng)用與軟件output: patterni，j映他的真實軌跡

19、。選取用戶歷史軌跡中最為相似的兩條記錄進行合并，則有可能更加真實地反映用戶的軌跡。1)2)3)4)5)6)7)8)9)10)11)12)3 4for each k doif rk = rk + 1if s is nulls = tk ，tk + 1 ，rk elses = s( 1) ，tk + 1 ，s( 3) end elsepatterni，j = patterni，j s s = nullend end 軌跡預(yù)測算法barabasi 在文獻9中指出，人類的行為有其潛在的規(guī)律例 3 用戶 i 在 j，k 兩天的真實軌跡均為 t ，r ， t ，1 12r ， t ，r ， t ，r ，表

20、示為: trajectory = t ，r ，i，j23 34 411t ，r ， t ，r ，trajectory = t ，r ， t ，r ， t ，2 23 3i，k113 34r4 ，則合并 j，k 這兩天的軌跡得到了真實的軌跡: trajectoryi，jtrajectoryi，k = t1 ，r1 ， t2 ，r2 ， t3 ，r3 ， ，t4 ，r4 。用戶兩天軌跡的相似程度由軌跡差來度量。定理 1三維空間( x，y，t) 中，由 trajectoryi，j 中序列點對依次連結(jié)形成的連續(xù)曲線記作( linexyj ( t) ，linej ( t) ，t) 。d1、d2兩天的軌跡

21、差為:tend 槡( linexd1( t) lined2( t) ) + ( lined1( t) lined2( t) )x2yy2 t start disi( m，n) =t tstart end其中( tstart ，tend ) 是曲線 ( lined1 ( t ) ，lined1 ( t ) ，t ) 與曲線 ( lined2xyx性。這個規(guī)律體現(xiàn)在人類的后一時刻的行為常常取決于前一時刻或前幾個時刻的行為?？梢越Y(jié)合用戶歷史通過前幾次行為來 預(yù)測用戶的下一次行為。例 1 已知 t3 時刻之前的軌跡序列為 t1 ，r1 ， t2 ，r2 。用戶歷史軌跡 trajectoryi 中包含該

22、序列的最頻繁子序列 為 t1 ，r1 ， t2 ，r2 ， t3 ，r3 ，那么用 t3 ，r3 作為預(yù)測 結(jié)果，即預(yù)測用戶在 t3 時刻位于 r3 。人類行為的規(guī)律性還體現(xiàn)在人類的作息以天為單位進行。 在一天中的某時刻或時段，人的行為總是相似的。比如，一個人 在夜晚常常在家中睡覺，白天在單位上班。多數(shù)人的時間還分 為工作日和周末，在工作日，人們主要從事勞動; 在周末，人們主 要休息娛樂。例 2 對于 patterni ，j，k 工作日 ，p 周末 ，使得 ( patterni，j patterni，p ) ( patterni，j patterni，k )根據(jù)上述規(guī)律和假設(shè)，提出算法 3 (

23、 稱之為 match 算法) 來 對用戶軌跡進行預(yù)測。( t) ，liney ( t) ，t) 定義域的交集。d2證明: 對于用戶 i，在同一時刻 t，第 m 天的位置為( xm ，ym ) ，第 n 天的位置為( xn ，yn ) ，這兩天在時刻 t 的距離為:l = 槡( x x ) 2 + ( y y ) 2m nm n兩天平均意義上的距離為:tendtlstartdisi ( m，n) = t tstart end其中 m、n 所對應(yīng)軌跡曲線為 ( fx ( t) ，fy ( t) ，t)、( fx ( t) ，fy ( t) ，m mn nt)。則上式可寫成:tendtstart=槡

24、 fm ( t)(x fm ( t) ) + ( fm ( t) fm ( t) )x2 yy2dis ( m，n)itstart tend如果 f 取由 trajectoryi，j 中序列點對依次連結(jié)形成的連續(xù)曲線 ( linexj ( t) ，linej ( t) ，t) ，那么上式可以寫成:ytendt 槡( linex ( t) linex ( t) ) 2 + ( liney ( t) liney ( t) ) 2d1d2d1d2 start 證畢disi( m，n) =算法 3matcht tstart endinput: t1 ，r1 ， t2 ，r2 ， tn 1 ，rn 1

25、，( t1 t2 tn 1 ) ，tn ，patterni output: r在確定兩天軌跡的相似程度度量方法后，計算 disi ( p，q) ，選取軌跡差最小的前 th% 的用戶軌跡進行合并，得到用戶軌跡1)define tk in patternij to find at2m t2m 1 ，t2m ，rm where t2m 1 tk合并集，稱之為 merge 。具體軌跡合并算法見算法 4。利用 mer-i進行軌跡預(yù)測，實驗證 明，能夠提高預(yù)測準 i 代替gepatterni2)3)4)5)6)7)8)9)10)11)12)13)14)15)16)17)18)3 5satisfy = fo

26、r each j doif tn in patterni，jsatisfy = satisfy patterni，jend endfor each j dofind maxi that tn 1 in satisfyj ，tn 2 in satisfyj ，tn i in satisfyjmatchj = n i endp = max( match)if p0r= rq ，that exists q with t2q 1 ，t2q ，rq satisfyp and t2q 1 tn t2elseuser algorithm most frequent get rend軌跡合并確率。算法 4co

27、mbinationinput: trajectoryi ，n，thoutput: mergei1)2)3)4)5)6)7)8)9)10)11)12)13)14)15)/ / n 為歷史話單數(shù)據(jù)的總天數(shù)，th 為合并記錄比例for every p do for every q doif p = qdisp，q = maxnumelsedisp，q = disi ( p，q)end endendfor j = 1to th* cn 2disp，q is the jth smallest num in dismergei = mergei trajectoryi，p trajectoryi，q en

28、dmergei = mergei trajectoryi用戶一天的通話行為十分離散，使得話單數(shù)據(jù)很難準確反1)人類行為不可知性。在文獻9中，作者詳細論述了實驗4問題，人類的行為雖然有著很強的規(guī)律性，但大約有 7% 的人行為是突發(fā)的、不可預(yù)知的。2) 基站轉(zhuǎn)換。每次通話時都會有一定概率發(fā)生基站轉(zhuǎn)換4 1實驗數(shù)據(jù)本文選用中國某地級市 2007 年 9 月 14 天 1240000 用戶的 話單數(shù)據(jù)。選擇 f0 5 的用戶數(shù)據(jù)進行實驗，滿足該條件的用 戶有 15000。4 2軌跡預(yù)測評估為了計算預(yù)測準確率，我們使用前 13 天的數(shù)據(jù)作為話單數(shù) 據(jù)集 call，應(yīng)用 3 2 節(jié)區(qū)域劃分算法對用戶的活動

29、范圍 ti 進行 劃分，最后使用軌跡預(yù)測策略對最后一天每一個整點時刻進行 預(yù)測，并計算準確率。結(jié)果如圖 1 所示。而不是與最近的基站進行通訊，使得部分驗證數(shù)據(jù)錯誤反映戶位置，影響預(yù)測準確率。3)行為模式并不能完整的反映用戶的歷史行為。用戶通話極為離散，即使是選擇通話行為較頻繁的用戶，其一個小內(nèi)所打出的電話也不過 1、2 個，也就是說，一個小時中，只能得到 1、2 次用戶的位置。用戶的軌跡很可能并未完全暴露，到的行為模式只反映了用戶部分歷史行為。軌跡合并預(yù)測評估針對 4 2 提出的第 3 個影響預(yù)測結(jié)果的因素，我們進行4 3軌跡合并實驗，希望使用用戶軌跡合并集提高預(yù)測的準確率。首先，使用前 13

30、 天的數(shù)據(jù)作為話單數(shù)據(jù)集 call，并對數(shù)做去基站轉(zhuǎn)換修正，應(yīng)用 3 2 節(jié)區(qū)域劃分算法對用戶的活動 圍進行劃分。接下來的步驟與 3 2 節(jié)軌跡預(yù)測實驗方法略有不同。使 算法 3 產(chǎn)生用戶軌跡合并集 merge，用 mergei 代替 trajectoryi 生行為模式 patterni ，并計算預(yù)測準確率。結(jié)果見圖 2。圖 1 不同方法的預(yù)測準確率具體解釋如下:1)case1: 使用 most frequent 算法。將最常訪問的區(qū)域作為軌跡預(yù)測結(jié)果，對數(shù)據(jù)不做額外處理。平均預(yù)測準確率為68 5% 。2) case2: 使用 most frequent 算法。使用 3 1 節(jié)所述算法 對話單

31、數(shù)據(jù)集 call 進行修正。平均預(yù)測準確率為 75 4% 。3) case3: 使用本文提出的 match 算法。使用 3 1 節(jié)所述算 法對話單數(shù)據(jù)集 call 進行修正。平均預(yù)測準確率為 85 4% 。由圖 1 可以得到以下結(jié)論:圖 2 經(jīng)過軌跡合并后預(yù)測準確率由圖 2 可知，隨著軌跡合并比例 th 的增大，平均預(yù)測準 率不斷上升，在 th = 30% 左右時，預(yù)測準確率達到峰值，th 繼 增大，預(yù)測準確率開始下降。這是因為當 th 很小時，只合并軌跡差異最小、最相關(guān)的 錄，合并后的軌跡能夠正確反映用戶的真實軌跡，能夠增大正 預(yù)測軌跡的比率。當 th 過大時，一些不相關(guān)的軌跡記錄也被 并，

32、合并后的軌跡不能反映用戶的真實軌跡，減小了正確預(yù)測 跡的比率。1)對數(shù)據(jù)進行去基站轉(zhuǎn)換處理很有必要。case1 實驗重復(fù)了文獻9中所述算法 most frequent，驗證了其預(yù)測準確率在70% 左右的結(jié)論。case2 實驗對 case1 實驗數(shù)據(jù)額外進行了去基 站轉(zhuǎn)換處理，比較 case1 與 case2，平均預(yù)測準確率提高了 6 9% 。 在具體實驗中，發(fā)現(xiàn)檢測出發(fā)生基站轉(zhuǎn)換的通話記錄只占總記錄 數(shù)的 1 9% 。說明雖然發(fā)生基站轉(zhuǎn)換的比例并不高，但基站轉(zhuǎn)換 錯誤地暴露了用戶位置，去除基站轉(zhuǎn)換，能夠很大程度上提高預(yù) 測準確率。2) 比較 case2 與 case3，發(fā)現(xiàn)本文提出的 matc

33、h 方法較之前 most frequent 的方法預(yù)測準確率提高了 10% 。本文提出的方法 不僅考慮了用戶前幾個時刻表現(xiàn)出來的行為對之后的影響，還 考慮了以天為單位，用戶行為的規(guī)律性。使得在軌跡預(yù)測時，能 夠找到最為相似的歷史中一天，給出合理的預(yù)測結(jié)果。3) 人類在休息時間( 一天的較早時間和較晚時間) 的規(guī)律 性要大于工作時間的規(guī)律性。對于休息時間的軌跡預(yù)測準確率 要高于工作時間的軌跡預(yù)測準確率。尤其是在正午時間，三條 預(yù)測曲線都達到了最小值，說明在正午時間人類行為的規(guī)律性 最差，最為難以預(yù)測。對 match 算法錯誤預(yù)測用戶軌跡的來源進行分析，發(fā)現(xiàn)主圖 2 還可以得出結(jié)論: 人類在以天為

34、單位的時間尺度上，30% 的行為是自相似的。結(jié)語5已有研究大多針對于 gps 等連續(xù)軌跡數(shù)據(jù)，無法預(yù)測離軌跡。本文對離散軌跡( 話單數(shù)據(jù)) 建模得到用戶行為模式，用本文提出的 match 算法，約有 85% 的人類軌跡可以預(yù)測，接使用軌跡合并算法，預(yù)測準確率得到進一步地提高。另外，在 軌跡合并進行研究的基礎(chǔ)上，我們得到了人類在以天為單位 時間尺度上，有 30% 的行為是自相似的結(jié)論?；谝苿訑?shù)據(jù)的軌跡預(yù)測，還應(yīng)有提高預(yù)測準確率的空間結(jié)合社會網(wǎng)絡(luò)的軌跡預(yù)測將是我們進一步研究的方向。( 下轉(zhuǎn)第 17 頁要有三個因素影響了預(yù)測的結(jié)果:第 2 期鄭強等: 基于 sm3 算法的動態(tài)口令卡的設(shè)計與實現(xiàn)17

35、 將時間 t 的分鐘值與 10 做取模運算，記為 t = t分 mod 10( t = 1，2，9) ，并將此時的時間記為 tt。截短口令初值每 次選取三組 m，分別為 mt、mt + 10、mt + 20。 將三個數(shù)組順序組合為 3 個字節(jié)的十六進制數(shù)，即 otp= mtmt + 10mt + 20。 將 otp 轉(zhuǎn)化為十進制數(shù) otp。 將 otp與 106 取模，得到截短的六位數(shù)字口令 p。舉例說明，如果當前時間是 14 點 53 分，則 t = 53mod10 =3，此時時間記為 t3 ，明文經(jīng)過加密，輸出值為 m = debe9ff92275b8a1 38604889 c18e5a4

36、d 6fdb70e5 387e5765 293dcba39c0c5732，取 m3= f9、m13= 8e、m23= 65 順序組合生成 otp = f98e65，轉(zhuǎn)換為十進制數(shù) otp = 16354917。則最終生成 的動態(tài)口令 p = 16354917mod106 = 354917。此種方法保證了生 成口令的二次動態(tài)性，使得非法用戶通過猜測的方法獲得密鑰 幾乎是不可能的，進一步提高了動態(tài)口令算法生成的安全性。于 sm3 算法的動態(tài)口令卡，是國有密碼算法在身份認證領(lǐng)域的具體應(yīng)用。本文提出了基于時間的截短口令算法，實現(xiàn)了截短 口令的二次動態(tài)性，進一步提高了動態(tài)口令算法的安全性。此 外，口令卡

37、采用低功耗芯片設(shè)計，通過測試和仿真實驗表明，達 到了降低系統(tǒng)功耗、延長了使用壽命的設(shè)計目標。本文設(shè)計實 現(xiàn)的動態(tài)口令卡，為 sm3 算法的現(xiàn)實應(yīng)用提供了一個可行的 選擇。參 考 文 獻1 張文 動態(tài)口令系統(tǒng)的設(shè)計與實現(xiàn)j 微計算機信息，2005，21( 3) : 236-2372 顧韻華，劉素英 動態(tài)口令身份認證機制及其安全性研究j 微 計算機信息，2007，23( 33) : 57-593 葉晰，葉依如 基于 md5 算法的動態(tài)口令技術(shù)的軟件實現(xiàn)j 計算機應(yīng)用與軟件，2009，29( 11) : 287-2884 王小云，馮登國，來學(xué)嘉，等 散列函數(shù)中的碰撞eb / ol ht- tp: /

38、 / www cstc net cn / docs / docs php? id = 3235 中華人民共和國國務(wù)院令第 273 號 商用密碼管理條例s / olhttp: / / topic csdn net / t /20011229 /11 /448986 html6 李曉東，賈慧斌 基于時間同步的動態(tài)口令認證系統(tǒng)j 信息網(wǎng) 絡(luò)安全，2010，31( 5) : 71，777 國家密碼管理局 sm3 密碼雜湊算法eb / ol 2010 12 22http: / / www oscca gov cn / upfile /201012221418577866 pdf8 九段 評價微處理器低功

39、耗的五個標準eb / ol 2008 09 24 http: / / www eetrend com / forum /1000235749 高小霞 基于哈希算法的動態(tài)口令令牌的分析設(shè)計與改進eb / ol http: / / wenku baidu com / view /23d30943a8956bec0975e32e html( 上接第 13 頁)參 考 文 獻1 han sangjun，cho sungbae predicting users movement with a combi-實驗驗證3本文設(shè)計和實現(xiàn)的基于時間的動態(tài)口令卡，以 sm3 算法作為加密算法，在 demo 板上實現(xiàn)

40、了每分鐘生成一次動態(tài)口令， 以 6 位數(shù)字顯示在液晶屏上。在 keil c 軟件模擬環(huán)境下，口令 每分鐘更新一次，測得單次口令的平均計算時間和時間刷新時 間均為 200ms 左右。動態(tài)口令系統(tǒng)在不同工作模式下的功耗如 表 1 所示。表 1 系統(tǒng)不同狀態(tài)功耗值nation of self-organizing map and markov modelc/ / icann 2006，883-8932 daniel ashbrook，thad starner using gps to learn significant loca- tions and predict movement across multiple usersj personal and u- biquitous computing，2003，7: 275-2863 jan petzold，faruk bagci，wolfgang trumler，et al global and local state context predictionc/ / artificial intelligence in mobile systems2003 ( aims 2003) in conjunction with the fifth international