بخشی از مقاله
بررسي الگوريتم هاي فشرده سازي بدون اتلاف ومقايسه دو الگوريتم
LEC,S-LEC از نظردرصد فشرده سازي و مصرف انرژي در شبکه حسگر بيسيم
خلاصه
فشرده سازي داده روشي است براي کاهش هزينه ذخيره سازي از طريق حذف اطلاعات تکراري که در اکثر فايلها اتفاق مي افتد. دو روش فشرده سازي داده وجود دارد فشرده سازي بدون اتلاف و با اتلاف . فشرده سازي با اتلاف اندازه فايل را با حذف اطلاعات غير ضروري کاهش مي دهد ،فشرده سازي بدون اتلاف از طرف ديگر هر بيت از داده ها را دستکاري مي کند تا اندازه فايل را بدون از بين رفتن داده ها بعد از کدبرداري حداقل نمايد.ما در اين مقاله الگوريتم هاي فشرده سازي بدون اتلاف بررسي ميشوند همچنين الگوريتم هاي S-LEC,LEC با داده هاي دما و رطوبت از نظر فشرده سازي و مصرف انرژي مقايسه ميشوند.
١. مقدمه
پيشرفت هاي اخير در فناوري شبکه هاي حسگر اين امکان را داده است که نودهاي حسگري با توانايي حس کردن انواع مختلفي از شرايط محيطي و فيزيکي، پردازش داده و ارتباط بيسيم داشته باشيم . اين تنوع در حس کردن باعث به کار بردن اين شبکه ها در محيط هاي مختلف شده است . اما خصوصيات شبکه هاي حسگر بيسيم مانند محدوديت پهناي باند، حافظه ، توانايي محاسباتي، افزونگي داده اين شبکه را از انواع ديگر شبکه ها متمايز ميکند و بنابراين به روش هاي
موثرتري براي انتقال و مسيريابي داده نياز دارد.قابليت مهم اين نوع شبکه ها آن است که در محلي که انسان قادر نيست در آنجا حضور يابد و يا حضور انسان باعث تغيير رفتار محيط مي شود مي توانند قرار گيرند و اطلاعات محيط را براي کاربر ارسال نمايند.
يکي از روشهاي مناسب براي استفاده بهينه از منابع محدود گره هاي حسگر مانند (سرعت پردازش پايين ، حافظه کم و محدوديت توان ) استفاده از فشرده سازي داده است . داده هاي گرد آوري شده از گره هاي همسايه هميشه تکراري و افزودني هستند و بسيار زياد مي باشند. به علاوه اين مقدار داده توليد شده در شبکه هاي حسگر بزرگ براي پردازش در ايستگاه مرکزي بسيار زياد است . بنابراين استفاده از روش هايي براي ترکيب داده ها براي توليد اطلاعات با کيفيت بالا در گره هاي حسگر که تعداد و ميزان بسته هاي ارسالي را کاهش دهد و در نتيجه انرژي و پهناي باند کمتري را مصرف کند ضروري است .{١} فشرده سازي در روش محلي به دو دسته فشرده سازي اتلافي (فشرده سازي با اتلاف ) و فشرده سازي بهينه (فشرده سازي بي اتلاف ) اطلاعات تقسيم مي شوند. فشرده سازي با اتلاف حالتي است که در آن داده ها يکبار فشرده سازي ميشوند و يکبار هم ، ناهم فشرده ميشوند. به طوري که داده دوباره بدست آمده اندکي با داده اصلي فرق دارد، ولي هنوز قابل استفاده است . فشرده سازي بياتلاف ، اطلاعات دسته اي از الگوريتم هاي فشرده سازي اطلاعات است که به داده اصلي اجازه ميدهد از داده فشرده شده دقيقاً نوسازي شود. واژه بياتلاف در تقابل با فشرده سازي بااتلاف اطلاعات است که در آن داده نوسازيشده ، نزديک به داده اصلي ساخته ميشود و اين کار به خاطر فشرده تر شدن داده ها صورت ميگيرد.
٢.آنتروپي
در فشرده سازي داده سعي بر حذف بخش افزونه داده حسگرها و کاهش همبستگي داده اي ميان داده ها و فراهم کردن اطلاعات مفيد و بدون افزونگي براي ايستگاه مرکزي مي باشد. منبع داده هر گره حسگر را با يک متغير تصادفي گسسته نمايش مي دهيم . آنتروپي متغير تصادفي گسسته X با نماد نمايش داده ميشود و برابر کمينه تعداد بيتهاي لازم براي کد کردن X بدون از دست دادن اطلاعات مي باشد. آنتروپي مشترک دو متغيير تصادفيY و X برابر کمينه تعداد بيتهايي لازم براي کد کردن مشترک Y و X است . اگر X شامل اطلاعاتي در موردY باشد آنگاه آنتروپي مشترک برابر خواهد بود با و بر طبق رابطه داريم که در صورت همبستگي داده اي، کاهش قابل توجهي در حجم داده کد شده بدست خواهد آمد. {٢}
٢. ١ويژگي هاي فشرده سازي آنتروپي:
١. تخصيص کدهاي متفاوت به عنصرهاي متفاوت از داده
٢. طول کدها متناظر است با تعداد تکرار عنصرها
٣. تخصيص بيت هاي کمتر به داده هاي با احتمال وقوع بالاتر
S={s1,s2,…,sn}
- pi : احتمال وقوع عنصر si
- (H)s: تعداد بيت هاي مورد نياز براي کد گذاري si.
Variable-Length Coding(VLC) .3
يکي از راههاي فشرده سازي داده استفاده از کدگذاري VLC است . اين دسته از الگوريتم ها بر اساس احتمال وقوع هر
کاراکتر عمل مي کنند و داراي چندين ويژگي مهم هستند:
١. کدهاي متفاوت ، طول هاي متفاوت دارند.
٢. کد کاراکترهايي که احتمال کمتري دارند طول بيشتري دارند و کد کاراکترهايي که احتمال بيشتري دارند طول بيت کمتري دارند.
٣. گرچه طول کدها متفاوت است ولي مي توانند به صورت يکجا بازيابي شوند.
الگوريتم هاي زيادي در رابطه با فشرده سازي داده بدون اتلاف ارائه شده که در ادامه به بررسي هر يک مي پردازيم .
٣ ١.الگوريتم شانون – فانو (Fano -shanon )
اين الگوريتم يک روش بالا به پايين ( top-down) محسوب مي شود.
مراحل اجراي الگوريتم به صورت زير است :
١-نمادها را بر اساس فراواني مرتب مي کنيم
٢- نمادها را به صورت بازگشتي به دو قسمت تقسيم مي کنيم ، هر کدام با تعداد شماره هاي تقريبا برابر ، تا جايي که هر قسمت فقط يک نماد داشته باشد .در شکل ١ درخت کدينگ HELLO و همچنين نتايج اجراي
الگوريتم در جدول ١ نشان داده شده است .
٣. ٢.الگوريتم هافمن
الگوريتم فشرده سازي هافمن را ديويد هافمن پروفسور دانشگاه MIT آمريکا اختراع کرد. روش فشرده سازي هافمن الگوريتمي است که براي فشرده سازي متن مناسب است .
الگوريتم هافمن جزو خانواده ء الگوريتم هايي است که طول کد متغييري دارند. اين به آن معناست که نماد هاي مجزا (براي نمونه کاراکترهايي در يک فايل متني) با رشته بيت هايي که طول هاي مختلفي دارند تعويض مي شود. بنابراين نماد هايي که زياد در يک فايل تکرار مي شوند يک رشته بيت کوتاه مي گيرند در حالي که نمادهاي ديگر که به ندرت ديده مي شوند رشته بيت طولاني تري رامي گيرند.
يک الگوريتم کدگذاري براي فشرده سازي بياتلاف اطلاعات است . اين تعبير بر ميگردد به استفاده از جدول کد طول متغير براي کد کردن هر کدام از نشانه هاي مبدا (مانند کاراکترهاي يک فايل ). جدول کد طول متغير از روشي بخصوص مبني بر احتمال وقوع هر کدام از نشان هاي مبدا بدست ميآيد. اين روش بوسيله ديويد هافمن توسعه يافت .
اين روش جزء روشهاي پايين به بالا محسوب مي شود.
مراحل اجراي الگوريتم به ترتيب زير است :
١. تمام نمادها بر اساس فراواني آنها در يک ليست مرتب مي کنيم .
٢. تازماني که فقط يک نماد باقي بماند ، ادامه مي دهيم :
١)دو نمادي که داراي کمترين فراواني هستند را از ليست بر مي داريم . يک زير درخت هافمن ايجاد مي کنيم و اين دو نماد را به عنوان گره فرزند قرار مي دهيم و يک گره پدر ايجاد مي کنيم .
٢)جمع تعداد فرزندان را به نود پدر اختصاص داده و در ليست مرتب وارد مي کنيم .
٣)فرزندان را از ليست حذف مي کنيم .
٣. از عمليات فوق يک درخت دو دويي حاصل مي شود ، بر روي اين درخت هر مسير به سمت چپ با صفر و هر مسير سمت راست با يک وزن دهي مي شود.
٤. کد هر کاراکتر با کنار هم گذاشتن وزن ها از ريشه تا آن کاراکتر به دست مي آيد.شکل ٢ کد گذاري هافمن را براي کلمه HELLO نشان مي دهد.
مثال ) کدينگ کلمه HELLO
شکل ٢.کدگذاري هافمن
-٣-٢-١کد قانوني هافمن
اگر وزن هاي مربوط به ورودي هاي مرتب شده بر اساس الفبا، به ترتيب عددي باشند، کد هافمن طولي برابر طول کد الفبايي بهينه دارد که ميتواند از طريق محاسبه بدست آيد. کد بدست آمده از ورودي هاي مرتب شده از نظر عددي ،کد قانوني هافمن گفته مي شود و کدي است که به خاطر سادگي رمز کردن و رمز گشايي ،در عمل استفاده مي شود. تکنيک پيدا کردن اين کد ، اکثرا کد گذاري هافمن -شانون -فانوناميده ميشود. و اين به خاطر آن است که مانند کدگذاري هافمن بهينه ، ولي در احتمال وزن ها مانند کد گذاري شانون – فانو الفبايي است . کد هافمن شانون - فانو مربوط به اين مثال
{٠٠٠,٠٠١,٠١,١٠,١١} است که در آن طول کد کلمه ها ، همان مقداري است که در حل اصلي آمده است .
٣. ٢.٢.کد هافمن با ارزش حرفي متفاوت
در کد گذاري استاندارد هافمن ، فرض شده است که هر نماد در مجموعه اي که کد ها از آن استخراج مي شوند،ارزشي يکسان با بقيه دارد: کد کلمه اي که طول آن N است ارزشي برابر N خواهد داشت ،مهم نيست که چند رقم آن ١ و چند رقم آن ٠ است . وقتي با اين فرض کار مي کنيم ، کم کردن هزينه کلي پيام ، با کم کردن تعداد رقم هاي کل ٢ چيز يکسان هستند. کد هافمن با ارزش حرفي متفاوت به نحوي عموميت يافته که اين فرض ديگر صحيح نيست : حروف الفباي
کدگذاري ممکن است طول هاي غير همساني داشته باشند ، به خاطر خصوصيت هاي واسطه انتقال . مثالي بر اين ادعا،
الفباي کد گذاري کد مورس است ، که در آن فرستادن يک "خط تيره " بيشتر از فرستادن يک "نقطه " طول ميکشد پس ارزش خط تيره در زمان انتقال بالاتر است . درست است که هدف هنوز کم کردن ميانگين طول وزني کد است اما ديگر کم کردن تعداد نماد هاي بکار برده شده در پيام ، به تنهايي کافي نيست . هيچ الگوريتمي شناخته نشده است که اين را به همان روش و همان کارآيي کد قراردادي هافمن انجام دهد.
٣.٢.٣.انواع کد هافمن
انواع مختلفي از کد گذاري هافمن وجود دارد، که بعضي از آنها از الگوريتم هايي شبيه الگوريتم هافمن و بعضي ديگر از کدهاي بهينه پيشوندي (با محدوديت هاي خاص براي خروجي)استفاه ميکنند. در حالت اخير، نياز نيست که روش ، شبيه روش هافمن باشد و حتي ممکن است زمان اجرايي چندجمله اي هم نداشته باشد. ليست کاملي از مقالات مربوط به انواع مختلف کد گذاري هافمن ، در «درخت هاي کد و تجزيه براي کد کردن بي زيان اطلاعات » داده شده است .
١.٣.٢.٣.کد هافمن n تايي
الگوريتم کد هافمن n تايي از الفباي {٠, ١ – n ,...,١} براي کد کردن پيام ها و ساختن درخت n تايي استفاده مي کند.
اين روش دسترسي بوسيله هافمن و در مقاله اش بررسي شده بود.
٢.٣.٢.٣.کد هافمن انطباقي
نوع ديگري به نام کد هافمن انطباقي، احتمالاتي را که به صورت پويا و بر اساس تکرار واقعي در منبع اصلي است ، محاسبه ميکند. اين به گونه اي مربوط به خانواده الگوريتم هاي LZ است .
٣.٣.٢.٣.کد هافمن با طول محدود
کد هافمن با طول محدود نوعي ديگر از کد هافمن است . اين نوع هنگامي مورد استفاده قرار ميگيرد که هدف هنوز بدست آوردن طول مسير با کمترين وزن است اما يک شرط ديگر نيز وجود دارد و آن اين است که اندازه هر کد، بايد کمتر از مقدار ثابت خاصي باشد. الگوريتم بسته بندي ادغام اين مشکل را بوسيله يک الگوريتم حريصانه ساده شبيه به هماني که در الگوريتم هافمن بکار رفته بود، حل ميکند. پيچيدگي زماني اين الگوريتم ,(O)nL که L ماکزيمم طول يک کدکلمه است .
رمزگزاري هافمن به دو روش مختلف مي تواند بهينه تر شود:
١- کد هافمن انطباقي به صورت پويا کلمات کد را با توجه به تغيير احتمال وقوع نماد ها تغيير مي دهد.
٢- فشرده سازي گسترده ء هافمن مي تواند گروهي از نماد ها را نسبت به يک نماد رمز گزاري کند .
اين روش مي تواند بين ٢٠% تا ٩٠% اطلاعات را فشرده کند .اين الگوريتم فشرده سازي اساسا براي فشرده سازي متون و
فايل هاي برنامه سودمند است .
GOLOMB- Coding .3.3
اين روش که يکي از روش هاي فشرده سازي بدون اتلاف است توسط گولومب در سال ١٩٦٦ پيشنهاد گرديد. در اين روش ورودي N به دسته هاي به اندازه M تقسيم مي گردد. سپس خارج قسمت q توسط unary coding رمز و باقيمانده توسط binary codig رمز مي شود. در شکل ٣ روش Golomb- Coding نشان داده شده است .
نسخه رمزنگاري Exponential-Golomb يا Exp-Golomb يک نوع از رمزنگاري سراسري ميباشد. در فشرده سازي داده رمزنگاري سراسري براي اعداد يک کد پيشوند است که ، نگاشت اعداد مثبت را به کلمات رمز باينري نشان مي دهد.
در رمزنگاري Exp-Golomb هدف کد کردن هر عدد غير منفي صحيح x با استفاده از رمزنگار Exp-Golomb است .
- ١+x به صورت باينري نوشته مي شود
- بيت هاي نوشته شده شمرده مي شود. از يک کم مي شود و به همين تعداد صفر در ابتدا رشته مي گذاريم . به
عنوان مثال داريم :
٤.٣.الگوريتم LZW
الگوريتم LZW يک الگوريتم برگشت پذير و مبتني بر ديکشنري است ، بدين معني که هيچ اطلاعاتي را از دست نمي دهد و رمز گشا قادر خواهد بود داده اوليه را عينا بازسازي نمايد.قدرت فشرده سازي اين الگوريتم از ساير الگوريتم ها از جمله هافمن بيشتر خواهد بود. اين الگوريتم از کلمه رمزهايي با طول ثابت براي کد کردن رشته اي از سمبل _ها با طول متغير استفاده مي کند. و نيازي به ارسال ديکشنري همراه داده ها نيست و انديس کلمات موجود در ديکشنري به عنوان کلمه رمز ارسال مي شود. در ابتدا ديکشنري فقط شامل مجموعه کاراکترها ست که به مرور زمان با دريافت ورودي ديکشنري تکميل تر مي شود.
مثال : رمز گذاري رشته ABABBABCABABBA .در جدول ٢کد گذاري را براي رشته
ABABBABCABABBA نشان داده شده است .{٣}
