在無線網路的環境下，將有愈多的使用者希望隨時隨地都能獲得即時的資訊，而這類提供即時資訊傳遞的服務我們稱為　``Time-Critical　Information　Service'。舉個例子來說，一位汽車駕駛希望能在還沒到達塞車地點前即獲得　``此地區路段的行車資訊'，如此才能變換路道以避免塞車。在這類服務中，使用者希望的是能獲得即時資訊，而我們以　``Expected　Time'　來量化資料的急迫性。在無線網路下的即時資訊傳遞，由於　server　需要對其負責範圍內的所有使用者提供服務，因此等待被傳遞的資料是十分龐大的，但用來傳輸資料的無線頻寬卻是有限的資源。因此如何設計良好的　scheduling　algorithm　以產生有效率的播放排程，並藉由　broadcasting　的方式以盡可能地滿足使用者需求將是一個相當關鍵的議題。過去有關　Time-Critical　Information　Service　的研究，不是只在　single-channel　上討論，便是對於資料的屬性　(如　data　length，expected　time)　做過多的限制以便簡化問題，但如此一來卻也降低了這些方法的實用性。在本篇論文中，我們為了更加符合實際環境的需求而必須面對一個嶄新的問題，並且提出一個有效的演算法以解決這個問題。最後，根據實驗的結果顯示出我們的方法的確是有效率的。

In　wireless　environment,　there　are　more　customers　wishing　to　acquire　up　to　date　information　at　any　where　at　any　time,　and　we　called　the　services　that　providing　the　instant　information　the　``Time-Critical　Information　Service'.　　For　instance,　a　vechicle　driver　may　wish　to　acquire　the　traffic　jam　information　before　arriving　that　area,　so　that　he　may　change　the　route.　　For　this　kind　of　service,　what　the　users　wish　are　instant　information,　so　we　use　``Expected　Time'　to　measure　a　piece　of　information's　``instantaneous'.　　In　wireless　instant　information　transmission,　in　order　for　a　server　to　provide　services　to　all　users　within　the　responsible　area,　there　is　a　enormous　amount　of　data　waiting　to　be　transmitted;　however,　the　wireless　bandwidth　is　a　limited　resources.　　Therefore　desiging　a　good　scheduling　alglrithm　to　generate　efficient　broadcasting　schedules　in　order　to　satisfy　every　single's　user's　need　becomes　a　critical　subject.　　Previous　research　on　the　topic　``Time-Critical　Information　Service'　focused　on　either　single　channel　environment　or　how　to　restrict　data　quality　(e.g.　data　length,　expected　time)　to　simplify　the　question.　　In　this　research,　we　proposed　an　　algorithm　to　solve　the　problem　in　a　real　environment,　and　the　performce　results　proved　that　our　method　is　efficnent.

[1]　Elia　Ardizzoni,　Alan　A.　Bertossi,　Shashank　Ramaprasad,　RomeoRizzi,　and　Madhusudana　V.　S.　Shashanka,　“Optimal　Skewed　Data　Allocation　on　Multiple　Channels　with　Flat　Broadcast　per　Channel,”　in　IEEE　Trans.　Comput.,　2005,　pp　558-572.
[2]　S.　Acharya,　R.　Alonso,　M.　Franklin　,　and　S.　Zdonik,　“Broadcast　disks:　data　management　for　asymmetric　communication　environments,”　in　Proceedings　of　ACM　SIGMOD.,　March　1995,　pp　199-210.
[3]　Sanjoy　Baruah　and　Azer　Bestavros,　“Pinwheel　Scheduling　for　Faulttolerant　Broadcast　Disks　in　Real-time　Database　Systems,”　in　Proceedings　of　the　Thirteenth　International　Conference　on　Data　Engineering.,　1997,　pp　543-551.
[4]　A.　Bar-Noy,　R.　Bhatia,　J.(S.)　Naor,　and　B.　Schieber,　“Minimizing　service　and　operation　costs　of　periodic　scheduling,”　in　In　Proc.　of　the　9th　Annual　ACM-SIAM　Symp.　on　Discrete　Algorithms(SODA’98).,　1998,　pp　11-20.
[5]　Mee　Yee　Chan　and　Francis　Y.　L.　Chin,　“General　Schedulers　for　the　Pinwheel　Problem　Based　on　Double-Integer　Reduction,”　in　IEEE　Transactions　on　Computers.,　pages　755-768,　June　1992.
[6]　Yu-Chi　Chung,　Chao-Chun　Chen　and　Chiang　Lee,　“Time-Constrained　Service　on　Air,”　in　Proceedings　of　the　25th　IEEE　International　Conference　on　Distributed　Computing　Systems　(ICDCS’05).,　pages　739-748,　2005　.
[7]　Jun　Cai　and　Kian-Lee　Tan,　“Tuning　integrated　dissemination-based　information　systems,”　in　Data　Knowledge　Engineering.,　3(1):1-21,　May　1999.　
[8]　Jesus　Fernandez　and　Krithi　Ramamritham,　“Adaptive　dissemination　of　data　in　time-critical　asymmetric　communication　environments,”　in　Mobile　Networks　and　Applications.,　pages　491-505,　ISSN:1383-469X,　October　2004.
[9]　D.　Gifford,　“Polychannel　Systems　for　Mass　Digital　Communications,”　in　CACM.,　33(2),　Feb.　1990.
[10]　Chih-Lin　Hu　and　Ming-Syan　Chen,　“Dynamic　data　broadcasting　with　traffic　awareness,”　in　Proceeding　of　the　22nd　International　Conference　on　Distributed　Computing　Systems　(ICDCS’02).,　pages　112-119,　Vienna,　Austria,　July　2-5　2002.　
[11]　J.-L.　Huang,　M.-S.　Chen　and　W.-C.　Peng,　“Broadcasting　Dependent　Data　for　Ordered　Queries　without　Replication　in　a　Multi-Channel　Mobile　Environment,”　in　Proc.　of　the　19th　IEEE　Intern’l　Conf.　on　Data　Engineering　(ICDE-03).,　Mar.　2003.
[12]　J.-L.　Huang,　M.-S.　Chen　and　W.-C.　Peng,　“Broadcast　Program　Generation　for　Unordered　Queries　with　Data　Replication,”　inProc.　of　the　8th　ACM　Symposium　on　Applied　Computing　(SAC-03).,　Mar.　2003.
[13]　J.-L.　Huang,　M.-S.　Chen　and　W.-C.　Peng,　“Dependent　Data　Broadcasting　for　Unordered　Queries　in　a　Multiple　Channel　Mobile　Environment,”　in　IEEE　Trans.　on　Knowledge　and　Data　Engineering,　Vol.　16,　No.　9.,　Sept.　2004.
[14]　Hao-Ping　Hung　and　Ming-Syan　Chen,　“On　Exploring　Channel　Allocation　in　the　Diverse　Data　Broadcasting　Environment,”　in　Proc.　of　the　25th　IEEE　Intern’l　Conference　on　Distributed　Computing　Systems　(ICDCS-2005).,　Jun　2005.
[15]　R.　Holte,　A.　Mok,　L.　Rosier,　I.　Tulchinsky,　and　D.　Varvel,　“The　pinwheel:　A　real-time　scheduling　problem,”　in　Proc.　22nd　Hawaii　Int.　Conf.　Syst.　Sci.,　1989,　pp　693-702.
[16]　Sohail　Hameed　,　and　Nitin　H.　Vaidya,　“Log-time　algorithms　for　scheduling　single　and　multiple　channel　data　broadcast,”　in　Proceedings　of　the　3rd　annual　ACM/IEEE　international　conference　on　Mobile　computing　and　networking.,　1997,　pp　90-99.
[17]　Chih-Hao　Hsu,　Guanling　Lee　and　Arbee　L.　P.　Chen,　“A　near　optimal　algorithm　for　generating　broadcast　programs　on　multiple　channels,”　in　Proceedings　of　the　tenth　international　conference　on　Information　and　knowledge　management.,　Atlanta,　Georgia,　USA,　ISBN:1-58113-436-3,　pp　303　-　309,　2001.
[18]　G.　Herman,　G.　Gopal,　K.　Lee　and　A.　Weinrib,　“The　Datacycle　Architecture　for　Very　High　Throughput　Database　Systems,”　in　Proc.　ACM　SIGMOD　Conf.,　May　1987.
[19]　T.　Imielinski　and　B.　Badrinath,　“Mobile　Wireless　Computing:　Challenges　in　Data　Management,”　in　CACM.,　37(10),　Oct.　1994.
[20]　T.　Imielinski,　S.　Viswanathan　and　B.　Badrinath,　“Energy　Efficient　Indexing　on　Air,”　in　Proc.　ACM　SIGMOD　Conf.,　May　1994.
[21]　Tomasz　Imielinski　and　S.　Viswanathan,　“Adaptive　wireless　information　systems,”　in　Proceedings　of　the　ACM　Special　Interest　Group　on　DataBase　Systems.,　pages　19-41,　1994.
[22]　T.　Imielinski,　S.　Viswanathan　and　B.　Badrinath,　“Data　on　air:　organization　and　access,”　in　IEEE　Transactions　on　Knowledge　and　Data　Engineering　9(3).,　1997,　pp　353-372.
[23]　Shu　Jiang　and　Nitin　H.　Vaidya,　“Scheduling　data　broadcast　to　“impatien”　users,”　in　Proceedings　of　the　ACM　international　workshop　on　Data　engineering　for　wireless　and　mobile　access.,　pages　52-59,　Seattle,　WA　USA,　August　20　1999.
[24]　R.　Katz,　“Adaption　and　Mobility　inWireless　Information　Systems,”　in　EEE　Personal　Comm.,　1st　Quarter　1994.
[25]　Claire　Kenyon　and　Nicolas　Schabanel,　“The　Data　Broadcast　Problem　with　Non-Uniform　Transmission　Times,”　Springer　New　York,　ISBN　0178-4617　(Paper)　1432-0541　(Online),　2002.
[26]　Wang-Chien　Lee,　Quinlong　Hu　and　Dik　Lun　Lee,　“Dynamic　data　delivery　in　wireless　communication　environments,”　in　Proceedings　of　ER’98　Workshops　on　Mobile　Data　Access,　volume　1552　of　Lecture　Nodes　in　Computer　Science.,　pages　218-229,　1998.
[27]　Wen-Chin　Peng　and　Ming-Syan　Chen,　“Dynamic　Generation　of　Data　Broadcast　Programs　for　a　Broadcast　Disk　Array　in　a　Mobile　Computing　Environment,”　in　Proc.　of　ACM　9th　Intern’l　Conf,　on　Information　and　Knowledge　Management.,　2000,　pp　167-176.
[28]　Wen-Chin　Peng　and　Ming-Syan　Chen,　“Efficient　Channel　Allocation　Tree　Generation　for　Data　Broadcasting　in　a　Mobile　Computing　Environment,”　in　ACM/Kluwer　Wireless　Networks,　9:2.,　2003,　pp　117-129.
[29]　Konstantinos　Stathatos,　Nick　Roussopoulos　and　John　S.　Baras,　“Adaptive　data　broadcast　in　hybrid　networks,”　in　Proceedings　of　the　23rd　International　Conference　on　Very　Large　Data　Bases.,　pages　326-335,　August　1997.
[30]　N.H.　Vaidya　and　S.　Hameed,　“Scheduling　data　broadcast　in:　asymmetric　communication　environments,”　in　Wireless　Networks　5(3).,　1999,　pp　171-182.
[31]　Ping　Xuan,　Subhabrata　Sen,　Oscar　Gonzalez,　Jesus　Fernandez　and　Krithi　Ramamritham,　“Broadcast　on　demand:　Efficient　and　timely　dissemination　of　data　in　mobile　environments,”　in　Proceedings　of　the　3rd　IEEE　Real-Time　Technology　and　Applications　Symposium　(RTAS’97).,　pages　38-48,　Montreal,　Canada,　June　9-11　1997.